专栏文章

「梦熊 X16 · 异或赛」XOR and Rockets

PPigsyy
P13687题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mioer0w6
此快照首次捕获于
2025/12/02 18:00
3 个月前
此快照最后确认于
2025/12/02 18:00
3 个月前
查看原文

前言

只有我赛时写的 Trie 树优化转移，然后卡了一年的常吗？
状态定义的方式不同，转移优化的难度和时间复杂度是不同的。这个还是第一次见，感觉挺深刻的。
题目描述
给定两个长度为 nn 的非负整数序列 a,ba,b。接下来进行若干次操作：
  • 选择一个整数 x∈[1,n]x\in[1,n] 与一个正整数 yy。
  • 进行操作 ∀i∈[1,x],ai←ai⊕y\forall i\in[1,x],a_i\gets a_i\oplus y。即将 [1,x][1,x] 中数异或上 yy。
  • 这次操作的代价为 bxb_x。
输出通过若干次操作使得 aa 变为单调不降的最小代价。

思路

不难想到用 DP 求解。由于每次是将前缀异或，所以倒着做会比较方便（应该正着做也行，没细想）。
需要观察到答案分为两种情况：
  1. ana_n 不操作：任何时刻，后缀操作的异或和不会超过 VV。
  2. ana_n 操作：最优异或 210000+x2^{10000}+x，其中 xx 为任意不超过 VV 的非负整数。一旦某个位置要操作，只需要将 22 的指数次幂减少 11，并随意改动 xx。

情况 1（ana_n 不操作）

令 fi,jf_{i,j} 表示 i∼ni\sim n 位置中，所有位置的操作的异或和为 jj。这时候，如果 ii 位置操作为异或 kk，则需满足 ai⊕k⊕j≤ai+1⊕ja_i\oplus k\oplus j\le a_{i+1}\oplus j。所有合法的 kk 是 Trie 树上 log⁡V\log V 个子树。这样，复杂度即可做到 O(nVlog⁡V)O(nV\log V)。
不过，这样太不好了。我们将限制放在转移中，但实际上可以将限制放在状态里。即，令 fi,jf_{i,j} 表示 i∼ni\sim n 位置中，aia_i 最终的值为 jj。如果操作，则 aia_{i} 可以变成任何值。这样，转移只需要做后缀 max⁡\max 即可（也就是转化成了一段区间）。
时间复杂度：O(nV)O(nV)。

情况 2（ana_n 操作）

根据上述分析，只要操作，异或值可以变成任何值。于是，令 fi,jf_{i,j} 表示 i∼ni\sim n 位置，所有操作的异或和为 jj。转移是容易做到 O(1)O(1) 的。
时间复杂度：O(nV)O(nV)。

代码

赛时代码 O(nVlog⁡V)O(nV\log V)CPP
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int n;
int a[1 << 13], b[1 << 13];
i64 dp[2][1 << 13], fg[13][1 << 13];

inline void chmin(i64 &a, i64 b) { a = min(a, b); }
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++)
		cin >> b[i];

	memset(dp, 0x3f, sizeof dp);
	dp[n & 1][0] = 0;
	for (int i = n - 1; i >= 1; i --) {
		memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
		memset(fg, 0x3f, sizeof fg);
		for (int j = 0; j < 1 << 13; j ++) {
			if (dp[~i & 1][j] >= 1E18) continue;
			int x = a[i] ^ j, y = a[i + 1] ^ j;
			int S = j;
			for (int k = 12; k >= 0; k --)
				if (y >> k & 1) {
					chmin(fg[k][(S ^ ((x >> k & 1) << k)) >> k], dp[~i & 1][j]);
					S ^= (~x >> k & 1) << k;
				} else if (x >> k & 1) S ^= 1 << k;
			fg[0][S] = min(fg[0][S], dp[~i & 1][j]);
			if (x <= y)
				dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
		}
		for (int k = 12; k >= 0; k --)
			for (int x = 0; x < 1 << 13 - k; x ++)
				if (fg[k][x] < 1E18)
					for (int y = 0; y < 1 << k; y ++)
						dp[i & 1][x << k | y] = min(dp[i & 1][x << k | y], fg[k][x] + b[i]);
	}
	i64 res = 1ll << 60;
	for (int i = 0; i < 1 << 13; i ++)
		res = min(res, dp[1][i]);

	for (int i = 0; i < 1 << 13; i ++)
		dp[n & 1][i] = b[n];
	for (int i = n - 1; i >= 1; i --) {
		i64 mn = 1ll << 60;
		for (int j = 0; j < 1 << 13; j ++)
			mn = min(mn, dp[~i & 1][j]);
		for (int j = 0; j < 1 << 13; j ++) {
			dp[i & 1][j] = mn + b[i];
			if ((a[i] ^ j) <= (a[i + 1] ^ j))
				dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
		}
	}
	for (int i = 0; i < 1 << 13; i ++)
		res = min(res, dp[1][i]);

	cout << res << '\n';
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int T;
	cin >> T;

	while (T -- ) solve();

	return 0;
}
O(nV)O(nV) 代码CPP
void solve() {
	cin >> n;
	int mx = 0;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], mx = max(mx, a[i]);
	for (int i = 1; i <= n; i ++)
		cin >> b[i];
	mx = (1 << __lg(mx) + 1);

	memset(dp, 0x3f, sizeof dp);
	dp[n & 1][a[n]] = 0;
	for (int i = n - 1; i >= 1; i --) {
		memset(dp[i & 1], 0x3f, sizeof dp[i & 1]);
		i64 mn = 1ll << 60;
		for (int j = mx - 1; j >= 0; j --) {
			int k = a[i] ^ j ^ a[i + 1];
			if (k <= j) dp[i & 1][k] = min(dp[i & 1][k], dp[~i & 1][j]);
			mn = min(mn, dp[~i & 1][j]);
			dp[i & 1][j] = min(dp[i & 1][j], mn + b[i]);
		}
	}
	i64 res = 1ll << 60;
	for (int i = 0; i < mx; i ++)
		res = min(res, dp[1][i]);

	for (int i = 0; i < mx; i ++)
		dp[n & 1][i] = b[n];
	for (int i = n - 1; i >= 1; i --) {
		i64 mn = 1ll << 60;
		for (int j = 0; j < mx; j ++)
			mn = min(mn, dp[~i & 1][j]);
		for (int j = 0; j < mx; j ++) {
			dp[i & 1][j] = mn + b[i];
			if ((a[i] ^ j) <= (a[i + 1] ^ j))
				dp[i & 1][j] = min(dp[i & 1][j], dp[~i & 1][j]);
		}
	}
	for (int i = 0; i < mx; i ++)
		res = min(res, dp[1][i]);

	cout << res << '\n';
}

评论

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

正在加载评论...