江西师范大学素拓网,停车遭村委会锁车,xcanvas
有一个长度为\(n\)个点连成的环。每个环为黑色或白色。当一个点和与他相邻的两个点颜色不同时。该点的颜色就会改变。
问改变\(k\)次后每个点的颜色。
发现两个性质:
1.发现如果一个点在第一次时就不需要改变。那么他以后都不需要改变。
2.如果有个点在某次不需要改变,那么下一次他相邻的两个点也一定不需要改变。
所有思路就很明显了。从不需要改变的点开始\(bfs\)。得到每个点最早不需要改变的时间。然后与\(k\)取\(min\)后计算出最终颜色就行了。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstdlib> #include<queue> #include<cstring> #include<vector> using namespace std; typedef long long ll; const int n = 200010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1;c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0';c = getchar(); } return x * f; } char s[n]; int vis[n]; queue<int>q; int main() { int n = read(),k = read(); scanf("%s",s); memset(vis,-1,sizeof(vis)); for(int i = 0;i < n;++i) { if(s[i] != s[(i - 1 + n) % n] && s[i] != s[(i + 1) % n]); else { q.push(i),vis[i] = 0; } } while(!q.empty()) { int u = q.front();q.pop(); if(vis[(u - 1 + n) % n] == -1) { vis[(u - 1 + n) % n] = vis[u] + 1;q.push((u - 1 + n) % n); } if(vis[(u + 1) % n] == -1) { vis[(u + 1) % n] = vis[u] + 1;q.push((u + 1) % n); } } for(int i = 0;i < n;++i) { if(vis[i] == -1 || vis[i] > k) { if(k & 1) putchar(s[i] == 'b' ? 'w' : 'b'); else putchar(s[i]); } else { if(vis[i] & 1) putchar(s[i] == 'b' ? 'w' : 'b'); else putchar(s[i]); } } return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论