제출 #380159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380159		nguyen31hoang08minh2003	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	2 ms	512 KiB

numbers

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <math.h>
#include <string.h>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <bitset>
#include <iterator>
#include <functional>
#include <algorithm>
#include <iomanip>
#include <map>
#include <ctime>
#define fore(i, a, b) for(ll i = (a), _b = (b); i < (_b); i++)
#define fort(i, a, b) for(ll i = (a), _b = (b); i <= (_b); i++)
#define ford(i, a, b) for(ll i = (a), _b = (b); i >= (_b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
using namespace std;

template<class A,class B> bool mini(A &a,const B b){return a > b ? (a = b, 1) : 0; }
template<class A,class B> bool maxi(A &a,const B b){return a < b ? (a = b, 1) : 0; }

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

ll n, a, b, T, dp[25][2][12][12][2],
   vis[25][2][12][12][2];
string t;

ll DP(ll i, bool f, ll x, ll y, bool st) {
    if (i >= n)
        return 1;
    #define v i][f][x][y][st
    if (vis[v] != T) {
        vis[v] = T;
        dp[v] = 0;
        const int d = f ? 9 : (t[i] - '0');
        fort(j, 0, d)
            if (!j) {
                if (st)
                    dp[v] += DP(i + 1, f || (j < d), 10, 10, true);
                else if (x != j && y != j)
                    dp[v] += DP(i + 1, f || (j < d), y, j, false);
            } else {
                if (x != j && y != j)
                    dp[v] += DP(i + 1, f || (j < d), y, j, false);
            }
    }
    return dp[v];
    #undef v
}

ll calc(ll x) {
    stringstream ss;
    ss << x;
    ss >> t;
    ++T;
    n = sz(t);
    return DP(0, false, 10, 10, true);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b;
    if (!a)
        cout << calc(b) << '\n';
    else
        cout << calc(b) - calc(a - 1) << '\n';
    return 0;
}

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