题意
题目链接:Problem - 1025C - Codeforces
给你一个只含有b
和w
的字符串,每次可以选择一个k(k可以等于0),以第k个后面为分界线,让前面部分和后面部分分别反转后再拼接起来。例如:bbwwb
我选取bbw|wb
变成wbb|bw
。
请问:这样经过若干次操作后,最长的bw
交替字串是多少?(可以是bwbwb...
也可以是wbwbw...
)
思路
一开始是没有的思路的,但是用手模拟几次很普通的可以发现,例如:有一个长度为8的字符串,我用数字代替字母。
[1,2,3,4,5,6,7,8]
我随意划分
[\underline{1,2,3,4,5} \ | \ \underline{6,7,8}]
变成
[\underline{5,4,3,2,1} \ | \ \underline{8,7,6}]
然后我再随意划分一个
[\underline{5,4,3} \ | \ \underline{2,1,8,7,6}]
变成
[\underline{3,4,5} \ | \ \underline{6,7,8,1,2}]
也就是
[3,4,5,6,7,8,\underline{1,2}]
可以看出我可以用若干次操作让字符串前面部分移到后面去,这样可以进行首尾相接,可以查找最长的。
我的思路:
首先对于不首尾进行拼接,先对于整个进行得到ans
,然后如果首尾不同就进行拼接:用双指针一直往内找,如果r\leq l说明整个都是,那么就是n,否则与之前不拼接的ans
取max
有一个比较好的思路就是扩展成两倍,类似于尺取法找,满足条件就退出取max然后找下一次。
代码
inline void Case_Test()
{
cin>>s;
n = s.size();
s = " "+s;
int l = 1, r = n;
int tmp = 1;
ans = 1;
for (int i=2;i<=n;i++)
{
if (s[i]!=s[i-1]) tmp++;
else tmp = 1;
ans = Max(ans,tmp);
}
if (s[l]!=s[r])
{
while (s[l+1]!=s[l]&&l+1<=n) l++;
while (s[r-1]!=s[r]&&r-1>=1) r--;
if (r>l)
cout<<Max(n-r+1+l,ans);
else
cout<<n;
}
else cout<<ans;
/*
scanf("%s", s);
int ans = 1, n = strlen(s);
int l = 0, r = 0;
while (r < n*2) {
while (r+1 < n*2 && s[(r+1)%n] != s[r%n]) r++;
ans = max(ans, r-l+1);
l = ++r;
}
printf("%d\n", min(ans, n));
*/
}
文章评论