codeforces #342 div 2 D. Finals in arithmetic

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}

Related