救命,对拍了5e6的数据,提交报0
查看原帖
救命,对拍了5e6的数据,提交报0
553482
oyecat楼主2022/11/18 23:21
#include <bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
#define ll long long 
#define int long long
#define endl '\n'
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
ll dp[20][2][2];
ll x[20];
ll jw[20];//没limit限制时,pos位的重复次数
ll yl[20];//有limit限制时,pos位的重复次数
ll dfs(int pos, int de, int limit, int pro0) {
	if (pos == -1) return 0;
	if (dp[pos][limit][pro0] != -1) return dp[pos][limit][pro0];
	ll ans = 0;
	for (int i = 0; i <= (limit ? x[pos] : 9); i++) {
		if (pro0 && i == 0) {
			ans += dfs(pos - 1, de, limit && i == x[pos], 1);
		}
		else {
			if (i == de) {
				if (i == x[pos] && limit)ans += dfs(pos - 1, de, limit && i == x[pos], 0) + yl[pos];
				else ans += dfs(pos - 1, de, limit && i == x[pos], 0) + jw[pos];
			}
			else {
				ans += dfs(pos - 1, de, limit && i == x[pos], 0);
			}
		}
	}
	dp[pos][limit][pro0] = ans;
	return ans;
}
ll solve(ll a, int de) {
	int len = 0;
	int cut = 0;
	while (a >= jw[cut]) {
		yl[cut] = a % jw[cut++] + 1;
	}
	while (a) {
		x[len++] = a % 10;
		a /= 10;
	}
	memset(dp, -1, sizeof dp);
	return dfs(len - 1, de, 1, 1);
}
int32_t main() {
	ll a, b;
	scanf("%lld%lld", &a, &b);
	a--;
	jw[0] = 1;
	for (int i = 1; i <= 15; i++) jw[i] = jw[i - 1] * 10;
	for (int i = 0; i <= 9; i++) {
		printf("%lld ", solve(b, i) - solve(a, i));
	}
}

真的会谢,难道是前导0会有问题吗QAQ求hack数据

2022/11/18 23:21
加载中...