Nordic Collegiate Programming ContestNCPC 2021

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

Date:October 9, 2021

Dashboard - 2021-2022 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2021) - Codeforces

Problem - C - Codeforces--Customs ControlsProblem - C - Codeforces-

题意:给定一个n个点，m条边的无向图，并且每个点带有权值。你可以任意摆k个N警察和n-k个S警察在任意点上，使得每个点上恰好有一个警察。因为总会有走私犯从1到n，并且走的是最短路。你需要放置警察，使得所有走1到n最短路的走私犯都被逮捕。当且仅当A，B点的警察同为N或S警察时，路过A，B的走私犯会被逮捕。问输出放置警察的方案 or impossible.

思路:要注意的是，权值是在点上的，而不是在边上的! 并且! 极端的情况是如下图的：

这样n个点的图，可以产生最多的最短路(n-2条)，那么贪心摆放肯定是可以满足条件的。

但是类似下图的图:

看似会产生比n-2条更多的最短路，有5条最短路，但是实际上这是不可能的，因为权值的点上，当1-->6是最短路，那么其他四条就不可能是最短路。

那么显而易见，除了样例的情况，其他情况都是有解的(得大胆相信赛时的结论).

那么剩下要做的，只需要找出和点1邻近的在最短路中的点near1，和点n邻近的在最短路中的点nearN，然后贪心放置警察即可。

ps:实际上本题并不难，主要是赛时画的极端情况的图都是不对的..贪心放置的思路是没问题的.

int n,m,k;
int tt[100005];
char ans[100005];
vector<int> vct[100005];
vector<int> near1,nearN;
priority_queue<pair<int,int>> pq;
int dis[100005],minDis;
bool vis[100005];
void dijkstra(int s,int typ){for(int i=1;i<=n;i++) vis[i]=0,dis[i]=INT_MAX;dis[s]=tt[s];pq.emplace(0,s);while(pq.size()){int from=pq.top().second;pq.pop();if(vis[from]) continue;vis[from]=1;for(auto v:vct[from]){int to=v,w=tt[v];if(dis[to]>=dis[from]+w){   取等dis[to]=dis[from]+w;pq.emplace(-dis[to],to);if(typ==1&&to==1&&dis[to]==minDis) near1.emplace_back(from);if(typ==2&&to==n&&dis[to]==minDis) nearN.emplace_back(from);}}}
}
一开始画的极端图,都是不对的!!
权值是在 '点' 上的!  不是在 '边'上的!
实际上不难...啊?
void solve(){           Ccin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>tt[i];for(int i=1;i<=m;i++){int u,v; cin>>u>>v;vct[u].emplace_back(v);vct[v].emplace_back(u);}if(n==2&&k==1){cout<<"impossible";return;}dijkstra(1,0);minDis=dis[n];dijkstra(n,1);  得到near1dijkstra(1,2);  得到nearNint N=k,S=n-k;if(max(N,S)>=min(near1.size(),nearN.size())+1){     可以直接堵完near1或nearNif(nearN.size()<near1.size()){if(N>=S){ans[n]='N',N--;for(auto v:nearN) ans[v]='N',N--;}else{ans[n]='S',S--;for(auto v:nearN) ans[v]='S',S--;}}else{if(N>=S){ans[1]='N',N--;for(auto v:near1) ans[v]='N',N--;}else{ans[1]='S',S--;for(auto v:near1) ans[v]='S',S--;}}}else{                           否则正常贪心放置即可if(N<=S&&N!=0){ans[n]='N',N--;for(auto v:nearN) {if(N==0) break;ans[v]='N',N--;}}else{ans[n]='S',S--;for(auto v:nearN) {if(S==0) break;ans[v]='S',S--;}}}for(int i=1;i<=n;i++){if(ans[i]!='N'&&ans[i]!='S') N?ans[i]='N',N--:ans[i]='S',S--;}for(int i=1;i<=n;i++) cout<<ans[i];
}

Problem - D - Codeforces--Deceptive Directions

题意:给出一个图和一个起始点S，和一个全是指向错误方向的指向宝藏的字符串。问最终宝藏可能的位置在哪里? 宝藏距离起始点的最短路径必然为str.size().

思路:普普通通的bfs，注意路径长度即可，去除路径长度不符合的点。

typedef struct node{int x,y,step;
}node;
int n,m;
char maze[1003][1003];
int dis[1003][1003];
bool vis[1003][1003];
string str;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int sx,sy;
void bfs0(int x0,int y0){queue<pair<int,int>> que;que.emplace(x0,y0);while(que.size()){int xx0=que.front().first;int yy0=que.front().second;que.pop();for(int i=0;i<4;i++){int x=xx0+dx[i];int y=yy0+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&maze[x][y]!='#'){que.emplace(x,y);dis[x][y]=dis[xx0][yy0]+1;vis[x][y]=1;}}}
}
void bfs(int x0,int y0){for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) vis[i][j]=0;queue<node> que;que.emplace(node{x0,y0,0});while(que.size()){int xx0=que.front().x;int yy0=que.front().y;int step=que.front().step;que.pop();if(step==str.size()-1){maze[xx0][yy0]='!';continue;}for(int i=0;i<4;i++){int x=xx0+dx[i];int y=yy0+dy[i];int way=-1;if(str[step+1]=='N') way=0;else if(str[step+1]=='S') way=1;else if(str[step+1]=='W') way=2;else if(str[step+1]=='E') way=3;if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&maze[x][y]!='#'&&way!=i){que.emplace(node{x,y,step+1});vis[x][y]=1;}}}
}
void solve(){           D  bfscin>>m>>n;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>maze[i][j];if(maze[i][j]=='S') sx=i,sy=j,vis[i][j]=1;}}cin>>str;str=" "+str;bfs0(sx,sy);bfs(sx,sy);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){这些指令直接通向宝藏(但可能需要绕过障碍物)，也就是说，没有更短的到达宝藏的途径。!!注意这句话即可!!.刚好走了str.size()-1步,不一定是到达那个点最短的步数!!if(maze[i][j]=='!'&&dis[i][j]<str.size()-1) maze[i][j]='.';cout<<maze[i][j];}cout<<endl;}
}

Problem - G - Codeforces--Grazed Grains

题意:给出n个圆的圆心坐标和圆的半径，求他们覆盖的面积。输出和答案误差在10％即可.n<=10,xi,yi<=10,r<=10.

思路:因为数据范围很小，直接枚举像素点，判断像素点是否在某个圆中即可。但是直接枚举的话误差会非常大。那么需要把整个图放大，再枚举像素点。队友的代码:

ll n;
int x[11],y[11],r[11];
const int p=50;
void solve(){cin >> n;for(int i=1;i<=n;i++){cin >> x[i] >> y[i] >> r[i];x[i]*=p,y[i]*=p,r[i]*=p;}double ans=0;for(int i=-10*p;i<=20*p;i++){for(int j=-10*p;j<=20*p;j++){for(int k=1;k<=n;k++){ll dis=(i-x[k])*(i-x[k])+(j-y[k])*(j-y[k]);if(dis<=r[k]*r[k]){ans++; break;}}}}cout << ans/p/p;
}

Problem - A - Codeforces--Antenna Analysis

思路:把式子去掉绝对值可以发现，组成式子的值都是定值，可以提前算出来，计算的时候去max即可.

int n,c;
int arr1[400005];
int arr2[400005];
void solve(){       Acin>>n>>c;for(int i=1;i<=n;i++){int x; cin>>x;arr1[i]=x-c*i;arr2[i]=-(x+c*i);}priority_queue<int> pq1,pq2;for(int i=1;i<=n;i++){pq1.emplace(-arr1[i]);pq2.emplace(-arr2[i]);cout<<max(arr1[i]+pq1.top(),arr2[i]+pq2.top())<<" ";}
}

这篇关于Nordic Collegiate Programming ContestNCPC 2021的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---