hdu 4920 Ugly Problem [模拟+大数减法]

点击打开链接

题意：

? ? ? ? ? ? ? ?? 给你一个巨大无比的数字。

? ? ? ? ? ? ? ? 让你拆成50个以内的回文数字。

题解：

? ? ? ? ? ? ? ?长度最长1000位。?

? ? ? ? ? ? ? 成为回文很明显可以想到折半找， 如果 前半部分反转之后小于后半部分，直接可以构成一个回文，长度直接减半。

? ? ? ? ? ? ? 现在问题是不符合上面情形怎么办，

? ? ? ? ? ? ? 我的方法是构造一个最大的回文，构造方法是取每一位和他对称位的最小值，

? ? ? ? ? ? ?如： ?88886789 ?构造出 ?88766788；

? ? ? ? ? ? ?然后做差，如果后半段是0的话直接减1.

? ? ? ? ? ? ?这两步加起来约等于折半效果。

? ? ? ? ? ? 但是还有一个错误点，wa了好多发， 一度怀疑题目，，，，

? ? ? ? ? ? 这种构造方法，的原数列末尾一定不能为0！！！！！

    #include<bits/stdc++.h>
    #define ll long long

    using namespace std;
    const int maxn=1e4+10;
    string s;

    string sub(string a,string b)
    {
        string c;
        bool ok=0;
        int len1=a.length();
        int len2=b.length();
        int len=max(len1,len2);
        for(int i=len1;i<len;i++)
            a='0'+a;
        for(int i=len2;i<len;i++)
            b='0'+b;
        if(a<b)
        {
            string temp=a;
            a=b;
            b=temp;
            ok=1;
        }
        for(int i=len-1;i>=0;i--)
        {
            if(a[i]<b[i])
            {
                a[i-1]-=1;
                a[i]+=10;
            }
            char temp=a[i]-b[i]+'0';
            c=temp+c;
        }
        int pos=0;
        while(c[pos]=='0' && pos<len) pos++;
        if(pos==len) return "0";
        if(ok) return "-"+c.substr(pos);
        return c.substr(pos);
    }
    bool check(string a){
        bool f=true;
        int len=a.size();
        for(int i=0;i<=len/2;++i)
            if(a[i]!=a[len-1-i]){
                f=false;break;
            }
        return f;
    }
    int daxiao(string a,string b){
        for(int i=0;i<a.size();++i){
            if(a[i]>b[i]) return 1;
            if(a[i]<b[i]) return -1;
        }
        return 0;
    }
    string ans[100];
    int main(){
        int T,n,m,p,ca=0;
        int left,right,mid;
        scanf("%d",&T);
        while(T--){
            cin>>s;
            int ss=0;
            string s1,s2,s3,s5;
            while(1){
                //cout<<s<<endl;
                if(check(s)||s.size()==1){
                    ans[++ss]=s;
                    break;
                }
                s1.clear();s2.clear();s3.clear();
                int len=s.size(),i,q=0;

                if(len&1){
                    left=len/2-1;
                    right=len/2+1;
                    mid=len/2;
                }
                else {
                    left=len/2-1;
                    right=len/2;
                }
                for(i=0;i<=left;++i)
                    s1+=s[i];
                for(i=right;i<len;++i)
                    s2+=s[i];
                for(int i=left;i>=0;--i)
                    s3+=s1[i];
                int t=daxiao(s2,s3);
                if(t==1){
                    if(len&1) s1+=s[mid];
                    s1+=s3;
                    ans[++ss]=s1;
    //cout<<"s=="<<s<<endl;
                //cout<<"s1="<<s1<<" s2="<<s2<<" s3="<<s3<<endl;
                    s=sub(s,s1);
                }else{
                    s3.clear();
                    int f=0;
                    if(s[len-1]=='0'){
                        s3="1";
                    }
                    else if(len&1){
                        for(int i=0;i<=left;++i){
                            char c=min(s[i],s[len-i-1]);
                            if(c!='0')f=1;
                            s3+=c;
                        }//cout<<"s3="<<s3<<" f="<<f<<endl;
                        if(f){
                            s3+=s[mid];
                            for(int i=left;i>=0;--i) s3+=s3[i];
                        }else s3="1";
                    }else{
                        for(int i=0;i<=left;++i){
                            char c=min(s[i],s[len-1-i]);
                            s3+=c;
                            if(c!='0') f=1;
                        }
                        if(f)
                            for(int i=left;i>=0;--i) s3+=s3[i];
                        else s3="1";
                    }
    //                cout<<s<<" "<<s3<<endl;
                    //system("PAUSE");
                    ans[++ss]=s3;
                    s=sub(s,s3);
                }//cout<<"s="<<s<<endl;
                int qq=0,p=0;
                while(s[q]=='0') qq++;
                s5.clear();
                for(int k=qq;k<s.size();++k){
                    s5+=s[k];
                }
                s=s5;
            }
            printf("Case #%d:n%dn",++ca,ss);
            for(int i=1;i<=ss;++i)
                cout<<ans[i]<<endl;
            
        }
        return 0;
    }