codeforces 726 E2

题目
题意: 给定长度为n的字符串s，有两种操作: 删除字符串的最后一个字符；复制字符串。通过两种操作使字符串长度变为k，并且是字典序最小的。
思路: 假设历史最优的前缀长度是p，那么对于某个位置i。
s[i] > s[i%p]，寄，没法比取前p个字符更优了。
s[i] == s[i%p]，和历史最优p一样，不用管，因为不知道s[i+1]和s[(i+1)%p]的关系
s[i] < s[i%p]，把s[i]加入到队伍会更优。
比如dbcab，遍历到b
dbcadbca
dbcab
不用看后边的，把b加入队伍显然更优越。
代码:

#include
using namespace std;
const int N = 5e5+10;
int n,m,k,T;
void solve()
{
	cin>>n>>k;
	string s; cin>>s;
	int now = 1;
	for(int i=0;i<n;++i)
	{
		if(s[i]>s[i%now]) break;
		if(s[i]<s[i%now]) now = i+1;
	}
	for(int i=0;i<k;++i)
	{
		cout<<s[i%now];
	}
}
signed main(void)
{
	solve();
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24