Codeforces Round #802 (Div. 2) B Palindromic Numbers
Problem - B - Codeforces
题意：
给你一个数，让你构造出一个位数相同的数，使得两个数相加是个回文数
思路：
鉴定为构造题
对于构造题，我们去确定构造的主体和构造主体的条件
主体是构造一个数
条件是：
１.位数与原数相同
２.和原数相加是回文数
接下来就要把构造条件简化，找出满足构造条件的特例，或者找规律
首先是位数要与原数相同
转化一下条件就是回文数满足一定的范围
然后是相加之后是回文数
回文数最简单的情况就是每一位都相同
以四位数为例
如果我们构造相加之后的数为１１１１１，其中位数为原数位数＋１
但是对于１０００来说，要加五位数才能到１１１１１
因此定一个更近一点的回文数：９９９９
分类讨论即可
最高位是９的回文数是１１１１１
最高位是１的回文数是９９９９
这里的数可能会很大，因此使用了高精度，顺便整理了一下高精度板子
Code：
#include <bits/stdc++.h>
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;
}总结：
对于构造题，我们去确定构造的主体和构造主体的条件
主体是构造一个数
条件是：
１.位数与原数相同
２.和原数相加是回文数
接下来就要把构造条件简化，找出满足构造条件的特例，或者找规律