题目链接：http://codeforces.com/contest/625/problem/D
题意： 给你一个数字字符串s，长度1e6，算是一个大数吧，让你找到一个x，使得，x加上 逆转（x）=s
例如33，能找到 12，逆转（12）=21
12+21=33
输出的x不允许有前导零，例如输出 032是错的，只能输出32，如果输出320，她的逆转是023，他们的和是320+23
其实，X和逆转X就是一对回文串
这个题细节很多，坑点也很多。参考了大神的题解，下面的解释来自大神的博客。写得太好啦。ORZ。http://blog.csdn.net/viphong/article/details/50668657
总得来说，我们就是要把长度为n位的一个串拆成两个长度n位的回文串
我们要尽可能让 S 的第i位和第n-1-i位相同，只有这两位相同，才可能分解出两个一样的数字构成回文串
我们令l=头，r=尾
逐个比较， 如果 s[l]==s[r] ，则l,r向中间移动一格，
否则，我们看能否通过进位使得他们相等， 对于l，它左边是已经确定的，就别动了，只考虑l的往右退位，
同样，对于r，它的右边是确定的，只考虑r-1位的退位
也就是三种情况：
1、 左边l退位， if ( s[l] -1 == s[r] )
2、右边r-1退位,r增10 if (s[l] == s[r]+10 )
3、左右同时退位 if ( s[l]-1 == s[r] +10 )
如果满足哪种情况 则作相应操作，如果都不满足 则必然不可能构造出一个X
要注意的是 当r-l==1的时候， 情况1不可能成立，也就是不只左边往右退位，而右边不进位，情况3同理
判断完整个串后，还要考虑奇偶，如果是偶数长度必然没问题，如果是奇数长度，要看 最中间的那个位的数，是否为偶数，如果为奇数，则无法分解成2个回文串
至此，对于其余的位，只需要 靠左的第i位 构造为 （S【i】+1/）2，右边第n-1-i为s【i】/2
前导零的问题：
//我们求答案的过程0abc,cba0,这种情况是合法的，但是我们要输出cba0
//我们已经尽量让奇数的一边在前面了，如果得到的答案还有前导零，表明答案是，0ab0,的情况，这种情况两个数都有前导零，显然也不合法
------------以上的构造基于，长度为n位的一个串拆成两个长度n位的回文串
还有一种情况，长度为n位的穿 是由长度 n-1的回文串构造而成
如 78+87=165 ，这时我们要特判一下
即，先把 首位1，加到第二位，变成（16）（5）
然后再按照上面的方法再判断一次， 注意第一次的判断已经改变了子串的数字，需要copy一下备份
//CF 625D
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
char bas[maxn];
int num[maxn];
int ans[maxn];
int check(int *t, int len)
{
int i;
for(i = 0; i <= len/2; i++){
int l = i;
int r = len - i - 1;
if(t[l] == t[r]) continue;
else{
if(t[l]-1 == t[r] && r-l!=1){
t[l]--;
t[l+1]+=10;
}
else{
if(t[l]-1 == t[r]+10){
t[l]--;
t[l+1]+=10;
if(r-l==1) continue;
t[r]+=10;
t[r-1]--;
}
else if(t[l] == t[r]+10 && r-l!=1){
t[r]+=10;
t[r-1]--;
}
else{
return 0;
}
}
}
}
if(len&1){
if(t[len/2]&1) return 0;
if(t[len/2]<0) return 0;
if(t[len/2]>18) return 0;
ans[len/2] = t[len/2]/2;
}
for(int i = 0; i < len/2; i++){
if(t[i] > 18) return 0;
if(t[i] < 0) return 0;
ans[i] = (t[i]+1)/2;
ans[len-i-1] = t[i]/2;
}
return ans[0] > 0;
//我们求答案的过程0abc,cba0,这种情况是合法的，但是我们要输出cba0
//我们已经尽量让奇数的一bian在前面了，如果得到的答案还有前导零，表明答案是，0ab0,的情况，这种情况两个数都有前导零，显然不合法
}
int main(){
scanf("%s", bas+1);
int len = strlen(bas+1);
for(int i = 1; i <= len; i++) num[i] = bas[i] - '0';
int flag = 0;
if(check(num+1, len)){
flag = 1;
for(int i = 0; i < len; i++) printf("%d", ans[i]);
printf("
");
}
else{
for(int i = 1; i <= len; i++) num[i] = bas[i] - '0';
if(num[1] == 1){
num[2] += 10;
if(check(num+2, len-1)){
flag = 1;
}
if(flag){
for(int i = 0; i < len - 1; i++){
printf("%d", ans[i]);
}
printf("
");
}
else{
printf("0
");
}
}
else{
printf("0
");
}
}
return 0;
}