P10368 「LAOI-4」Colors

· · 题解

P10368 「LAOI-4」Colors 题解

更新于 2024 年 4 月 29 日：修改了题目的证明，感谢 WhisperingWillow 的指正。

题目链接

题目大意

给定一个字符串 s，求出其按照题目变换方式变换后的字符串。

题目分析

不加证明的给出一个结论：

对于每个字符串 s，最多只能进行两次变换。

这是为什么呢？从变换方式的角度入手，对于每次变换，我们都会把形如 aba 的子串进行操作。这会导致其变为 aa 的样子。此时就有两种情况：

  1. 左边的若干个字符与这两个字符不相同，拼到一起后记为 aabbcc，它显然不满足题目的性质，不可继续消除；

  2. 左边的若干个字符与这两个字符相同，拼到一起后就为 aaaaaaa，它虽然满足消除条件，但只需要一次就可以将其消除到最短的 aa，所以只能再多消除一次。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long t, id, n, k;
string s1, s2;
//s1储存给定的字符串, s2储存删除后的字符串
int main() {
    cin >> t >> id;
    while (t--) {
        cin >> n >> k;
        cin >> s1;
        if (k == 0 || n < 3) {
            cout << s1 << endl;
            continue;
        }
        //不用操作或者长度不够不能操作
        if (k > 2) k = 2;
        //最多只能操作两次
        s2 = s1[0];
        //由于给定的字符串开头的左边没有字符,所以开头一定不会被删除
        for (int i = 0; i <= n - 2; i++) {
            if (s1[i] != s1[i + 2]) s2 += s1[i + 1];
            //左右不相同,不会删除
        }
        s1 = s2, s2 = "";
        if (k == 1) {
            cout << s1 << endl;
            continue;
        }
        s2 = s1[0];
        n = s1.length();
        if (n < 3) {
            cout << s1 << endl;
            continue;
        }
        for (int i = 0; i <= n - 2; i++) {
            if (s1[i] != s1[i + 2]) s2 += s1[i + 1];
            //左右不相同,不会删除
        }
        //再操作一遍
        s1 = s2, s2 = "";
        cout << s1 << endl;
        s1 = "";
    }
    return 0;
}