求助0分,一直输出0,调了2天没调出来
查看原帖
求助0分,一直输出0,调了2天没调出来
502658
Ray662楼主2023/7/2 21:31
#include <bits/stdc++.h>
#define int long long
#define F f[p][v1][v2][_3][_4][_8]
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define _all(i, a, b)  for (int i = (a); i >= (b); i -- )
using namespace std;
int a, b, tt[15], f[15][10][10][2][2][2];
// 长度,p + 1位的值,p + 2 位的值,是否已经出现连续 3 个,4 是否出现过,8 是否出现过
int dfs(int p, int v1, int v2, int _3, int lim, int _4, int _8) {
	if (p == 2) {
		if (! _3)  return 1;
		else {
			if (((! _8) && (_4)) || ((_8) && (! _4)))  return 81;  // 100 - 10 - 9 = 81
			if ((! _8) && (! _4))  return 98;  // 100 - 2 = 98 (48、84)
		}
	}
	if (F != -1)  return F;
	int ans = 0, mx;
	if (lim)  mx = tt[p];
	else  mx = 9;  // 如果有上限,当前位最大值为原数的当前位,否则为9 
	_for (i, 0, mx) {
		if ((_4 && (i == 8)) || (_8 && (i == 4)))  continue;
		if ((p == 11) && (! i))  continue;
		ans += dfs(p - 1, i, v1, (_3 || ((i == v1) && (i == v2))), (lim && (i == mx)), (_4 || (i == 4)), (_8 || (i == 8)));
	}
	if (! lim)  F = ans;
	return ans;
}
inline int solve(int x) {
	int num = 0;
	while (x)  tt[ ++ num] = x % 10, x /= 10;
	memset(f, -1, sizeof(f));
	return dfs(num, -1, -1, 0, 1, 0, 0);
}
signed main() {
	ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> a >> b;
	cout << solve(b) - solve(a - 1) << endl;
	return 0;
}
2023/7/2 21:31
加载中...