codeforces D. Omkar and Bed Wars codeforces

文章图片

题目题意： 【codeforces D. Omkar and Bed Wars】有一个游戏，把大家围成一个圈，每一个人都可以攻击相邻的人，这样会造成人受到的攻击数为 0 , 1 , 2 0,1,2 0,1,2，当只受到一个人的攻击时，此时你需要反击这个人才算合理，如果没有反击的话，你需要进行纠正，问最少需要纠正多少次。
思路：首先有两种情况：

全部都为同一个方向的(比如RRRRRR)，当我们需要最少纠正的时候，我们可以每三个纠正一次，因为可以将 R R R RRR RRR变成 R R L RRL RRL，这样收到攻击数就成了 0 , 2 , 1 0,2,1 0,2,1，符合条件，所以一次性最多能够让 3 3 3个符合条件，如果是 R R R R RRRR RRRR的时候，我们可以变成 R R L R RRLR RRLR，但是转换一下就变成了 R R R L RRRL RRRL，这样就又要三个需要转换了，所以可以得到公式 a n s = n / 3 + ( n % 3 > 0 ) ans=n/3+(n \% 3 > 0) ans=n/3+(n%3>0)。
第二个就是有不同方向的了，我们首先要将圈变成 R . . . . . L R.....L R.....L或者 L . . . . . R L.....R L.....R的形式，然后计算连续的个数 c n t cnt cnt，这里和上面不同的是，如果是如果连续的是 R R R R RRRR RRRR的时候，只需要纠正一次，因为这个肯定会符合 L R R R R ( L . . . . ) LRRRR(L....) LRRRR(L....)或者 R R R R L . . . . . RRRRL..... RRRRL.....的形式，当我们修改第三个的时候 L R R L R ( L . . . . . ) LRRLR(L.....) LRRLR(L.....)或者 R R L R L . . . . RRLRL.... RRLRL....这些都是符合条件的，所有可得 a n s + = c n t / 3 ans+=cnt/3 ans+=cnt/3。

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector veci; typedef vector vecl; typedef pair pii; typedef pair pll; template inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != '-' && (c < '0' || c > '9')) c = getchar(); sgn = (c == '-') ? -1:1; ret = (c == '-') ? 0:(c - '0'); while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return ; } inline void outi(int x) {if (x > 9) outi(x / 10); putchar(x % 10 + '0'); } inline void outl(ll x) {if (x > 9) outl(x / 10); putchar(x % 10 + '0'); } const int maxn = 2e5 + 10; char a[maxn << 1]; int main() { int t; read(t); while (t--) { int n; read(n); scanf("%s", a); int k = -1; for (int i = 0; i < n; i++) a[n + i] = a[i]; for (int i = 0; i < n; i++) { if (a[0] != a[i]) { k = i; break; } } ll ans = 0; if (k == -1) { if (n == 3) ans = 1; else if (n <= 2) ans = 0; else ans = n / 3 + (n % 3 > 0); printf("%d\n", ans); continue; } int last = k, cnt = 0; for (int i = k; i < n + k; i++) { if (a[i] == a[last]) cnt++; else { ans += cnt / 3; cnt = 1; last = i; } } ans += cnt / 3; printf("%d\n", ans); } return 0; }