Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/contest/625/problem/D 题意：问能否找到一个s,满足s+s的反转=k 思路：如果是回文数。。。那么显然满足。除以2就可以得到答案。
1 如果不是回文数。。那么考虑进位的情况。
2 要么从后一位进1，要么从前一位退10回来。
3 需要特殊考虑1开头的。
4
5
6
7/* ***********************************************
8Author :111qqz
9Created Time :2016年02月07日 星期日 18时28分39秒
10File Name :code/cf/#342/D.cpp
11************************************************ */
12
13#include <cstdio>
14#include <cstring>
15#include <iostream>
16#include <algorithm>
17#include <vector>
18#include <queue>
19#include <set>
20#include <map>
21#include <string>
22#include <cmath>
23#include <cstdlib>
24#include <ctime>
25#include <sstream>
26#define fst first
27#define sec second
28#define lson l,m,rt<<1
29#define rson m+1,r,rt<<1|1
30#define ms(a,x) memset(a,x,sizeof(a))
31typedef long long LL;
32#define pi pair < int ,int >
33#define MP make_pair
34
35using namespace std;
36const double eps = 1E-8;
37const int dx4[4]={1,0,0,-1};
38const int dy4[4]={0,-1,1,0};
39const int inf = 0x3f3f3f3f;
40const int N=1E5+7;
41bool vis[N];
42
43void pre()
44{
45 ms(vis,false);
46 for ( int i = 10 ; i <12000 ; i++)
47 {
48 int vala = i ;
49 stringstream ss;
50 ss<<vala;
51 string tmp = ss.str();
52
53 reverse(tmp.begin(),tmp.end());
54
55 int valb;
56 sscanf(tmp.c_str(),"%d",&valb);
57// cout<<i<<" "<<vala+valb<<endl;
58 if (vala+valb<N) vis[vala+valb] = true;
59
60 }
61
62 for ( int i = 1 ; i < N ; i++)
63 {
64 if (vis[i]) cout<<i<<endl;
65 }
66}
67char ans[N],s[N];
68int n;
69int sum[N];
70
71bool ok()
72{
73 // cout<<"n:"<<n<<endl;
74 for ( int i = 0 ; i < n/2 ;)
75 {
76 int l = i ;
77 int r = n-1-i;
78 if (sum[l]==sum[r]) i++;
79 else if (sum[l]==sum[r]+1||sum[l]==sum[r]+11)
80 {
81 sum[l]--;
82 sum[l+1]+=10;
83 }
84 else if (sum[l]==sum[r]+10)
85 {
86 sum[r-1]--;
87 sum[r]+=10;
88
89 }
90 else return false;
91 }
92
93 if (n%2==1)
94 {
95 if (sum[n/2]%2==1) return false;
96 if (sum[n/2]>18||sum[n/2]<0) return false;
97 ans[n/2] = char(sum[n/2]/2 +'0');
98// cout<<"ASDHJKASD"<<endl;
99 }
100 for ( int i = 0 ; i < n/2 ; i++)
101 {
102 if (sum[i]<0||sum[i]>18) return false;
103 ans[i] =(sum[i]+1)/2+'0';
104 ans[n-1-i] =sum[i]/2+'0';
105 }
106 return ans[0]>'0';
107}
108int main()
109{
110 #ifndef ONLINE_JUDGE
111 freopen("code/in.txt","r",stdin);
112 #endif
113
114 //pre();
115 //
116
117 scanf("%s",s);
118 n = strlen(s);
119 for ( int i = 0 ; i < n ; i++) sum[i] = s[i] - '0';
120 if (ok())
121 {
122 cout<<ans<<endl;
123// cout<<"aaa"<<endl;
124 return 0;
125 }
126
127 if (s[0]=='1'&&n>1)
128 {
129 for ( int i = 0 ; i < n ; i++)
130 sum[i] = s[i+1]-'0';
131 sum[0]+=10;
132 n--;
133 if (ok())
134 {
135 cout<<ans<<endl;
136 return 0;
137 }
138 else
139 puts("0");
140 }
141 else puts("0");
142
143
144 #ifndef ONLINE_JUDGE
145 fclose(stdin);
146 #endif
147 return 0;
148}