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(){ C
cin>>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); 得到near1
dijkstra(1,2); 得到nearN
int N=k,S=n-k;
if(max(N,S)>=min(near1.size(),nearN.size())+1){ 可以直接堵完near1或nearN
if(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 bfs
cin>>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(){ A
cin>>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())<<" ";
}
}