99分 RE on #25 求救
查看原帖
99分 RE on #25 求救
186472
AC_loveRealNewbie楼主2023/10/2 21:31
#include <bits/stdc++.h>
#define int long long
using namespace std;
int sw[1001];
int dp[1001][10][2];
string lef, rig;
int k, l;
int dfs(int x, int lst, int llst, bool ok, bool have_llst, bool to_max)
// x 表示搜到了哪一位
// lst 表示上一位是什么
// llst 表示上上位是什么 
// ok 表示是否已经满足条件
// have_llst 表示是否存在上上位 
// to_max 表示是否达到上限 
{
	if(x == 0)
		return ok;
	if(!to_max && dp[x][lst][ok] != -1)
		return dp[x][lst][ok];
	int maxn = to_max ? sw[x] : 9;
	int r = 0;
	for(int i = 0; i <= maxn; i = i + 1)
		r = (r + dfs(x - 1, i, have_llst ? lst : -1, ok || ((i == lst) && have_llst) || ((i == llst) && have_llst), have_llst || (i != 0), to_max && (maxn == i)) );
	if(!to_max && have_llst && llst != -1)
		dp[x][lst][ok] = r;
	return r;
}
int solve(string s)
{
	int len = 0, slen = s.size() - 1;
	while(slen >= 0)
		sw[++ len] = s[slen] - '0', slen --;
	while(!sw[len])
		len --;
	memset(dp, -1, sizeof(dp));
	return dfs(len, -1, -1, 0, 0, 1);
}
signed main()
{
	int ll, rr;
	cin >> ll >> rr;
	int tmp = 0;
	if(ll == 0)
		ll = 2, tmp = 2;
	if(ll == 1)
		ll = 2, tmp = 1;
	lef = to_string(ll);
	rig = to_string(rr);
//	cin >> lef >> rig;
	k = 1;
	l = lef.length();
	while(lef[l - k] == '0' && l > k)
		lef[l - k] = '9', k ++;
	lef[l - k] -= 1;
	printf("%lld\n", (rr - ll + tmp + 1 - (solve(rig) - solve(lef))));
	return 0;
}
2023/10/2 21:31
加载中...