POJ2402/UVA 12050 Palindrome Numbers 数学思维

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A palindrome is a word, number, or phrase that reads the same forwards as backwards. For example,
the name “anna” is a palindrome. Numbers can also be palindromes (e.g. 151 or 753357). Additionally
numbers can of course be ordered in size. The ﬁrst few palindrome numbers are: 1, 2, 3, 4, 5, 6, 7, 8,
9, 11, 22, 33, ...
The number 10 is not a palindrome (even though you could write it as 010) but a zero as leading
digit is not allowed.
Input
The input consists of a series of lines with each line containing one integer value i (1 ≤ i ≤ 2 ∗ 109
).
This integer value i indicates the index of the palindrome number that is to be written to the output,
where index 1 stands for the ﬁrst palindrome number (1), index 2 stands for the second palindrome
number (2) and so on. The input is terminated by a line containing ‘0’.
Output
For each line of input (except the last one) exactly one line of output containing a single (decimal)
integer value is to be produced. For each input value i the i-th palindrome number is to be written to
the output.
Sample Input
1
12
24
0
Sample Output
1
33
151

题意：给出i，输出第i个回文数，不能有前导0.

题解：第一和最后一位不为0，

我们预处理i位数有多少，以及在不是第一位和最后一位情况下i位有多少情况

再不断细分就好了

//meek///#include<bits/stdc++.h>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include<iostream>

#include<bitset>

#include<vector>

#include <queue>

#include <map>

#include <set>

#include <stack>

using namespace std ;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

#define MP make_pair

typedef long long ll;

const int N = ;

const int M = ;

const int inf = 0x3f3f3f3f;

const int MOD = ;

const double eps = 0.000001;

ll a[N],sum[N],b[N],s;

void init() {s=;

   a[] = ;b[] = ;

   a[] = ;b[] = ;

   for(int i=;i<=;i++) {

    a[i] = a[i-] * ;

   }s=;

   for(int i=;i<=;i++) {

    b[i] = *a[i-];

    s+=b[i];

   // cout<<s<<endl;

   }

}

int main() {

    init();

    ll n, num, ans[N];

    while(scanf("%lld",&n)!=EOF) {

        if(!n) break;

        mem(ans);

        int l,r,mm;

        for(int i=;i<=;i++) {

            if(b[i]>=n) {

                num = i;

                mm = num;

                l = , r = num;

                while(l<=r) {

                    if(num == ) {

                        if(l!=) n--;

                        ans[l] = n;

                        ans[r] = n;break;

                    }

                    if(num == ) {

                        if(l!=)n--;

                        ans[l] = n;

                        ans[r] = n;break;

                    }

                    ans[l] = n/a[num-] + (l == ?:);

                    n = n%a[num-];

                    if(n ==  && num-!=) {

                        ans[l]--;

                        n = a[num-];

                    }

                    ans[r] = ans[l];

                    l++,r--;num-=;

                }

                break;

            }

            n -= b[i];

        }

        for(int i=;i<=mm;i++) printf("%lld",ans[i]);

        printf("\n");

    }

    return ;

}