首页 > 代码库 > UVALive 2889(回文数字)
UVALive 2889(回文数字)
题意:给定i,输出第i个回文数字。
分析:1,2,3,4,……,9------------------------------------------------------------------------------------------9个
11,12,13,14,……,19-------------------------------------------------------------------------------------9个
101,111,121,131,141,151,161,171,181,191,202,212,222,232,……,979,989,999-------------------------------90个
1001,1111,1221,1331,1441,……,9889,9999----------------------------------------------------------------90个
10001,10101,10201,10301,……,99899,99999--------------------------------------------------------------900个
规律是把回文串一分为二看,例如第四行,前两个数字是从10到99,共90个数字。而第三行也是从10到99,区别在于,需要去掉最后一位再反转,才是另一半(后两个数字)。
思路:先确定i所对应的回文数字的位数,再确定具体值。
1 #include<cstdio> 2 #include<cstring> 3 #include<cctype> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 #include<sstream> 8 #include<iterator> 9 #include<algorithm>10 #include<string>11 #include<vector>12 #include<set>13 #include<map>14 #include<deque>15 #include<queue>16 #include<stack>17 #include<list>18 #define fin freopen("in.txt", "r", stdin)19 #define fout freopen("out.txt", "w", stdout)20 #define pr(x) cout << #x << " : " << x << " "21 #define prln(x) cout << #x << " : " << x << endl22 typedef long long ll;23 typedef unsigned long long llu;24 const int INT_INF = 0x3f3f3f3f;25 const int INT_M_INF = 0x7f7f7f7f;26 const ll LL_INF = 0x3f3f3f3f3f3f3f3f;27 const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;28 const double pi = acos(-1.0);29 const double EPS = 1e-6;30 const int dx[] = {0, 0, -1, 1};31 const int dy[] = {-1, 1, 0, 0};32 const ll MOD = 1e9 + 7;33 const int MAXN = 1000000 + 10;34 const int MAXT = 10000 + 10;35 using namespace std;36 ll a[25];37 void init()38 {39 ll tmp = ll(9);40 for(int i = 1; i < 20; i += 2)41 {42 a[i] = a[i - 1] = tmp;43 tmp *= ll(10);44 }45 }46 ll POW(ll x)47 {48 ll w = 1;49 for(ll i = 1; i <= x; ++i)50 w *= ll(10);51 return w;52 }53 int main()54 {55 init();56 int n;57 while(scanf("%d", &n) == 1 && n)58 {59 int cnt = 0;60 while(n > a[cnt])61 {62 n -= a[cnt];63 ++cnt;64 }65 if(cnt == 0)66 {67 printf("%d\n", n);68 continue;69 }70 else if(cnt == 1)71 {72 printf("%d%d\n", n, n);73 continue;74 }75 else76 {77 int tmp = cnt / 2;78 char str[50];79 memset(str, 0, sizeof str);80 ll ans = POW(ll(cnt / 2)) + ll(n - 1);81 sprintf(str, "%lld", ans);//把数字变为指定格式的字符串82 printf("%s", str);83 string s = string(str);84 int len = s.size();85 if(cnt % 2 == 0) s.resize(len - 1);86 reverse(s.begin(), s.end());87 printf("%s\n", s.c_str());88 }89 }90 return 0;91 }
UVALive 2889(回文数字)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。