HDU 5920

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5920

题意：给出长度为1000的10进制数n，让你用小于50个回文数来组成n。

思路：我们可以取当前串的前面一半，例如 93840 ，取938 ，然后另这串减1 ，（减1是为了对称后比原来串小）得937，然后再对称得到 93739 ，

用原串减去当前串得到一个位数减少一半的新串 111，然后再采取这样的操作，但当那个数小于20时就会进入死循环，所以当它小于20时就特判下。

我的代码在当a[1]=1时，就用n-1个9来构成一个回文串，这样可以好一点确定所选定回文串的位数。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
int a[2005],b[55][2005],p[55],c[2005];
char s[2005];
int n,k;
void fun()
{
    k++;
    if(a[1]==1)
    {
        p[k]=n-1;
        for(int i=1;i<n;i++)
            b[k][i]=9;
        for(int i=n;i>1;i--)
            a[i]-=9;
        for(int i=n;i>1;i--)
        {
            if(a[i]<0)
            {
                a[i]+=10;
                a[i-1]--;
            }
        }
        if(a[1]==0)
        {
            int y;
            for(int i=1;i<=n;i++)
            {
                if(a[i]>0)
                {
                    y=i;
                    break;
                }
            }
            for(int i=1,j=y;j<=n;i++,j++)
                a[i]=a[j];
            n=n-y+1;
        }
        return;
    }
    int v=0;
    if(n%2)
        v=1;
    int x=n/2+v;
    for(int i=1;i<x;i++)
        c[i]=a[i];
    c[x]=a[x]-1;
    if(c[x]<0)
    {
        for(int i=x;i>1;i--)
        {
            if(c[i]<0)
            {
                c[i]+=10;
                c[i-1]--;
            }
            else
                break;
        }
    }
    for(int i=x+1,j=x-v;i<=n;i++,j--)
        c[i]=c[j];
    p[k]=n;
    for(int i=1;i<=n;i++)
    {
        a[i]-=c[i];
        b[k][i]=c[i];
    }
    for(int i=n;i>1;i--)
    {
        if(a[i]<0)
        {
            a[i]+=10;
            a[i-1]--;
        }
    }
    int y;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0)
        {
            y=i;
            break;
        }
    }
    for(int i=1,j=y;j<=n;i++,j++)
        a[i]=a[j];
    n=n-y+1;
}
int main()
{
    int t,u=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        n=strlen(s);
        for(int i=0;i<n;i++)
            a[i+1]=s[i]-'0';
        k=0;
        while(1)
        {
            if(n==1)
            {
                k++;
                p[k]=1;
                b[k][1]=a[1];
                break;
            }
            if(n==2)
            {
                int sum=a[1]*10+a[2];
                if(sum<19)
                {
                    p[++k]=1;
                    b[k][1]=9;
                    p[++k]=1;
                    b[k][1]=sum-9;
                    break;
                }
                else if(sum==19)
                {
                    p[++k]=2;
                    b[k][1]=1;
                    b[k][2]=1;
                    p[++k]=1;
                    b[k][1]=8;
                    break;
                }
            }
            fun();
        }
        printf("Case #%d:
",++u);
        printf("%d
",k);
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=p[i];j++)
                 printf("%d",b[i][j]);
            printf("
");
        }
    }
}