Codeforces Round #802 (Div. 2) B Palindromic Numbers

Problem - B - Codeforces

题意：

给你一个数，让你构造出一个位数相同的数，使得两个数相加是个回文数

思路：

鉴定为构造题

对于构造题，我们去确定构造的主体和构造主体的条件

主体是构造一个数

条件是：

１.位数与原数相同

２.和原数相加是回文数

接下来就要把构造条件简化，找出满足构造条件的特例，或者找规律

首先是位数要与原数相同

转化一下条件就是回文数满足一定的范围

然后是相加之后是回文数

回文数最简单的情况就是每一位都相同

以四位数为例

如果我们构造相加之后的数为１１１１１，其中位数为原数位数＋１

但是对于１０００来说，要加五位数才能到１１１１１

因此定一个更近一点的回文数：９９９９

分类讨论即可

最高位是９的回文数是１１１１１

最高位是１的回文数是９９９９

这里的数可能会很大，因此使用了高精度，顺便整理了一下高精度板子

Code：

#include 
using namespace std;
const int mxn=1e6+10;
vector<int> A,B;
int n;
char s[mxn];
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for(int i = 0 ; i < A.size() ; i ++ )
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }
    
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
void solve(){
    A.clear();B.clear();
    scanf("%d%s",&n,s);
    for(int i=n-1;i>=0;i--){
        A.push_back(s[i]-'0');
    }
    if(A[n-1]==9){
        for(int i=1;i<=n+1;i++) B.push_back(1);
    }else{
        for(int i=1;i<=n;i++) B.push_back(9);
    }
    auto C=sub(B,A);
    for(int i=n-1;i>=0;i--) printf("%d",C[i]);
    printf("\n");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

总结：

对于构造题，我们去确定构造的主体和构造主体的条件

主体是构造一个数

条件是：

１.位数与原数相同

２.和原数相加是回文数

接下来就要把构造条件简化，找出满足构造条件的特例，或者找规律