比赛&训练|Codeforces D. Omkar and Bed Wars (思维 / 构造) (Golab Round 10) 比赛&训练|字符串

传送门
【比赛&训练|Codeforces D. Omkar and Bed Wars (思维 / 构造) (Golab Round 10)】题意：现有一个一圈人在进行游戏(给出他们的初始攻击状态)，R表示向右边相邻的人进行攻击，L反之。有一游戏规则：若受到单方向攻击就必须还予攻击，若受到0或两个方向的攻击则任选一个方向攻击。现问需要改变多少次(将R取反为L，或将L取反为R)才能使这一圈人按在规则进行游戏。

文章图片

思路：

若都是单一元素，那么只需要改变n/3上取整次即可。
若出现R和L交替，则对每次连续区间改变cnt/3次即可(cnt为连续区间的长度)。

代码实现：

#include #define endl '\n' #define null NULL #define ll long long #define int long long #define pii pair #define lowbit(x) (x &(-x)) #define ls(x) x<<1 #define rs(x) (x<<1+1) #define me(ar) memset(ar, 0, sizeof ar) #define mem(ar,num) memset(ar, num, sizeof ar) #define rp(i, n) for(int i = 0, i < n; i ++) #define rep(i, a, n) for(int i = a; i <= n; i ++) #define pre(i, n, a) for(int i = n; i >= a; i --) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; using namespace std; const intinf = 0x7fffffff; const double PI = acos(-1.0); const double eps = 1e-6; const llmod = 1e9 + 7; const intN = 2e5 + 5; int t, n; signed main() { IOS; cin >> t; while(t --){ cin >> n; string s, t; cin >> s; int pos = n; for(int i = n-1; ~i; i --){ if(s[i] == s[0]){ t += s[i]; pos = i; } else break; } for(int i = 0; i < pos; i ++) t += s[i]; bool flag = 0; for(int i = 0; i < n-1; i ++) if(s[i] != s[i+1]) {flag = 1; break; } if(!flag) cout << n/3 + bool(n%3) << endl; else{ int ans = 0, cnt = 1; for(int i = 0; i < n; i ++){ if(t[i] == t[i+1]) cnt ++; else{ ans += cnt/3; cnt = 1; } } cout << ans << endl; } }return 0; }