专栏文章

题解：P8145 [JRKSJ R4] kth

WWilliamFranklin
P8145题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min96jwz
此快照首次捕获于
2025/12/01 22:37
3 个月前
此快照最后确认于
2025/12/01 22:37
3 个月前
查看原文
很牛的题啊，感觉自己的思维需要更深一层了。

Hint

Hint 1
题意可以转化成在一个排列上走。那么考虑走的过程中需要什么？以及如何实现这个走的过程。
Answer 1
走的时候肯定是需要从 ii 走 jj 个点（包括 ii 这个点）的方案数的，设其为 fi,jf_{i, j}。走的过程就是每一次判断走小的那一边是否方案数 ≥k\ge k，若满足，就走小的那边；否则，走大的那边，且 kk 减去 fmx,jf_{mx, j}。
Hint 2
考虑 n≥3n \ge 3 时，从任意一个点走至少多少步，都满足方案数 ≥k\ge k。
Answer 2
答案是 j≥2log⁡2kj \ge 2\log_2 k，且仅在 n=3n = 3 时取到下界。
Hint 3
考虑是不是可以利用 Hint 2 优化一下 dp 的状态数。
Hint 4
对于任意的 j≤min⁡{i,n−i+1}j \le \min\{i, n - i + 1\}，fi,jf_{i, j} 的值是多少？
Answer 4
答案是 2j−12^{j - 1}。
Hint 5
能否利用 Hint 4 再次优化一下 dp 状态数。

Solution

题意就转化成在一个排列上任取起点开始走 mm 步，求出所有路径中字典序第 kk 小的路径的权值和。
首先自然的，想到 fi,jf_{i, j} 表示从 ii 走 jj 个点（包括 ii 这个点）的方案数。求最终答案是容易的，不会的可以看下 Hint 1。时间复杂度 O(nm)O(nm)。
考虑优化。我们发现，在 n(n≥3)n(n \ge 3) 时，对于任意的正整数 kk，都有在 j≥2log⁡2kj \ge 2\log_2 k 时（且仅在 n=3n = 3 时取到下界），fi,j≥kf_{i, j} \ge k。那就可以 O(nlog⁡2k)O(n\log_2 k) 求出所有对我们有用的 ff 值。设 B=⌈2log⁡2k⌉B = \lceil2\log_2 k\rceil，考虑前 k−Bk - B 步怎么走。若 k−B>nk - B > n，那么最后一定在某一个 ii 与 i+1i + 1 之间交替走；若 k−B≤nk - B \le n，那就直接暴力走即可。所以我们直接 O(n)O(n) 就可以求出 k−Bk - B 步的答案以及最后的停留位置。后面 BB 步的过程和一开始暴力做法一样。时间复杂度 O(nlog⁡2k)O(n\log_2 k)。竟然还没完。
接下来，考虑现在瓶颈是在求 ff 上，继续考虑如何优化这个过程。简单但或许并不是那么显然的想到，对于 i∈[B,n−B+1]i \in \left[B, n - B + 1\right]，其 fi,j(1≤j≤B)f_{i, j}(1 \le j \le B) 就直接是 2j−12^{j - 1}。所以我们只用单独对 i∈[1,B)∪(n−B+1,n]i \in \left[1, B\right)\cup\left(n - B + 1, n\right] 求 ff 值即可。
别忘了特判一下 n=1n = 1 和 n=2n = 2 的情况。
最终，时间复杂度 O(n+log⁡22k)O(n + \log_2^2k)。
AC CodeCPP
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 2e7 + 5;
const __int128 INF = 1e30;
int n, K = 125, p[N], mp[N], W[N];
long long m, k;
__int128 f[300][130], fac2[130];
__int128 get(int x, long long k) {
	if (x <= 0 || x > n) return 0;
	if (k > K) return INF;
	if (K < x && x < n - K + 1) return fac2[k - 1];
	return f[mp[x]][k];
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	fac2[0] = 1;
	For(i, 1, 125) fac2[i] = fac2[i - 1] * 2;
	cin >> n >> m >> k;
	For(i, 1, n) cin >> p[i];
	For(i, 1, n) W[p[i]] = i;
	int w = 0;
	For(i, 1, n) if (p[i] == 1) w = i;
	if (n == 1) { cout << -1; return 0; }
	if (n == 2) {
		if (k > 2) cout << -1;
		else if (k == 1) cout << (unsigned int)((m + 1) / 2 + m / 2 * 2);
		else cout << (unsigned int)((m + 1) / 2 * 2 + m / 2);
		return 0;
	}
	p[0] = p[n + 1] = 1e9;
	vector<int> G;
	int L = min(n, K);
	For(i, 1, L) G.push_back(i), mp[i] = G.size() - 1;
	For(i, max(L + 1, n - K + 1), n) G.push_back(i), mp[i] = G.size() - 1;
	int sz = G.size();
	For(i, 0, sz - 1) f[i][1] = 1;
	For(i, 2, K) For(j, 0, sz - 1) f[j][i] = get(G[j] - 1, i - 1) + get(G[j] + 1, i - 1);
	unsigned int ans = 0;
	w = 0;
	For(i, 1, n) {
		if (get(W[i], m) < k) k -= get(W[i], m);
		else { w = W[i]; break; }
	}
	if (w == 0) { cout << -1; return 0; }
	int minn = (p[w - 1] < p[w + 1] ? w - 1 : w + 1);
	m--;
	int S = w;
	long long yu = m - K;
	ans = p[S];
	if (yu > 0) {
		while (yu) {
			int x = (p[minn - 1] < p[minn + 1] ? minn - 1 : minn + 1);
			ans += p[minn];
			yu--;
			if (x == w || yu == 0) break;
			w = minn, minn = x;
		}
		ans += (unsigned int)p[w] * (unsigned int)((yu + 1) / 2) 
			+  (unsigned int)p[minn] * (unsigned int)(yu / 2);
		if (yu & 1) S = w;
		else S = minn;
	}
	m = min(m, 1ll * K);
	Dec(i, m, 1) {
		if (S == 1) ans += p[++S];
		else if (S == n) ans += p[--S];
		else {
			if (p[S - 1] < p[S + 1]) {
				if (get(S - 1, i) >= k) ans += p[--S];
				else k -= get(S - 1, i), ans += p[++S];
			} else {
				if (get(S + 1, i) >= k) ans += p[++S];
				else k -= get(S + 1, i), ans += p[--S];
			}
		}
	}
	cout << ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...