Codeforces Round #619
2月 15, 2020
A. Three Strings
题意
对于每一个 \(i\)，必须交换 \(a_i,c_i\) 或者 \(b_i,c_i\) ，问最后是否有可能使得 \(a=b\) 。
分析
显然，最后要想等，对于每一位必须有 \(a_i=c_i\) 或者 \(b_i=c_i\) 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include<bits/stdc++.h> #define LL long long using namespace std; #define inf 0x3fffffff int T,n; char a[110],b[110],c[110]; bool check() { for (int i=1;i<=n;i++) if (a[i]==c[i]||b[i]==c[i]) continue; else return false; return true; } int main() { scanf("%d",&T); while(T--) { scanf("%s%s%s",a+1,b+1,c+1); n=strlen(a+1); if (check()) puts("YES");else puts("NO"); } return 0; } |
B. Motarack’s Birthday
题意
给一个数列，讲数列中所有的 \(-1\) 均替换成同一个数 \(x\) ，使得相邻数的绝对值的最大值最小。
分析
如果我们把所有的与 \(-1\) 相邻的数全部取出来。
显然，我们肯定会吧 \(x\) 设为最大和最小之间的中间数。
然后将所有的 \(-1\) 替换成 \(x\) 计算一遍相邻数的绝对值的最大值即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<bits/stdc++.h> #define LL long long using namespace std; #define inf 0x3fffffff int T,n,a[100010],b[100010]; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); int s=0; for (int i=1;i<=n;i++) if (a[i]==-1) { if (i-1>=1&&a[i-1]!=-1) b[++s]=a[i-1]; if (i+1<=n&&a[i+1]!=-1) b[++s]=a[i+1]; } sort(b+1,b+1+s); int ans=(b[1]+b[s])/2,res=0; for (int i=1;i<n;i++) { if (a[i]==-1) a[i]=ans; if (a[i+1]==-1) a[i+1]=ans; res=max(res,abs(a[i]-a[i+1])); } printf("%d %d\n",res,ans); } return 0; } |
C. Ayoub’s function
题意
将一个长度为 \(n\) 的串中的其中 \(m\) 位设为 \(1\) ，使得包含 \(1\) 的子串数量最多。
分析
要使得包含 \(1\) 的子串最多，显然就是要使得不包含 \(1\) 的最少。
不包含 \(1\) 的比较好考虑，对于 \(1\) 的位置其实是吧字符串切成了若干段，对于连续的全 \(0\) 长度为 \(l\) 的子串，显然包含 \(\frac{l(l+1)}{2}\) 个不包含 \(1\) 的子串。
那么我们要最小化这个数量，显然是要尽可能的最小化 \(l\) ，而 \(m\) 个 \(1\) 会把字符串分成 \(m+1\) 段，于是我们肯定会尽可能平均的分配这个 \(l\) .
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<bits/stdc++.h> #define LL long long using namespace std; #define inf 0x3fffffff int T; LL n,m,l,r; int main() { scanf("%d",&T); while(T--) { scanf("%lld%lld",&n,&m); LL t,ans=(n+1)*n/2LL; if ((n-m)%(m+1)==0) { t=(n-m)/(m+1); ans-=t*(t+1)/2LL*(m+1); } else { LL k=(n-m)%(m+1); t=(n-m)/(m+1)+1; ans-=t*(t+1)/2LL*k; t--; ans-=t*(t+1)/2LL*(m+1-k); } printf("%lld\n",ans); } return 0; } |
D. Time to Run
题意
相邻的各自之间有两条往返路，显然要求道路不重复的任意游走 \(k\) 步，求一个构造方案。
分析
显然，最多游走的步数就是道路的总数量。
于是考虑一种构造方案，能够不重复的经过所有的道路，这样比较小的 \(k\) 步从这里面截取前一部分即可。
构造还是比较显然的：
- 第一行一直向右走到底；
- 第一行向左回到起点；
- 然后向下一步，移到下一行；
- 向右走到底；
- 不断重复上下左，直到回到这一行的第一列；
- 重复第三步到第五步，直到处理完最后一行；
- 不断的向上走，回到第一行第一列。
不够需要注意，\(m=1\) 的情况，可能会导致循环步长 \(=0\) 的情况出现。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include<bits/stdc++.h> #define LL long long using namespace std; #define inf 0x3fffffff int n,m,k,ans; struct data { int x,len; char s[5]; }a[5010]; void walk1(int x) { if(x==0) return ; ans++;a[ans].x=x; a[ans].len=1; a[ans].s[1]='R'; } void walk2(int x) { if(x==0) return ; ans++;a[ans].x=x; a[ans].len=1; a[ans].s[1]='L'; } void walk5(int x) { if(x==0) return ; ans++;a[ans].x=x; a[ans].len=1; a[ans].s[1]='U'; } void walk3() { ans++;a[ans].x=1; a[ans].len=1; a[ans].s[1]='D'; } void walk4(int x) { if(x==0) return ; if (x/3>=1) { ans++; a[ans].x=x/3; a[ans].len=3; a[ans].s[1]='U'; a[ans].s[2]='D'; a[ans].s[3]='L'; } if (x%3==1) { ans++; a[ans].x=1; a[ans].len=1; a[ans].s[1]='U'; } else if (x%3==2) { ans++; a[ans].x=1; a[ans].len=2; a[ans].s[1]='U'; a[ans].s[2]='D'; } } void print() { printf("%d\n",ans); for (int i=1;i<=ans;i++) { printf("%d\n",a[i].x); for (int j=1;j<=a[i].len;j++) putchar(a[i].s[j]); puts(""); } } int main() { scanf("%d%d%d",&n,&m,&k); if (k>n*m*4LL-n*2-m*2) {puts("NO");return 0;} ans=0;puts("YES"); if (k<=m-1) {walk1(k);print();return 0;}else walk1(m-1),k-=m-1; if (k<=m-1) {walk2(k);print();return 0;}else walk2(m-1),k-=m-1; for (int i=2;i<=n;i++) { if (k<=1) {walk3();print();return 0;}else walk3(),k--; if (k<=m-1) {walk1(k);print();return 0;}else walk1(m-1),k-=m-1; if (k<=3*(m-1)) {walk4(k);print();return 0;}else walk4(3*(m-1)),k-=3*(m-1); } walk5(k);print(); return 0; } |
E. Nanosoft
题意
每次询问给出一个子矩阵，在子矩阵中找到最大的 \(l\) ，使得存在一个 \(2l\times 2l\) 的正方形子矩阵，满足题目要求的四个颜色分布。
分析
我们可以预处理每一个位置作为中心的时候，可以得到的最大 \(l\) 的大小。
可以通过枚举中心位置，二分 \(l\) 的大小，然后分别通过四种颜色的前缀和来得到一个子矩阵的和，判断是否可行。
之后，对于每次询问的子矩阵，我们也可以同样二分答案。
对于二分的答案，我们可以得到中心位置所在的范围，我们现在只需要直到中心位置所在的范围内是否存在 \(l\) 大于等于当前二分的答案，因为只要大于等于当前，显然我们可以选择当前的 \(l\) 。
而对于一个子矩阵中最大值的维护，我们用二维 ST 表即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<bits/stdc++.h> #define LL long long using namespace std; #define inf 0x3fffffff int n,m,Q,r[510][510],g[510][510],b[510][510],y[510][510],a[510][510]; char s[510][510]; int calcb(int i,int j,int p,int q){ if (i>=1&&i<=n&&j>=1&&j<=m&&p>=1&&p<=n&&q>=1&&q<=m) return b[p][q]-b[i-1][q]-b[p][j-1]+b[i-1][j-1]; else return -1; } int calcg(int i,int j,int p,int q){ if (i>=1&&i<=n&&j>=1&&j<=m&&p>=1&&p<=n&&q>=1&&q<=m) return g[p][q]-g[i-1][q]-g[p][j-1]+g[i-1][j-1]; else return -1; } int calcy(int i,int j,int p,int q){ if (i>=1&&i<=n&&j>=1&&j<=m&&p>=1&&p<=n&&q>=1&&q<=m) return y[p][q]-y[i-1][q]-y[p][j-1]+y[i-1][j-1]; else return -1; } int calcr(int i,int j,int p,int q){ if (i>=1&&i<=n&&j>=1&&j<=m&&p>=1&&p<=n&&q>=1&&q<=m) return r[p][q]-r[i-1][q]-r[p][j-1]+r[i-1][j-1]; else return -1; } int f[1010][1010][10][10]; inline int highbit(int x) { return 31 - __builtin_clz(x); } inline int calc(int x, int y, int xx, int yy, int p, int q) { return max( max(f[x][y][p][q], f[xx - (1 << p) + 1][yy - (1 << q) + 1][p][q]), max(f[xx - (1 << p) + 1][y][p][q], f[x][yy - (1 << q) + 1][p][q]) ); } void init() { for (int x=0;x<highbit(n) + 1;x++) for (int y=0;y<highbit(m) + 1;y++) for (int i=0;i<n - (1 << x) + 1;i++) for (int j=0;j<m - (1 << y) + 1;j++){ if (!x && !y) { f[i][j][x][y] = a[i][j]; continue; } f[i][j][x][y] = calc( i, j, i + (1 << x) - 1, j + (1 << y) - 1, max(x - 1, 0), max(y - 1, 0) ); } } inline int get_max(int x, int y, int xx, int yy) { return calc(x, y, xx, yy, highbit(xx - x + 1), highbit(yy - y + 1)); } bool check(int x,int y,int z) { if (calcr(x-z+1,y-z+1,x,y)!=z*z) return false; if (calcg(x-z+1,y+1,x,y+1+z-1)!=z*z) return false; if (calcy(x+1,y-z+1,x+1+z-1,y-z+1+z-1)!=z*z) return false; if (calcb(x+1,y+1,x+1+z-1,y+1+z-1)!=z*z) return false; return true; } int main() { scanf("%d%d%d",&n,&m,&Q); for (int i=1;i<=n;i++) scanf("%s",s[i]+1); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (s[i][j]=='R') r[i][j]=1; if (s[i][j]=='G') g[i][j]=1; if (s[i][j]=='Y') y[i][j]=1; if (s[i][j]=='B') b[i][j]=1; r[i][j]+=r[i-1][j]+r[i][j-1]-r[i-1][j-1]; b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; y[i][j]+=y[i-1][j]+y[i][j-1]-y[i-1][j-1]; g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { int l=1,r=max(n,m),res=0,mid; while(l<=r) { mid=l+r>>1; if (check(i,j,mid)) res=mid,l=mid+1; else r=mid-1; } a[i][j]=res; } init(); int x,y,p,q; while(Q--) { scanf("%d%d%d%d",&x,&y,&p,&q); int l=1,r=min(p-x+1/2,q-y+1/2),mid,res=0; while(l<=r) { mid=l+r>>1; int a=x+mid-1,b=y+mid-1; int c=p-mid,d=q-mid; //cout<<mid<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<get_max(a,b,c,d)<<endl; if (a>c||b>d||get_max(a,b,c,d)<mid) r=mid-1; else res=mid,l=mid+1; } printf("%d\n",res*res*4); } return 0; } |
F. Super Jaber
题意
给一张 \(n\times m\) 的图，每个位置有一个颜色，每次询问一个位置到另一个位置的最短距离。
可以通过下面两种方式来走：
- 花费代价 \(1\) ，向四个相邻方向任意走一步；
- 花费代价 \(1\) ，移动到任意一个相同颜色的位置。
分析
我们可以考虑成，颜色是一种走路的媒介，即预处理出 \(f[i][j][c]\) 表示从位置 \((i,j)\) 出发走到颜色为 \(c\) 的位置所需要的最少步数。
考虑对于每一种颜色单独处理，从每一个位置出发可以选择走四个方向，或者移动到同颜色的位置，但是每次都考虑移动到同颜色的位置，显然时间复杂度是不能接受的。
但因为每一步的代价都相同，那么显然，移动到相同颜色的位置，在发生过一次以后，之后的都没有意义了。
所以对于每一种颜色单独考虑的时候，对于每一种颜色同颜色的移动只发生最早的一次即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<bits/stdc++.h> #define LL long long using namespace std; #define inf 0x3fffffff int n,m,k,f[1010][1010][42],a[1010][1010],v[42],g[1010][1010]; struct data { int x,y; data(int p=0,int q=0):x(p),y(q){} }; vector<data> e[42]; queue<data> q; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; void bfs(int x) { for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) g[i][j]=inf; for (auto y:e[x]) q.push(data(y.x,y.y)),g[y.x][y.y]=0; memset(v,0,sizeof(v)); while(!q.empty()) { int x=q.front().x,y=q.front().y;q.pop(); if (!v[a[x][y]]) { v[a[x][y]]=1; for (auto z:e[a[x][y]]) if (g[z.x][z.y]>g[x][y]+1) g[z.x][z.y]=g[x][y]+1,q.push(data(z.x,z.y)); } for (int i=0;i<4;i++) if (x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m) if (g[x+dx[i]][y+dy[i]]>g[x][y]+1) g[x+dx[i]][y+dy[i]]=g[x][y]+1,q.push(data(x+dx[i],y+dy[i])); } } int main() { scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&a[i][j]), e[a[i][j]].push_back(data(i,j)); for (int i=1;i<=k;i++) { bfs(i); for (int p=1;p<=n;p++) for (int q=1;q<=m;q++) f[p][q][i]=g[p][q]; } int q,u,v,x,y;scanf("%d",&q); while(q--) { scanf("%d%d%d%d",&x,&y,&u,&v); int ans=abs(x-u)+abs(y-v); for (int i=1;i<=k;i++) ans=min(ans,f[x][y][i]+f[u][v][i]+1); //cout<<i<<" "<<f[x][y][i]<<" "<<f[u][v][i]<<endl; printf("%d\n",ans); } return 0; } |
