Znzryb's Blog
0%

ABC-363-D- Palindromic Number

Posted on Edited on

AC代码

回文数生成算法

前面搞半天没过，原来是pow的问题，pow只会返回int，导致int溢出了。

自己手搓了一个lpow就过了。

主要原理是经过观察

image

那么i位回文数就有9*10**((i-1)/2)个（/2为向下取整）

然后我们要确定回文数母体，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef unsigned long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n;
vector<ll> ans;
ll lpow(int a,int b) {
    return {b==0 ? 1: lpow(a,b-1)*a};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n==1) {
        cout<<0<<endl;
        return 0;
    }
    ll cnt=0;
    n-=1;
    bool isOdd=true;
    for(int i=1;i<=n;++i) {
        cnt+=9*lpow(10,(i-1)/2);
        if(cnt>=n) {
            cnt-=9*lpow(10,(i-1)/2);
            ll ten;ten= lpow(10,(i-1)/2);
            ten-=1;
            ll remain=ten+n-cnt;
            // 把remain存入ans数组
            while (remain) {
                ans.push_back(remain%10);   // 900 存入后是 0 0 9
                remain/=10;
            }
            if(i%2==0)
                isOdd=false;
            break;
        }
    }
    if(isOdd) {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=1;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }else {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=0;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }
}
// AC https://atcoder.jp/contests/abc363/submissions/59551360

心路历程（WA，TLE，MLE……）

虽然样例吧都过不了，但我百思不解为何WA，对拍程序生成的都没WA呀。

搞半天原来是pow的问题，pow只会返回int，导致int溢出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef unsigned long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n;
vector<ll> ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n==1) {
        cout<<0<<endl;
        return 0;
    }
    ll cnt=0;
    n-=1;
    bool isOdd=true;
    for(int i=1;i<=n;++i) {
        cnt+=9*pow(10,(i-1)/2);
        if(cnt>=n) {
            cnt-=9*pow(10,(i-1)/2);
            ll ten;ten= pow(10,(i-1)/2);
            ten-=1;
            ll remain=ten+n-cnt;
            // 把remain存入ans数组
            while (remain) {
                ans.push_back(remain%10);   // 900 存入后是 0 0 9
                remain/=10;
            }
            if(i%2==0)
                isOdd=false;
            break;
        }
    }
    if(isOdd) {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=1;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }else {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=0;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }
}