2019ICPC南京站

2023-11-23 11:30
文章标签 南京站 2019icpc

本文主要是介绍2019ICPC南京站，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A

A Hard Problem

题意：给定一个正整数 n ，你需要找出最小整数 k，满足：从{1,2,⋯,n}中任意选择长度为k的子集，存在两个不同的整数 u,v∈T, 且 u 是 v 的因数。

思路：打表找规律 k = \left \lceil n/2 \right \rceil + 1

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e8+10;
const int inf=0x3f3f3f3f;using namespace std;void solve()
{int n;cin>>n;cout<<(n+3)/2<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;// get();// cout<<cnt<<'\n';int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

C

Digital Path

题意：给定一个n*m的数字矩阵，从入度为0的点出发，每次操作只能向上下左右且增值为1的格子移动，终点为出度为0的点。求长度大于等于4的路径个数。

思路：先算出每个点的出度入度，从入度为0的开始bfs，更新方案数。

f[i][j][x]表示到达点(i, j)路径长度为x的方案数，特别的f[i][j][4]表示到达点(i, j)路径长度大于等于4的方案数。更新方式如下：

f[nx][ny][2] += f[x][y][1]

f[nx][ny][3] += f[x][y][2]

f[nx][ny][4] += f[x][y][3] + f[x][y][4]

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>typedef long long ll;
const int N=1010;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
using namespace std;
int n,m;
int a[N][N];
int in[N][N],out[N][N];
int f[N][N][5];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void bfs()
{queue<pair<int,int>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(in[i][j]==0) {q.push({i,j});f[i][j][1]=1;}while(q.size()){int x=q.front().first,y=q.front().second;q.pop();for(int k=0;k<4;k++){int nx=x+dir[k][0],ny=y+dir[k][1];if(nx<1||nx>n||ny<1||ny>m) continue;if(a[nx][ny]==a[x][y]+1){f[nx][ny][2]=(f[nx][ny][2]%mod+f[x][y][1])%mod;f[nx][ny][3]=(f[nx][ny][3]%mod+f[x][y][2])%mod;f[nx][ny][4]=((f[nx][ny][4]%mod+f[x][y][3]%mod)%mod+f[x][y][4]%mod)%mod;in[nx][ny]--; if(in[nx][ny]==0) q.push({nx,ny});}}}
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=0;k<4;k++){int nx=i+dir[k][0],ny=j+dir[k][1];if(nx<1||nx>n||ny<1||ny>m) continue;if(a[nx][ny]==a[i][j]+1) out[i][j]++;else if(a[nx][ny]==a[i][j]-1) in[i][j]++;}bfs();int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(out[i][j]==0) ans=(ans%mod+f[i][j][4])%mod;cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

H

Prince and Princess

题意：

有n个房间,每个房间有一个人,他们知道任一个人在哪个房间,其中公主在某一房间.你可以问任一房间的人下列三个问题之一:①你是谁;②某个房间里的人是谁;③公主在哪个房间.

这n个人可分为三类,说真话、说假话、可能说真话也可能说假话,分别有a , b , c( 0 < a , b , c < 2e5 )人.至少问几次才能确定公主在哪个房间.若无法确定,输出"NO";若可以确定,输出"YES",下一行输出最小询问次数.

思路：考虑最坏情况，开始问的(b+c)个人都说假话，都回答错误答案A，再接着问(b+c)个人都说真话，都回答答案B，此时两个答案选择人数相同；再多问一个人，就可以区分出哪个是真话。所以至少需要问a+b+a+b+1=2(a+b)+1次，当总人数a+b+c >= 2(b+c)+1时，即a>=b+c+1时，输出YES。注意需要特判a=1 b=0 c=0时，只有公主一人时不需要询问。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int a,b,c;
void solve()
{cin>>a>>b>>c;if(b+c>=a) cout<<"NO\n";else {cout<<"YES\n";if(a==1&&b==0&&c==0) cout<<0<<'\n';else if(b==0&&c==0) cout<<1<<'\n';else cout<<2*(b+c)+1<<'\n';}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

K

Triangle

题意：给定三角形三个顶点的坐标，给定点p，在三角形上找一点q的坐标，使得pq可以平分三角形面积。若p点不在三角形上时输出-1.

思路：分类讨论，讨论p在哪条边上，更靠近边的哪个顶点，在对应的边上二分求点q

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
const double eps=1e-7;
using namespace std;
inline double sqr(double x){return x*x;}
int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1;
}struct Point{double x,y;Point(){}Point(double _x,double _y){x = _x;y = _y;}void input(){scanf("%lf%lf",&x,&y);}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}//叉积double operator ^(const Point &b)const{return x*b.y - y*b.x;}//点积double operator *(const Point &b)const{return x*b.x + y*b.y;}//返回两点的距离double distance(Point p){return hypot(x-p.x,y-p.y);}Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}Point operator *(const double &k)const{return Point(x*k,y*k);}};struct Line{Point s,e;Line(){}Line(Point _s,Point _e){s = _s;e = _e;}// 点在线段上的判断bool pointonseg(Point p){return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;}};Point mid_(Point a, Point b)
{return (a+b)*0.5;
}double area(Point a, Point b, Point c)
{return fabs((b - a) ^ (c - a) * 0.5);
}void solve()
{Point a,b,c,p;Line ab,ac,bc;a.input();b.input();c.input();p.input();ab=Line(a,b);ac=Line(a,c);bc=Line(b,c);if(!ab.pointonseg(p)&&!ac.pointonseg(p)&&!bc.pointonseg(p)){printf("-1\n");}else{double s=area(a,b,c)/2;if(ab.pointonseg(p)){double dispa=p.distance(a);double dispb=p.distance(b);if(dispa<dispb){Point l=b,r=c;Point mid;int x=50;while(x--){mid=mid_(l,r);int ret=sgn(area(mid,p,b)-s);if(ret>0) r=mid;else if(ret<0) l=mid;else break;}printf("%.10f %.10f\n",mid.x,mid.y);}else{Point l=a,r=c;Point mid;int x=50;while(x--){mid=mid_(l,r);int ret=sgn(area(mid,p,a)-s);if(ret>0) r=mid;else if(ret<0) l=mid;else break;}printf("%.10f %.10f\n",mid.x,mid.y);}}else if(ac.pointonseg(p)){double dispa=p.distance(a);double dispc=p.distance(c);if(dispa<dispc){Point l=c,r=b;Point mid;int x=50;while(x--){mid=mid_(l,r);int ret=sgn(area(p,mid,c)-s);if(ret>0) r=mid;else if(ret<0) l=mid;else break;}printf("%.10f %.10f\n",mid.x,mid.y);}else{Point l=a,r=b;Point mid;int x=50;while(x--){mid=mid_(l,r);int ret=sgn(area(p,mid,a)-s);if(ret>0) r=mid;else if(ret<0) l=mid;else break;}printf("%.10f %.10f\n",mid.x,mid.y);}}else{double dispb=p.distance(b);double dispc=p.distance(c);if(dispb<dispc){Point l=c,r=a;Point mid;int x=50;while(x--){mid=mid_(l,r);int ret=sgn(area(p,mid,c)-s);if(ret>0) r=mid;else if(ret<0) l=mid;else break;}printf("%.10f %.10f\n",mid.x,mid.y);}else{Point l=b,r=a;Point mid;int x=50;while(x--){mid=mid_(l,r);int ret=sgn(area(p,mid,b)-s);if(ret>0) r=mid;else if(ret<0) l=mid;else break;}printf("%.10f %.10f\n",mid.x,mid.y);}}}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;// cin>>_t;scanf("%d",&_t);while(_t--) solve();system("pause");return 0;
}

J

Spy

题意：给定n个敌人的力量值a[i]，及击杀敌人获得的荣誉值p[i].给定你的第一队的力量值b[i]，第二队的力量值c[i].需要将b[i]与c[j]一一配对后组成n只队伍d[]，新的力量值为两人之和，d[]再与a[]随机战斗，每只队伍只能战斗一次，共n!种情况。若d[i]>a[i]我方获得荣誉值p[i].求可获得的荣誉的最大期望乘n的值，数据保证最大期望乘n后是整数

思路：把b[]和c[]当作二分图，边的权值为这对组合可以获得的荣誉值之和。然后进行KM算法，找到最大权值匹配即为答案。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=410;
const int inf=0x3f3f3f3f;
const ll infll=1e15+7;
using namespace std;
int n;
ll a[N],p[N],b[N],c[N];
ll w[N][N];
ll la[N], lb[N], upd[N]; // 左、右部点的顶标
bool va[N], vb[N]; // 访问标记：是否在交错树中
ll match[N]; // 右部点匹配了哪一个左部点
ll last[N]; // 右部点在交错树中的上一个右部点，用于倒推得到交错路bool dfs(ll x, ll fa) 
{va[x] = 1;for(int y = 1; y <= n; y++){if(!vb[y]){if(la[x] + lb[y] == w[x][y]) { vb[y] = 1; last[y] = fa;if(!match[y] || dfs(match[y], y)) {match[y] = x;return true;}}else if(upd[y] > la[x] + lb[y] - w[x][y]) {upd[y] = la[x] + lb[y] - w[x][y];last[y] = fa;}}}return false;
}ll KM() 
{for(int i = 1; i <= n; i++) {la[i] = -infll;lb[i] = 0;for(int j = 1; j <= n; j++) la[i] = max(la[i], w[i][j]);}for(int i = 1; i <= n; i++) {memset(va, 0, sizeof(va));memset(vb, 0, sizeof(vb));for(int j = 1; j <= n; j++) upd[j] = infll;// 从右部点st匹配的左部点match[st]开始dfs，一开始假设有一条0-i的匹配int st = 0; match[0] = i;while(match[st]) 	// 当到达一个非匹配点st时停止{ ll delta = infll;if(dfs(match[st], st)) break;for(int j = 1; j <= n; j++)if(!vb[j] && delta > upd[j]) {delta = upd[j];st = j; 		// 下一次直接从最小边开始DFS}for(int j = 1; j <= n; j++)  // 修改顶标{if(va[j]) la[j] -= delta;if(vb[j]) lb[j] += delta; else upd[j] -= delta;}vb[st] = true;}while(st)	// 倒推更新增广路 { match[st] = match[last[st]];st = last[st];}}ll ans = 0;for(int i = 1; i <= n; i++) if(match[i]) ans += w[match[i]][i];return ans;
}void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>p[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) cin>>c[i];for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){ll sum=0;for(int k=1;k<=n;k++)if(b[i]+c[j]>a[k]) sum+=p[k];w[i][j]=sum;}cout<<KM()<<'\n';}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

这篇关于2019ICPC南京站的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/417610。

相关文章

2019ICPC秦皇岛I Invoker

2019ICPC秦皇岛I Invoker

Problem Description 在 dota2 中有一个叫做祈求者(Invoker)的英雄，在游戏中他有三个基础技能：冰(Quas)，雷(Wex)，火(Exort)，每施展一个技能就可以获得相应属性的一个法球(element)。 但是祈求者同时最多只能有三个法球，即如果他在有三个法球的状态下又使用了某个法球技能，那么他会获得该法球，并失去之前三个法球中最先获得的一个。 不难得出，祈求者身
阅读更多...
2020年ICPC南京站 补题记录

2020年ICPC南京站 补题记录

文章目录 A - Ah, It's Yesterday Once More（构造）E - Evil Coordinate（构造）F - Fireworks（概率+三分）H - Harmonious Rectangle（打表）K - K Co-prime Permutation（签到）L - Let's Play Curling（贪心+签到）M - Monster Hunter（树形dp）
阅读更多...
2020ICPC南京站补题题解

2020ICPC南京站补题题解

菜鸡只写银牌以下的题 这场铜牌4题，银牌5~6题 K Co-prime Permutation 题意： 构造一个n长的1到n不重复序列p，其中 p i p_i pi​和 i i i互质的个数有k个 思路： 已知： n n n和 n − 1 n-1 n−1互质，1和任何数互质，任何数和它本身不互质 k要是奇数，1不变，后面的 k − 1 2 \frac{k-1}{2} 2k−1​对数，两两换
阅读更多...
2022年ICPC亚洲区域赛南京站题解

2022年ICPC亚洲区域赛南京站题解

文章目录 I: 完美回文G: 邪恶铭刻A:停停，昨日请不要重现D: 聊天程序(待补) I: 完美回文 解题思路: ​ 签到题，没什么好讲的。 解题代码： void solve() {vector<int> a(30, 0);string str;cin >> str;int maxx = 0;for(auto i : str){a[i - 'a'] ++;if(a[i
阅读更多...
2022icpc亚洲区域赛（南京站）Problem D - 聊天程序

2022icpc亚洲区域赛（南京站）Problem D - 聊天程序

2022 i c p c 亚洲区域赛（南京站） P r o b l e m D − 聊天程序 \Huge{2022icpc亚洲区域赛（南京站）Problem D - 聊天程序} 2022icpc亚洲区域赛（南京站）ProblemD−聊天程序 文章目录 题意思路标程 题目链接：Problem - D - Codeforces 官方题解：D - 聊天程序 - SUA Wiki
阅读更多...
2022ICPC（南京站）

2022ICPC（南京站）

I题 思路：这是一个签到题比较简单，只要判断出字符串中出现最多的字符，然后再让字符总数减去就行了 代码如下 //I#include<iostream>#include<algorithm>#include<string>#include<map>#define int long long#define endl '\n'#define IOS ios::sync_with_st
阅读更多...
2019ICPC 银川区域赛 Base62（进制转换 java）

2019ICPC 银川区域赛 Base62（进制转换 java）

As we already know, base64 is a common binary-to-text encoding scheme. Here we define a special series of positional systems that represent numbers using a base (a.k.a. radix) of 22 to 6262. The symbo
阅读更多...
【南京站-EI会议征稿中】第三届网络安全、人工智能与数字经济国际学术会议（CSAIDE 2024）

【南京站-EI会议征稿中】第三届网络安全、人工智能与数字经济国际学术会议（CSAIDE 2024）

第三届网络安全、人工智能与数字经济国际学术会议（CSAIDE  2024） 2024 3rd International Conference on Cyber Security, Artificial Intelligence and Digital Economy 第三届网络安全、人工智能与数字经济国际学术会议（CSAIDE 2024）将于2024年3月1-3日在中国南京召开。会议将围
阅读更多...
2019南京站（重温经典）

2019南京站（重温经典）

2019南京站（重温经典） 导语涉及的知识点题目ACHJK 参考文献 导语 日常练习，这一次做的不是很满意 涉及的知识点 思维，乘法逆元，组合数学，拓扑排序，DP，二分图最大权匹配，平面几何 链接：南京2019区域赛 [Cloned] 题目 A 题目大意：给出一个正整数n，找到一个最小的整数k使得集合 { 1 , 2 , … n } \{1,2,\dots n\}
阅读更多...
南航c语言程序设计,第43届ACM/ICPC国际大学生程序设计竞赛亚洲区域赛（南京站）在南航成功举行...

南航c语言程序设计,第43届ACM/ICPC国际大学生程序设计竞赛亚洲区域赛（南京站）在南航成功举行...

10月13日至14日，第43届ACM/ICPC国际大学生程序设计竞赛亚洲区域赛(南京站)在南京航空航天大学将军路校区拉开帷幕。本次大赛吸引了来自全国184所高校、3所中学和1家企业共333支队伍参赛(含香港大学3支队伍)，近千名程序设计精英们汇聚南航，同场竞技。经过热身赛的赛场环境适应和正式赛的激烈角逐，来自清华大学的“中二之力”战队赢得了本次比赛的冠军，获得了直接进入ACM/ICPC国际大学生
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2