半个月没写题了，果然手很生，C读了假题意卡了半天，D题推表推错了演了起来，E1大水题没来得及写。
题意
给定一个长度为 $n$ 的字符串 $s(1 \le n \le 5 \cdot 10^5)$，支持如下操作：
- 删去 $s$ 结尾的一个字符。
- 将 $s$ 复制，得到一个新的字符串 $s’ = s + s$ （加意为将后一个字符串接在前一个字符串末尾）。
所有操作可以按任意顺序使用任意次。
要得到一个字典序最小的 $k(1 \le k \le 5 \cdot 10^5)$ 长字符串。
思路
我们可以发现，执行操作2之后会因为减少到长度 $k$ 执行操作1，但不会再为了减少字典序而执行操作1。所以答案必定是由某一前缀不断循环而成的。
E1即可暴力枚举每一个前缀，$O(n^2)$ 通过。
E2的话我口胡了一个假的筛法如下，甚至无法通过样例1。
问题在于会保留多余的历史最低值，放在整体来看却并不一定是最优的前缀，会导致提前跳出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| string solve(string &s,int k)
{
std::unique_ptr<int[]> vis = std::make_unique<int[]>(maxn);
unique_ptr<char[]> low (new char[maxn]);
int len=1;
for(int i=0;i<maxn;i++)
low[i]='z',vis[i]=0;
for(int i=0;i<s.length();i++)
{
fprintf(stderr,"low[%d] = %c, s[%d] = %c\n",i,low[i],i,s[i]);
if(s[i]==low[i])
continue;
else if(s[i]>low[i])
break;
else{
low[i]=s[i];
len=i+1;
for(int p=1;i*p+p-1<s.length();p++)
{
low[i*p+p-1]=min(low[i*p+p-1],s[i]);
}
}
}
fprintf(stderr,"len = %d",len);
string ans;
for(int i=0;i<k;i++)
ans+=s[i%len];
return ans;
}
|
所以我们只保留上一个最优的前缀，当每次前缀字典序变得更小了，我们才更新答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9;
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,k,len=1;
string s;
cin>>n>>k>>s;
for(int i=0;i<s.length();i++)
{
if(s[i]==s[i%len])
continue;
else if(s[i]<s[i%len])
len=i+1;
else
break;
}
for(int i=0;i<k;i++)
cout<<s[i%len];
cout<<endl;
return 0;
}
|