「BZOJ2505」tickets 题解

preface

网上目前还没看到我的方法，就大概讲一下做法

solution

首先想到贪心，考虑 \([l, r]\) 的最大次数，一定是找到最小的 \(x\) 满足 \(l \sim x\) 的位数的和大于等于 \(k\)，然后递归的求解 \([x + 1, r]\)，易证。

还是考虑将 \(Query (l, r)\) 拆分成 \(Query (1, r)\) 和 \(Query (1, l - 1)\)

那么我们就有一个简单的数位 \(dp\)，\(dfs (step, tot, last, limit)\) 表示从最高位考虑到 \(step\) 位，这些位的位数和位 \(tot\)，上一个区间剩下 \(last\) 的位数和，是或否顶到上届，容易写出。

但是我们发现 \(Query (1, r) - Query (1, l - 1) \neq Query (l, r)\)，问题在于 \([1, l - 1]\) 这个区间剩下的位数和给到 \([l, r]\) 可能会让答案多一。

怎么处理这个问题呢？考虑暴力就是如果当前考虑到了 \(l\)，那么他就不从上一个区间继承 \(last\) 了，考虑记忆化搜索优化，那么只需要判断当前这个状态是否包含 \(l\)，再加一维状态 \(past\) 用以判断当前这个区间是否包含 \(l\)。

code

//我看着，天真的我自己
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio> 
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define MP(x,y) make_pair (x, y)
#define PII pair <int, int>
#define db double
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)

template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
void read (T &x) {
	x = 0; bool fl_for_x = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') {
		if (ch == '-') fl_for_x = 0;
		ch = getchar ();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar ();
	}
	if (!fl_for_x) x = -x;
}
template <typename T, typename... Args>
void read (T &x, Args&... args) {
	read (x), read (args...);
}
const int Maxn_For_Print = 30;
int Tp_For_Print, St_For_Print[Maxn_For_Print + 5];
template <typename T>
void write (T x) {
	if (x == 0) {
		putchar ('0');
		return;
	}
	if (x < 0) {
		x = -x;
		putchar ('-');
	}
	while (x) {
		St_For_Print[++Tp_For_Print] = x % 10;
		x /= 10;
	}
	while (Tp_For_Print) {
		putchar (St_For_Print[Tp_For_Print--] + '0');
	}
}
template <typename T>
void print (T x, char ch) {
	write (x), putchar (ch);
}

const int Maxn = 18;
const int Maxtot = 9 * 17;
const int Maxlast = 1e3;

LL l, r, k, w[Maxn + 5];
int tp, x[Maxn + 5];

pair <LL, int> dp[2][Maxn + 5][Maxtot + 5][Maxlast + 5];
bool vis[2][Maxn + 5][Maxtot + 5][Maxlast + 5];
LL calc (LL past, int step) {
	if (past <= l && l <= past + w[step] - 1) return 1;
	else return 0;
}
pair <LL, int> dfs (int step, int tot, int last, int Limit, LL past) {
	if (!Limit && vis[calc (past, step)][step][tot][last]) return dp[calc (past, step)][step][tot][last];

	if (step == 0) {
		if (past == l) {
			if (tot >= k) return MP (1, 0);
			else return MP (0, tot);
		}
		last += tot;
		if (last >= k) return MP (1, 0);
		else return MP (0, last);
	}
	int Up = Limit ? x[step] : 9;
	pair <LL, int> res = MP (0, last);
	rep (i, 0, Up) {
		pair <LL, int> tmp = dfs (step - 1, tot + i, res.se, Limit & (i == Up), past + (w[step - 1] * i));
		res = MP (res.fi + tmp.fi, tmp.se);
	}
	if (!Limit) dp[calc (past, step)][step][tot][last] = res, vis[calc (past, step)][step][tot][last] = 1;
	return res;
}
LL Query (LL qwq) {
	tp = 0;
	while (qwq) {
		x[++tp] = qwq % 10;
		qwq /= 10;
	}
	return dfs (tp, 0, 0, 1, 0).fi;
}

signed main () {
	// freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.in", "r", stdin);
	// freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.out", "w", stdout);
//	freopen ("transport.in", "r", stdin);
//	freopen ("transport.out", "w", stdout);

	w[0] = 1; rep (i, 1, Maxn) w[i] = w[i - 1] * 10;
	read (l, r, k);
	write (Query (r) - Query (l - 1));
	return 0;
}