제출 #1125309

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

numbers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;

// (index) (current_number) (previous_number) (equal_or_less)
ll dp[20][11][11][2]; 
int a[20], n;
ll coz (int idx, int cur_num, int pre_num, int ok) {
	if (idx == n) {
		return 1;
	}
	ll &ret = dp[idx][cur_num][pre_num][ok];
	if (~ret) return ret;
	ret = 0;
	int git = 9;
	if (!ok) git = a[idx + 1];
	for (int i = 0; i <= git; ++i) {
		if (i == cur_num or i == pre_num) continue;
		int new_pre_num = cur_num;
		int new_ok = ok;
		if (i < a[idx + 1]) new_ok = 1;
		ret += coz (idx + 1, i, new_pre_num, new_ok);
	}
	return ret;
}


ll solve (ll x) {
	if (x < 0) return 0;
	memset (dp, -1, sizeof(dp));
	string k = to_string(x);
	n = (int)k.sz;
	for (int i = 0; i < n; ++i) {
		a[i + 1] = int(k[i] - 48);
	}
	ll ret = 1;
	for (int idx = 1; idx <= n; ++idx) {
		int git = 9;
		if (idx == 1) git = a[idx];
		for (int i = 1; i <= git; ++i) {
			int new_ok = 0;
			if (i < a[idx] or idx != 1) new_ok = 1;
			ll gosh = coz(idx, i, 10, new_ok);
			ret += gosh;
		}
	}
	return ret;
}


int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll a1, b1;
	cin >> a1 >> b1;
	cout << solve (b1) - solve (a1 - 1);
}

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