CF1606A AB Balance 题解


赛时唯一做出来的题,这题水过了其它都不会做。/ll

题意

给你一个由ab组成的字符串 \(s\),改变其中一个字符(变ab,变ba)使得其中AB子串的数量和BA子串的数量相等。

思路

看到 \(s\) 的长度不超过 \(100\),考虑大暴力。

枚举每一个字符,计算变换该字符后ABBA的个数。如果相等,输出这个变换后的字符串;反之把字符串改回原样继续枚举下一个字符。

代码

string s;
int ab,ba;
ab=ba=0;
cin>>s;
s+='L';

这一部分是输入,在字符串后面加一个L的目的是为了防止枚举最后一个字符的时候越界。当然你也可以通过改变枚举范围避免越界。

for(int i=0;i

第一次统计两种子串的个数,如果相等直接输出这个字符串,注意我们刚刚多加了一个L,要把L改成空格让评测机忽略(还不如直接加空格或者改变范围)。

for(int i=0;i

接下来枚举每一个字符,对它进行变换,每次变换之后统计ABBA的个数,相等就变L为空格输出,否则把这个字符改回原样。

AC 记录

你谷 AC 记录

CF AC 记录

相关