「CF1269C」Long Beautiful Integer

题意：给一个 $n$ 位 $10$ 进制数字串 $s$ (首位不为 $0$)，构造一个数字串 $t$ (首位不为 $0$)，使得 $t$ 串是有周期 $k$，且 $t$ 串 $\ge s$ 串，且 $t$ 串最小。

~就是正解的思路不知道为什么错第 $7$ 个点。~

首先不可能会得到比 $n$ 位还长的数字，因为没有串可以比 $999..9$ 更大。

先把数字 $s$ 的前 $k$ 位复制若干次直到长度为 $n$，然后和 $s$ 比较，假如比 $s$ 小就给这个数字 $s$ 的前 $k$ 位代表的数字 $+1$，然后再复制若干次，这次一定更大。

这个构造是最小的，因为要比 $s$ 大，所以前 $k$ 位都是至少要和 $s$ 相同，然后受限于周期性后面只能够不断重复。假如最后弄出来的不够大那么在前面的数字位 $+1$ 之后就已经从第 $k$ 位开始严格比 $s$ 大了。

重点是要注意进位的情况，即前 $k$ 位的后面一截都是 $9$。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 9223372036854775807LL
using namespace std;
const int maxn=2e5+1010;
int n,k;
char s[maxn],t[maxn];
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=k;i++)
	{
		t[i]=s[i];
		for(int j=i;j<=n;j+=k)
			t[j]=t[i];
	}
	bool flag=1;
	for(int i=1;i<=n;i++)
	{
		if(t[i]<s[i])
			flag=0;
		else if(t[i]>s[i])
			break;
	}
	if(flag)
	{
		printf("%d\n",n);
		puts(t+1);
		return 0;
	}
	for(int i=k;i>=1;i--)
	{
		t[i]++;
		if(t[i]<='9')
		{
			for(int j=i;j<=n;j+=k)
				t[j]=t[i];
			break;
		}
		else
		{
			t[i]='0';
			for(int j=i;j<=n;j+=k)
				t[j]=t[i];
		}
	}
	printf("%d\n",n);
	puts(t+1);
	return 0;
}