Submission #950465

#	Time	Username	Problem	Language	Result	Execution time	Memory
950465		phoenix0423	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	600 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long 
const int maxn = 1e5 + 5;

int sol(int x){
    if(x < 0) return 0;
    string s = to_string(x);
    vector<vector<vector<int>>> dp(11, vector<vector<int>>(11, vector<int>(2)));
    dp[10][10][1] = 1;
    int n = s.size();
    for(int i = 0; i < n; i++){
        vector<vector<vector<int>>> ndp(11, vector<vector<int>>(11, vector<int>(2)));
        for(int a = 0; a <= 10; a++){
            for(int b = 0; b <= 10; b++){
                for(int c = 0; c < 10; c++){
                    if(a == c || b == c) continue;
                    if(a == 10 && b == 10 && c == 0) continue;
                    if(c < s[i] - '0'){
                        ndp[b][c][0] += dp[a][b][0] + dp[a][b][1];
                    }
                    else if(c == s[i] - '0'){
                        ndp[b][c][0] += dp[a][b][0], ndp[b][c][1] += dp[a][b][1];
                    }
                    else{
                        ndp[b][c][0] += dp[a][b][0];
                    }
                }
            }
        }
        ndp[10][10][0] = 1;
        swap(dp, ndp);
    }
    int ret = 0;
    for(int i = 0; i <= 10; i++){
        for(int j = 0; j < 10; j++){
            for(int k = 0; k < 2; k++) ret += dp[i][j][k];
        }
    }
    return ret + 1;
}
signed main(void){
    int a, b;
    cin>>a>>b;
    cout<<sol(b) - sol(a - 1)<<"\n";
}

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