题意：n个人站成一圈，一个人如果只被一个人攻击，那么他只能回击攻击者，如果被两个人同时攻击，那么可以攻击任意一个，现在给你一个L,R组成的字符串，L表示向左边攻击，R表示向右边攻击，现在问你需要改变多少个人的朝向才能使得所有的人都可以满足上述要求。
如果所有人的初始方向不一样。对于一串全部都是R的字符串，两侧都是L。
当R的个数为1和2时不用改变初始方向。
当R的个数为3LRRRL时，我们需要改变一个，成为LRRLL。
当R的个数为4时，需要改变一次，成为LRRLRL。
当R个数为5时，需要改变一次，成为LRRLRRL。
当R的个数为6时，需要改变两次，成为LRRLRRLL
…
我们可以发现每三个R需要将第三个R变为L就可以使得这一小段满足条件，当一串全部都是L时同理可的。
如果所有人的初始方向一样。
如果长度为3时，如LLL,只需要改变一次，变成LLR。
当长度为4时，如LLLL，对于前三个，我们改变一次后可以得到LLRL,由于这是一个圈，所以LLRL相当于LLLR，还需要一次操作，变成LLRR,总次数为两次,这是我们也可以发现我们的目标是避免出现连续三个同方向的人。
当长度为5时，如LLLLL，第一次操作后：LLRLL,第二次操作后LLRLR,此时已符合条件。
当长度为6时，我们需要两次操作使得字符串变成LLRLLR。
当长度为7时，两次操作后仍然存在LLL，所以需要三次操作。。。。
【补题|Omkar and Bed Wars】规律：当所有人的初始方向一致时，ans+=len/3+(len%3==0)?0:1,当所有人的初始方向不是都相同时，ans+=len/3.
#include
#include
#includeusing namespace std;
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n,ans=0,sign=0,cnt=0;
string str;
cin >> n >> str;
str = str + str;
//cout << str;
for (int i = 0;
i < n;
i++) {//判断是否朝向都相同
if (str[i] != str[0]) {
sign = i;
break;
}
}
if (!sign) {
if (n < 3) ans = 0;
else ans = (n / 3) + ((n % 3 == 0) ? 0 : 1);
cout << ans << endl;
continue;
}
int rem = sign;
for (int i = sign;
i < sign + n;
i++) {
if (str[i] == str[rem]) cnt++;
else {
ans += cnt / 3;
cnt = 1;
rem = i;
}
}
ans += cnt / 3;
cout << ans << endl;
}
} 推荐阅读
- 每日一题|每日一题-解码（第十一届蓝桥杯）（简单思维）
- acm基础|哈希has散列-字符串hash
- 算法刷题笔记|牛客网 NC205084 牛牛爱字符串
- LeetCode|实现strStr()--KMP
- 字符串|LeetCode 28. Implement strStr()（实现子串定位）
- 动态规划|Longest Common Subsequence（入门dp题）
- 比赛&训练|Codeforces D. Omkar and Bed Wars (思维 / 构造) (Golab Round 10)
- 字符串|【codeforces 576D】LCS Again
- 字符串|【VOJ1895】 ニニスの守護 后缀数组 DP
- 数论and数学|牛客练习赛51-记录