codeforces1025C.Plasticinezebra(字符串翻转)

题目&＃xff1a;http://codeforces.com/contest/1025/problem/C

题意&＃xff1a;有一含&＃39;b&＃39;,&＃39;w&＃39;的字符串s&＃xff0c;现要求对他进行切割&＃xff0c;并同时翻转前后两部分&＃xff0c;操作次数不限。如"bwbbw"&＃xff0c;切割&＃xff1a;"bw|bbw" &＃xff0c;翻转后&＃xff1a;&＃39;&＃39;wbwbb” 。求经过若干次操作后可以使其子序列b w 相邻得间隔着的最长的长度。

思路&＃xff1a;切割并前后同时翻转的操作即原字符串的首尾相接&＃xff0c;中间切割处产生一头一尾&＃xff0c;那么该操作就等同于把后面切割的那一段移到了字符串的前面&＃xff08;画图会发现倒着读和翻转操作后的字符串顺着读是完全一样的&＃xff09;。那么将原字符串长度扩大为两倍&＃xff0c;在最后面接上原字符串&＃xff0c;遍历一遍 寻找最长bw交错子序列即可。注意最后得到的len需要和原长度n取min。

#include
#pragma GCC optimize(3)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune&＃61;native")
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mkp(a,b) make_pair(a,b)
#define PII pair
#define PLL pair
#define fi first
#define se second
#define lc (d<<1) //d*2
#define rc (d<<1|1) //d*2&＃43;1
#define eps 1e-9
#define stn(a) setprecision(a)//小数总有效位数
#define stfl setiosflags(ios::fixed)//点后位数:cout<using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI&＃61;3.1415926535897932;
const int MAXN&＃61;1e5&＃43;10;
const ll mod&＃61;1e9&＃43;7;
ll inline mpow(ll a,ll b){ll ans&＃61;1;a%&＃61;mod;while(b){if(b&1)ans&＃61;(ans*a)%mod;a&＃61;(a*a)%mod,b>>&＃61;1;}return ans;}
int inline sgn(double x){return (x>-eps)-(xpriority_queue,greater > qu; //up
priority_queue,less > qd; //dn
const int inf &＃61; 0x3f3f3f3f; //9
const ll inff &＃61; 0x3f3f3f3f3f3f3f3f; //18char s[200010];int main()
{fio;cin>>s;int n&＃61;strlen(s);int j&＃61;n;for(int i&＃61;0;i}