1 条题解
-
0
在一个起床战争局面中，有 支队伍形成环状，第 支在第 队伍左边， 在 左边。用一个长度为 的由
L、R组成的字符串给出每支队伍在攻击它的左边还是右边。合法攻击满足以下条件：-
若只有 攻击 ， 必须攻击 ；
-
若没有或有两支队伍攻击 ， 可以随意攻击左或右。
求最少改变多少个队伍的攻击状态，使序列合法。
。
唯一的不合法状态：只有 攻击 ，而 没有攻击 。转换成字符串就是
LLL和RRR。问题转换成改变多少个
L和R，使环形字符串不含LLL和RRR。扫一遍瞎搞搞即可。代码写得贼丑。
CODE
#include <bits/stdc++.h> using namespace std; #define int long long inline int read() { int x = 0, f = 0; char c = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar(); return f ? -x : x; } char s[200010]; signed main() { for (int T = read(); T --;) { int n = read(), res = 0; scanf("%s", s + 1); int st = 1, i = 0; while (s[st] == s[1]) st ++; if (st > n) { if (n == 1) puts("0"); else if (n == 2) puts("0"); else if (n == 3) puts("1"); else { res = n / 3; if (res * 3 != n) res ++; printf("%lld\n", res); } continue; } i = st; do { int j = i, nw = 1; while (s[(j == n ? 1 : j + 1)] == s[i] && (j == n ? 1 : j + 1) != st) { nw ++; j ++; if (j > n) j = 1; } res += nw / 3; i = j + 1; if (i > n) i = 1; } while (i != st); printf("%lld\n", res); } return 0; } -
- 1
