专栏文章

P12407 「CZOI-R3」数字变换 Solution

冷冷却心月明かり
P12407题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mipfa4yn
此快照首次捕获于
2025/12/03 11:03
3 个月前
此快照最后确认于
2025/12/03 11:03
3 个月前
查看原文
锐评一下难度，B 放困难推式子推半天不会做发现 CD 都是简单题，/tuu。再锐评一下出题人怎么不卡暴力枚举子集的 O(3v)O(3^v) 做法。
dp。定义状态 fi,jf_{i,j} 表示操作 ii 次恰好变为 jj 的最小代价。直接转移那么有：
fi,j=wi,j+min⁡k=1n{fi−1,k+2(L−(xkAND⁡xi))}.f_{i,j} = w_{i,j}+ \min_{k=1}^n \{f_{i-1,k}+2(L-(x_k \operatorname{AND} x_i))\}.
略微变形得到：
fi,j=2L+wi,j+min⁡k=1n{fi−1,k−2(xkAND⁡xi)}.f_{i,j}=2L + w_{i,j}+\min_{k=1}^n \{f_{i-1, k} - 2 (x_k \operatorname{AND} x_i)\}.
我们应当着手于后面的最小值。注意到这个值只和 xkx_k 和 xix_i 有关。我们记 bit⁡(x)\operatorname{bit}(x) 表示 xx 在二进制下为 11 的位的集合。考虑一下按位与的性质，与得的结果一定是原数的子集，所以我们可以枚举 xix_i 与 xkx_k 的按位与，然后考虑 xkx_k 转移的贡献。哥们把贡献传到每个子集上，记辅助数组 gS=min⁡bit⁡(xj)=Sfi−1,j\displaystyle g_S=\min_{\operatorname{bit}(x_j) = S} f_{i-1,j}，以及 hT=min⁡T⊆SgS\displaystyle h_T=\min_{T \subseteq S} g_S。那么我们就有转移
fi,j=wi,j+2L+min⁡T⊆bit⁡(j){hT−2T}.f_{i,j} = w_{i,j} + 2L + \min_{T \subseteq \operatorname{bit}(j)} \{h_T-2T\}.
会发现你枚举的 TT 不一定恰好等于两个数的与，可能是两个数的与的子集，但这个转移是对的，原因是：假如正确的按位与得到的是 T0T_0，而枚举到了一个 T1⊂T0T_1 \subset T_0，在 hT0=hT1h_{T_0}= h_{T_1} 的情况下，显然 2T0>2T12T_0 > 2T_1，后者的转移不优。故转移有正确性。然后做完了。一共 kk 层转移，每次转移要枚举子集，设 xix_i 的值域为 O(2v)O(2^v)，如果暴力枚举就是 O(3v)O(3^v)，如果用 FMT 实现就是 O(v2v)O(v 2^v)，再加上最后转移回到 ff 数组还带一个 O(n)O(n)。根据实现的不同，总复杂度 O((n+3v)k)O((n+3^v) k) 或者 O((n+v2v)k)O((n+v 2^v)k)。
代码是 FMT 版本，和赛时写的暴力枚举子集相比总用时快了六倍。
CPP
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const int V = 16;
int n, K, P, X[N], W[N][11];

namespace RAND {
	int c, y[65536]; unsigned long long seed;
	int get_rand(int mod)
	{
		seed ^= seed << 14;
		seed ^= seed >> 7;
		seed ^= seed << 19;
		seed ^= seed << 23;
		return seed % mod;
	}
	void get_input()
	{
		for (int i = 0; i < c; i ++) cin >> y[i];
		for (int i = 1; i <= n; i++) X[i] = y[get_rand(c)];
		for (int i = 1; i <= n; i++) for (int j = 1; j <= K; j++) W[i][j] = get_rand(1000000);
	}
}

LL DP[11][N], tmp[1 << 16], g[1 << 16]; int popc[1 << 16];

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> P >> K >> RAND::c >> RAND::seed; RAND::get_input();
	int mx = 0;
	for (int i = 1; i <= n; i ++) mx = max(mx, X[i]);
	memset(DP, 0x3f, sizeof DP); DP[0][P] = 0;
	for (int i = 1; i <= K; i ++) {
		memset(tmp, 0x3f, sizeof tmp); memset(g, 0x3f, sizeof g);
		for (int j = 1; j <= n; j ++) g[X[j]] = min(g[X[j]], DP[i - 1][j]);
		for (int j = 0; j < V; j ++) for (int k = 0; k < (1 << V); k ++)
			if ((k >> j) & 1) g[k ^ (1 << j)] = min(g[k ^ (1 << j)], g[k]);
		for (int j = 0; j < (1 << V); j ++) g[j] -= 2 * j;
		for (int j = 0; j < V; j ++) for (int k = 0; k < (1 << V); k ++)
			if ((k >> j) & 1) g[k] = min(g[k], g[k ^ (1 << j)]);
		for (int j = 1; j <= n; j ++) DP[i][j] = g[X[j]] + 2 * mx + W[j][i];
	}
	for (int i = 1; i <= n; i ++) cout << DP[K][i] << " \n"[i == n];
	return 0;
}

评论

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

正在加载评论...