题目传送
题意:
n个人站成一圈，每个人有一个朝向（L或R）。每次操作可以改变一个人的朝向。输入每个人初始的朝向，输出至少经过多少次操作。使得一个人只被一个人攻击时，这个人与攻击他的人必须相互攻击，当一个人被俩个人同时攻击时，这个人可以任意攻击一个人
【codeforces|Codeforces Global Round 10 D. Omkar and Bed Wars(思维，分块)】思路:
分块思想，先把连续的朝向相同的人分成一块一块的。
如: RLLLLRRLLRLR
分成: R | LLLL | RR | LL | R | L | R
每一块的长度为len，则每一块需要改动的次数则为:len/3
但是首尾相同的时候，要合并为一块计算
还有一种情况就是，当全是R，或者全是L的时候，只要改动n/3 + (n%3>0)次，也就是这样改动: LLLLLLL -> LLRLLRR
AC代码
#include
inline int read(){char c = getchar();
int x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';
c = getchar();
}
return x*s;
}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 1e6 + 5;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const int mod = 998244353;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
typedef pair piil;
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t,n;
cin >> t;
while(t--)
{
string s;
cin >> n >> s;
int sum = 0,flag = 0,len = 1,ans = 0;
//ans记录第一块的长度
for(int i = 1;
i < n;
i++)
{
if(s[i] == s[i-1]) len++;
else
{
if(!flag) ans = len,flag = 1;
else sum += (len/3);
len = 1;
}
}
if(!flag) cout << (n/3+(n%3>0)) << endl;
else if(s[n-1] == s[0]) cout << sum+(len+ans)/3 << endl;
else cout << sum+len/3+ans/3 << endl;
}
}
推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- 分治|全排列算法整理
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- 数论|hdu 5322 Hope（分治+NTT）
- 题库-CF|【Codeforces Round 370 (Div 2) E】【线段树 等比数列 区间合并】Memory and Casinos 赌场区间[l,r] l进r先出的概率