Lotuses's Blog

CF1654B Solution

  • 508 字
  1. 1. Solution

Solution

初看这道题，诶，有点难度，果然是 Div.1 + Div.2 的难度啊，AC 自动机？

啊不不不，完全可以不用 AC 自动机。

可以发现，只需要查找第一个字母是否出现在后面即可。

设字符串为 。

如果 在后面出现过，那么发现 实际上也会在后面出现。

实际上 也都出现。（虽然都是废话）

所以只需要依次删除字符串的第一个字符，只要在后面找到，就说明这个字符必定是在当前最长前缀里头的，且之后的字符都可以依次删除。

那么，

时 ，空 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
string ac;

int main()
{
    int t,p;
    cin>>t;
    while(t--)
    {
        cin>>ac;
        while((p=ac.find(ac[0],1))!=ac.npos) ac=ac.substr(1);
        cout<<ac<<endl;
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可