【题解】CF1606A AB Balance

ExplodingKonjac · 2021-10-30 09:47:16 · 题解

【原题链接】

一道 nt 题居然想了我十几分钟

题目分析

不难发现，只有在连续的 a 和 b 之间才会产生 ab 或 ba。

下文中用 (a) 表示连续的 a，(b) 表示连续的 b。

由于字符串一定是类似于 (a)(b)(a)... 的样子，所以 \mathrm{AB}(s) 与 \mathrm{BA}(s) 一定是相等或者只相差 1。

考虑一下 \mathrm{AB}(s)>\mathrm{BA}(s) 的情况：

• 首先我们可以发现字符串一定是形如 (a)(b)(a)(b)...(a)(b) 的；

  • 当最后面只有一个 b 时，即 ...(a)b 的样子，我们把最后一个 b 改为 a，于是 \mathrm{AB}(s) 少了 1，而 \mathrm{BA}(s) 不变，所以做完了。
  • 当最后面不止一个 b 时，即 ...(a)(b) 的样子，我们把最后一个 b 改为 a，于是 \mathrm{AB}(s) 不变，而 \mathrm{BA}(s) 多了 1，所以也做完了。

• 所以得到了一个优美的结论：把最后一个元素改为 a 即可。

当 \mathrm{BA}(s)>\mathrm{AB}(s) 时也是类似的。

代码实现

#include <bits/stdc++.h>
using namespace std;

/*
省略快读快写模板
*/

int T,n,ab,ba;
char s[105];
int main()
{
    qin>>T;
    while(T--)
    {
        qin>>s+1,n=strlen(s+1);
        ab=ba=0;
        for(int i=1;i<n;i++)
        {
            if(s[i]=='a' && s[i+1]=='b')    ab++;
            if(s[i]=='b' && s[i+1]=='a')    ba++;
        }
        if(ab>ba)   s[n]='a';
        if(ab<ba)   s[n]='b';
        qout.writeln(s+1);
    }
//  return qout.flush(),0;
}