题目链接在这里：200202.pdf (codeforces.com)
其实思路非常好想，就是每次折半，把前一半回文到后面，这样的复杂度是log肯定可以行得通。然后如果最后剩的是10的话要特判一下
需要注意的是如果在结构体里面开很大的数组比如1e5以上的话会很有可能RE
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=1e5+5; 4 int t,ls1,ls2; 5 char s1[MAX],s2[MAX]; 6 vector <string> ans; 7 int main(){ 8 freopen ("i.in","r",stdin); 9 freopen ("i.out","w",stdout); 10 int i,j,mid; 11 scanf("%d",&t); 12 while (t--){ 13 scanf("%s",s1+1); 14 ls1=strlen(s1+1); 15 reverse(s1+1,s1+ls1+1); 16 ans.clear(); 17 while (ls1){ 18 if (ls1==2 && s1[2]=='1' && s1[1]=='0'){ 19 ans.push_back("1"); 20 ans.push_back("9"); 21 break; 22 } 23 if (ls1==1){ 24 ans.push_back(string(1,s1[1])); 25 break; 26 } 27 mid=ls1/2; 28 memset(s2,0,sizeof(s2)); 29 for (i=ls1;i>mid;i--) s2[i]=s1[i]; 30 s2[mid]--; 31 i=mid; 32 while (s2[i]<'0'){ 33 s2[i]+=10; 34 s2[i+1]--; 35 i++; 36 } 37 if (s2[ls1]=='0'){ 38 for (i=1;i<=mid;i++) s2[i]=s2[ls1-1-i+1]; 39 if (ls1%2==0) s2[mid]='9'; 40 ans.push_back(string(s2+1,s2+ls1)); 41 } 42 else{ 43 for (i=1;i<=mid;i++) s2[i]=s2[ls1-i+1]; 44 ans.push_back(string(s2+1,s2+ls1+1)); 45 } 46 for (i=1;i<=ls1;i++){ 47 s1[i]=s1[i]-(s2[i]-'0'); 48 if (s1[i]<'0'){ 49 s1[i]+=10; 50 s1[i+1]--; 51 } 52 } 53 while (s1[ls1]=='0' && ls1) ls1--; 54 } 55 printf("%d ",ans.size()); 56 for (i=0;i<ans.size();i++) 57 cout<<ans[i]<<endl; 58 } 59 return 0; 60 }