CF319D题解

· · 题解

思路

不要被难度唬住了，其实就是一道小模拟。

最短的并且最左边就告诉我们可以直接去暴力找 X 而不用考虑这个不删能不能使得字符串长度更短之类的问题。

怎么模拟呢？先拿样例试一试。

abccabc

首先显然，这个 X 的长度不会大于整个字符串的一半，设现在枚举的 X 长度为 len。

然后是匹配的位置，即第一个 X 的左端点，设为 l，显然 0\le l \le x-len（其中 x 代表字符串的当前长度）。

接下来手动模拟一下样例，有 1\le len \le \lfloor \frac{x}{2} \rfloor = 3。

当 len = 1 时有 0\le l \le 6，当 l=2 时，匹配到了两个 c，删除，现在的字符串为 abcabc，同时更新 len 的范围 1\le len \le \lfloor \frac{x}{2} \rfloor = 3。

当 len = 2 时有 0\le l \le 5，没有一样的两个连着的字符串，现在的字符串仍然为 abcabc。

当 len = 3 时有 0\le l \le 4，当 l=0 时，匹配到了两个 abc，删除，现在的字符串为 abc，同时更新 len 的范围 1\le len \le \lfloor \frac{x}{2} \rfloor = 1，由于 len > 1，跳出循环。

最后的答案就为 abc，和样例输出相同。

所以按照上面的步骤模拟即可。

需要注意的是，同样长度的 X 可能不止一个，所以必须每次都要遍历整个字符串。

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int main() {
    cin>>s;//输入字符串 
    for(int len=1; (len<<1)<=s.length(); len++) {//枚举可能的X的长度，显然len最大为s的长度的一半 
        for(int l=0; l<=s.length()-len;) {//枚举X的判断起始点 
            bool flag=1;//匹配？ 
            for(int i=0; i<len; i++)if(s[i+l]!=s[i+l+len]) {flag=0,l++;break;}//不匹配，l++代表起始点向后移一位 
            if(!flag)continue;//不匹配，跳过 
            s.erase(l,len);//匹配，删除X 
        }
    }
    cout<<s;//输出处理后的字符串 
}