HDU 5920 - Ugly Problem

题意

将一个长度不超过\(1000\)的大整数拆分成不超过\(50\)个回文数之和。

思路

每次考虑从数\(a\)中拆分出一个最大的回文数\(b\)

从高位开始向中位循环，把\(b\)中对称的一对位置的数字定作数\(a\)中对应位置的数字

例如\(a=54321\)，每个对称位置取大，得到初始的\(b=54345\)

例如\(a=1716999\)，得到\(b=1716171\)

然后判断两个数的大小，如果满足\(a\leq b\)，那么\(b\)就可以作为这个回文数，同时将\(a\)减去\(b\)

如果\(a\gt b\)，那么需要从数\(b\)的中部考虑将某个数位减去\(1\)

因为数字\(a\)与\(b\)的左半部分相同，如果\(b\)在左半部分任意减去一个\(1\)（假如能减），肯定可以保证\(a\lt b\)成立

所以从中位开始向高位循环，如果当前位不为\(0\)且不是最高位（会出现前导\(0\)），则将当前位与对称的位同时减\(1\)（保证回文）；或者如果当前位是最高位，且大于\(1\)，也可以减去

例如在\(a=54321\)的情况，初步得到\(b=54345\)，发现中位\(3\ge 0\)，故最终\(b=54245\)

例如在\(a=11000\)的情况，初步得到\(b=11011\)，发现次高位\(1\ge 0\)，故最终\(b=10001\)

但如果在最高位为\(1\)，其余位均为\(0\)的情况下（即样例），那么可以发现最大的回文数为位数\(-1\)后全为\(9\)的数字

例如在\(a=10000\)的情况下，初步得到\(b=10001\)，发现没有任何一位可以被减，故最终\(b=9999\)

最后，手写下大数减法、大数判断即可。

程序

代码里将数字倒着存了，然后用了变量\(len\)来控制当前处理的数字\(a\)的位数

每次进行减法之后就更新一次\(len\)

#include<bits/stdc++.h>
using namespace std;

int a[1050],b[1050];
int len;
vector<int> v[55];

bool check() //判断a是否回文
{
    for(int i=0,j=len-1;i<=j;i++,j--)
        if(a[i]!=a[j])
            return false;
    return true;
}

bool check2() //判断a>=b
{
    for(int i=len-1;i>=0;i--)
        if(b[i]>a[i])
            return false;
        else if(b[i]<a[i])
            return true;
    return true;
}

void subtract() //将a=a-b，并更新len
{
    for(int i=0;i<len;i++)
    {
        if(a[i]<b[i])
        {
            a[i]+=10;
            a[i+1]-=1;
        }
        a[i]-=b[i];
    }
    while(len>0&&a[len-1]==0)
        len--;
}

void deal(int pos)
{
    if(check()) //如果是回文，直接结束
    {
        v[pos].clear();
        for(int i=len-1;i>=0;i--)
            v[pos].push_back(a[i]);
        len=0;
        return;
    }
    
    for(int i=0,j=len-1;i<=j;i++,j--) //初步处理出数字b
    {
        b[i]=b[j]=a[j];
    }
    
    if(check2()) //如果a>=b，直接将b作为答案并a=a-b
    {
        v[pos].clear();
        int i=len-1;
        while(i>0&&b[i]==0)
            i--;
        for(;i>=0;i--)
            v[pos].push_back(b[i]);
        subtract();
    }
    else
    {
        bool flag=false;
        for(int i=len/2,j=len/2-(len%2==0?1:0);j>=0;i++,j--)
        {
            if(b[i]>0&&j>0||b[i]>1&&j==0) //尝试做某一位的减法
            {
                b[i]--;
                if(i!=j)
                    b[j]--;
                flag=true;
                break;
            }
        }
        if(flag) //做了减法，此时可以直接a=a-b
        {
            v[pos].clear();
            int i=len-1;
            while(i>0&&b[i]==0)
                i--;
            for(;i>=0;i--)
                v[pos].push_back(b[i]);
            subtract();
        }
        else //否则，将b作为a位数-1后全为9的数
        {
            v[pos].clear();
            for(int i=0;i<len-1;i++)
                b[i]=9,v[pos].push_back(9);
            b[len-1]=0;
            subtract();
        }
    }
}

void solve(int cas)
{
    string str;
    cin>>str;
    len=str.size();
    for(int i=0;i<len;i++)
        a[i]=str[len-i-1]-‘0‘;
    
    int t=0;
    while(len>0) //如果a的长度不为0，继续处理下去
        deal(t++);
    
    cout<<t<<‘\n‘;
    for(int i=0;i<t;i++)
    {
        for(int it:v[i])
            cout<<it;
        cout<<‘\n‘;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    for(int t=1;t<=T;t++)
    {
        cout<<"Case #"<<t<<":\n";
        solve(t);
    }
    return 0;
}

2016CCPC长春站 J - Ugly Problem （构造、贪心）

原文：https://www.cnblogs.com/stelayuri/p/13932941.html