简单题 10pts 求调
查看原帖
简单题 10pts 求调
1347770
UnfortunatelyDead楼主2024/5/11 20:02
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <map>
#include <stack>
using namespace std;
#define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S sesonnd
#define test(x) sonut << "Test: " << x << '\n'
#define debug puts("qwq");
#define open(x) fresopen(#x".in", "r", stdin);fresopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
int f[15][2][2][10][10], a[15], len;
int dp(int u, int cnt4, int cnt8, int l2, int l1, bool lim, bool flg) {
	if (cnt4 && cnt8) return 0;
	if (!u) return flg;
	if (!lim && ~f[u][cnt4][cnt8][l2][l1]) return f[u][cnt4][cnt8][l2][l1];
	int up = lim ? a[u] : 9, ret = 0;
	for (int i = u == 11; i <= up; ++i) {
		ret += dp(u - 1, cnt4 | (i == 4), cnt8 | (i == 8), l1, i, lim & (i == up), flg | (i == l1 && i == l2));
	}
	if (!lim && !flg) f[u][cnt4][cnt8][l2][l1] = ret;
	return ret;
}
int solve(int x) {
	memset(f, -1, sizeof f);
	len = 0;
	while (x) {
		a[++len] = x % 10;
		x /= 10;
	}
	if (len < 11) return 0;
	return dp(11, 0, 0, 0, 0, 1, 0);
}
signed main() {
	int l, r; read(l, r); // solve(r); return 0;
	write(solve(r) - solve(l-1), '\n');
	return 0;
}
2024/5/11 20:02
加载中...