제출 #1262098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262098		nguyenvietanh	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	1 ms	328 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define inp(name) freopen(name, "r", stdin);
#define out(name) freopen(name, "w", stdout);
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int l, r;
int f[21][2][13][13], a[N];
int calc(int pos, int smaller, int pre1, int pre2, int ans){
    if (pos == 0){
        //cout << ans << " ";
        return 1;
    }
    if (f[pos][smaller][pre1][pre2] > -1) return f[pos][smaller][pre1][pre2];
    int cur = 9;
    if (!smaller) cur = a[pos];
    int res = 0;
    for (int i = 0; i <= cur; i ++){
        if (ans == 0 && i == 0){
            res += calc(pos - 1, smaller || (i < a[pos]), -1, -1, ans);
        }
        else{
            if (i != pre1 && i != pre2) res += calc(pos - 1, smaller || (i < a[pos]), pre2, i, ans * 10 + i);
        }
    }
    return f[pos][smaller][pre1][pre2] = res;
}
int solve(int x){
    int cur = 0;
    while (x){
        a[++cur] = x % 10; x /= 10;
    }
    memset(f, -1, sizeof(f));
    return calc(cur, 0, 11, 11, 0);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> l >> r;
    int x = solve(r), y = 0;
    //cout << solve(l - 1) << '\n';
    if (l > 0) y = solve(l - 1);
    cout << x - y;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75