题解 CF1268A 【Long Beautiful Integer】

## 题目大意 已知有$n$位的数$A$，和常数$k$。现在需要求出最小的数$B$，使得对于任何可能的$i$，有$B_i=B_{i+k}$，且$A\le B$。 ## 题解 很显然，$B$的这个限制条件就是把一个长度为$k$的数字重复了若干遍。 $$B=\overline{\tt{abcdabcdabc\cdots}} _ {(10)}$$ 显然，$B$的位数和$A$相同。因为如果$B$的位数小于$A$，那么$B$不可能大于$A$；我们可以构造符合条件的数字$\overline{\tt{99999\cdots}} _ {(10)}$，来保证长度为$n$位的数字符合条件。 我们要让$B$最小，最贪心的做法就是直接取$A$的前$k$位。 举个例子： $$A=\overline{1919810}_{(10)},k=3\Rightarrow B=\overline{1911911}_{(10)}$$ 但此时，我们发现$B<A$。不过我们可以使$B_k$加上$1$（同时向前进位），然后更新答案。这样可以保证在前$k$位，$B>A$，此时$B$取得最小值。 ## 参考代码 ``` #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; const int MAXN=2e5+3; int n,m; bool flg; char A[MAXN],B[MAXN]; int main(){ scanf("%d%d%s",&n,&m,A); up(0,n/m,i) memcpy(B+i*m,A,min(m,n-i*m)); up(0,n-1,i) if(A[i]!=B[i]){flg=A[i]>B[i];break;} if(flg){ ++A[m-1]; dn(m-1,1,i) if(A[i]=='9'+1) A[i]='0',++A[i-1]; up(0,n/m,i) memcpy(B+i*m,A,min(m,n-i*m)); } printf("%d\n%s\n",n,B); return 0; } ```