5. The Next Palindrome

                        

The Next Palindrome

题目：A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.
题目分析：这题与上次华中南赛区的一个题目一样，曾记得当时我一看到这样的题目就不想做，觉得很麻烦，所以马上果断地扔给zsq做，唉，这也反映出我一向的怪毛病，碰到麻烦题就不想做。这次再次做这个题目，发现只要把这个题目的思路好好的想清楚，写代码还是挺快，其实也不是很长，一交，局然神奇般的1Y
    题目思路其实很简单，首先考虑特殊情况。当k<9时，直接输出k+1;当k各位全部都是9时，如k=9999,直接输出10001。
     其它情况，我们可以肯定输出的值最多也就是全部都是9，也就是说最后一位来处理时肯定不会超过9，所以不需要处理最后一位的进位问题。
     首先按k的位数分为奇数、偶数两种情况对称处理。按照对称位置，低位服从于高位，即不管低位的值是什么，全部都改为与对称的高位的值相同。这时可能会出现数k的值会减少，这时通过中间位加1,然后处理相关进位问题即可。

//贪心+模拟
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1000010;
char k[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        gets(k);
        int len=strlen(k);
        if(len==1)
        {
            if(k[0]>='0'&&k[0]<='8')    putchar(k[0]+1);
            else    puts("11");
            continue;
        }
        int i;
        for(i=0;i<len;i++)
        {
            if(k[i]!='9')   break;
        }
        if(i>=len)
        {
            putchar('1');
            for(int i=1;i<len;i++)  putchar('0');
            puts("1");
            continue;
        }
        k[len-1]++;
        for(int i=len-1;i>=0;i--)
        {
            if(k[i]-'0'>9)  k[i]='0',k[i-1]++;
            else    break;
        }
        if(len&1)
        {//处理奇数的情况
            int mid=len/2;
            bool flag=false;//用于标记数k是否变小啦
            for(int i=len-1;i>mid;i--)
            {
                if(k[i]>k[2*mid-i])    flag=true;//数k变小
                k[i]=k[2*mid-i];
            }
            if(flag)
            {//数k比原数小，需要调整
                k[mid]++;
                int l=mid;
                while(l>=0)
                {
                    if(k[l]-'0'>9)
                    {
                        k[l]=k[2*mid-l]='0';
                        k[l-1]++,k[2*mid-(l-1)]++;
                        l--;
                    }
                    else    break;
                }
            }
            puts(k);
        }
        else
        {//处理偶数的情况
            int mid=len/2;
            bool flag=false;//用于标记数k是否变小啦
            for(int i=len-1;i>=mid;i--)
            {
                int j=2*mid-i-1;
                if(k[i]>k[j])   flag=true;//数k变小
                k[i]=k[j];
            }
            if(flag)
            {//数k比原数小，需要调整
                int i=mid,j=mid-1;
                k[i]++,k[j]++;
                while(i<len&&j>=0)
                {
                    if(k[i]-'0'>9)
                    {
                        k[i]=k[j]='0';
                        k[i+1]++,k[j-1]++;
                        i++,j--;
                    }
                    else    break;
                }
            }
            puts(k);
        }
    }
    return 0;
}