联合省选 2024 题解

题解/做题记录
12k 词

Day1T1 季风 wind

Link

Day1T2 魔法手杖 xor

考虑扔 Trie 上，然后在 Trie 上游走，表示当前 U∖SU \setminus S 中 ⊕x{} \oplus x 后最小的值。

然后考虑往某个儿子走，若要 min⁡i∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus x 这一位是 11 则需要把另一个儿子扔到 SS 里，但是当走 11 的时候不一定 min⁡i∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus x 这一位是 11 答案就更优，那这种情况就需要两种都跑一遍。

以上是考场想法。

考虑二分答案，这样就可以直接贪做到 O(nk2)O(n k ^ 2)，用压缩 Trie 可以优化到 O(nk)O(nk)，但是毛想想就知道很难写。

不妨直接考虑最终答案，若答案这一位需要是 11，则除了 min⁡i∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus x 这一位是 11 以外，min⁡i∈Sai+x\min _ {i \in S} a _ i + x 这一位也需要是 11，判断就考虑确定这一位取值后剩下的位全填 11 然后 check 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

void read(__int128 &x){
	// read a __int128 variable
	char c; bool f = 0;
	while(((c = getchar()) < '0' || c > '9') && c != '-');
	if(c == '-'){f = 1; c = getchar();}
	x = c - '0';
	while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';
	if(f) x = -x;
}
void write(__int128 x){
	// print a __int128 variable
	if(x < 0){putchar('-'); x = -x;}
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}

int dataID, T, n, m, k, b[100005];
__int128 a[100005], ans;
struct Trie {
	int tot, trie[12000005][2];
	__int128 mn[12000005];
	long long sum[12000005];

	Trie() {memset(mn, 0x3f, sizeof(mn));}
	void clear() {
		for (int i = 0; i <= tot; i++)
			trie[i][0] = trie[i][1] = 0, mn[i] = (__int128)1 << 121, sum[i] = 0;
		tot = 0;
		return ;
	}
	void insert(__int128 x, int val) {
		int now = 0;
		for (int i = k - 1; i >= 0; i--) {
			int id = x >> i & 1;
			if (!trie[now][id]) trie[now][id] = ++tot;
			now = trie[now][id];
			mn[now] = min(mn[now], x), sum[now] += val;
		}
		return ;
	}
	void dfs(int now, int h, int m, __int128 mnS, __int128 val, __int128 x) {
		if (h == -1) {ans = max(ans, val ^ x); return ;}
		__int128 bit = (__int128)1 << h, rest = bit - 1;
		if (!now && h != k - 1) {ans = max(ans, mnS + (x | bit | rest)); return ;}
		int flag = 0;
		if (sum[trie[now][1]] <= m && (x | bit | rest) + min(mnS, mn[trie[now][1]]) >= ((val ^ x) | bit)) {
			dfs(trie[now][0], h - 1, m - sum[trie[now][1]], min(mnS, mn[trie[now][1]]), val, x | bit);
			flag = 1;
		}
		if (sum[trie[now][0]] <= m && (x | rest) + min(mnS, mn[trie[now][0]]) >= ((val ^ x) | bit)) {
			dfs(trie[now][1], h - 1, m - sum[trie[now][0]], min(mnS, mn[trie[now][0]]), val | bit, x);
			flag = 1;
		}
		if (!flag) {
			dfs(trie[now][0], h - 1, m, mnS, val, x);
			dfs(trie[now][1], h - 1, m, mnS, val | bit, x | bit);
		}
		return ;
	}
} tr;

int main() {
	// freopen("xor.in", "r", stdin);
	// freopen("xor.out", "w", stdout);
	scanf("%d%d", &dataID, &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &k);
		tr.clear();
		for (int i = 1; i <= n; i++) read(a[i]);
		long long sum = 0;
		__int128 mnS = (__int128)1 << 121;
		for (int i = 1; i <= n; i++) scanf("%d", &b[i]), tr.insert(a[i], b[i]), sum += b[i];
		ans = 0;
		tr.dfs(0, k - 1, m, mnS, 0, 0);
		if (sum <= m) {
			__int128 res = (__int128)1 << 121;
			for (int i = 1; i <= n; i++) res = min(res, a[i]);
			ans = max(ans, res + ((__int128)1 << k) - 1);
		}
		write(ans);
		puts("");
	}
	return 0;
}

Day1T3 虫洞 wormhole

还不会。

Day2T1 迷宫守卫 maze

简单题，设 fi,jf _ {i, j} 表示只考虑子树 ii，要使排列第一位是 jj 的最小代价。设 SiS _ i 表示 ii 子树中数的集合，则有状态转移方程：

fi,j={f2i,j+min⁡{wi,min⁡k∈S2i+1∧k>jf2i+1,k}j∈S2if2i+1,j+min⁡k∈S2i∧k>jf2i,kj∈S2i+1f _ {i, j} = \begin{cases} f _ {2i, j} + \min\left\{w _ i, \min\limits _ {k \in S _ {2i + 1} \land k > j} f _ {2i + 1, k}\right\} & j \in S _ {2i} \\ f _ {2i + 1, j} + \min\limits _ {k \in S _ {2i} \land k > j} f _ {2i, k} & j \in S _ {2i + 1} \end{cases}

由于是满二叉树，所以状态数总和为 O(nlog⁡n)O(n \log n)，直接求就行了。

考虑输出方案，我们已经知道要先走哪个儿子，为了使排列尽量小，我们要将尽量大的 kk 传给第一个儿子。也就是说，假如排列第一个数是 jj，则第一个儿子的 kk 应该等于 k−fi,j−fson,jk - f _ {i, j} - f _ {son, j}，然后求出第一个儿子用了多少，再把剩余的全都传给第二个儿子。

另外有一个小细节就是为了保证第二个儿子能用的 kk 尽量大，在能不使用 wiw _ i 时就不使用 wiw _ i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int T, n, Q[140005];
long long k, w[66005];
vector<pair<int, long long>> vec[140005];

long long print(int i, long long k) {
	if (i >= 1 << n) {printf("%d ", Q[i]); return 0;}
	long long used = 0;
	int ls = i << 1, rs = i << 1 | 1, p = 0, q = 0;
	long long lmn = k + 1, rmn = w[i], rmn2 = 0x3f3f3f3f3f3f3f3f;
	while (p < (int)vec[ls].size() || q < (int)vec[rs].size())
		if (p < (int)vec[ls].size() &&
			(q >= (int)vec[rs].size() || vec[ls][p].first > vec[rs][q].first)) {
			long long cost = min(vec[ls][p].second + rmn, k + 1);
			if (cost <= k) {
				used += print(ls, k - rmn);
				if (rmn2 > k - used) used += w[i];
				used += print(rs, k - used);
				break;
			}
			lmn = min(lmn, vec[ls][p].second);
			p++;
		} else {
			long long cost = min(vec[rs][q].second + lmn, k + 1);
			if (cost <= k) {
				used += print(rs, k - lmn);
				used += print(ls, k - used);
				break;
			}
			rmn = min(rmn, vec[rs][q].second);
			rmn2 = min(rmn2, vec[rs][q].second);
			q++;
		}
	return used;
}

int main() {
	// freopen("maze.in", "r", stdin);
	// freopen("maze.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
		scanf("%d%lld", &n, &k);
		for (int i = 1; i < 1 << n; i++) scanf("%lld", &w[i]);
		for (int i = 1 << n; i < 2 << n; i++) scanf("%d", &Q[i]);
		for (int i = 1; i < 2 << n; i++) vector<pair<int, long long>>().swap(vec[i]);
		for (int i = (2 << n) - 1; i >= 1; i--)
			if (i >= 1 << n) vec[i].emplace_back(Q[i], 0);
			else {
				int ls = i << 1, rs = i << 1 | 1, p = 0, q = 0;
				long long lmn = k + 1, rmn = w[i];
				while (p < (int)vec[ls].size() || q < (int)vec[rs].size())
					if (p < (int)vec[ls].size() &&
						(q >= (int)vec[rs].size() || vec[ls][p].first > vec[rs][q].first)) {
						long long cost = min(vec[ls][p].second + rmn, k + 1);
						vec[i].emplace_back(vec[ls][p].first, cost);
						lmn = min(lmn, vec[ls][p].second);
						p++;
					} else {
						long long cost = min(vec[rs][q].second + lmn, k + 1);
						vec[i].emplace_back(vec[rs][q].first, cost);
						rmn = min(rmn, vec[rs][q].second);
						q++;
					}
			}
		print(1, k);
		puts("");
	}
	return 0;
}

Day2T2 重塑时光 timline

看数据范围猜复杂度是 O(3n)/O(3nn)O(3 ^ n) / O(3 ^ n n)。

考虑 k=0k = 0 的情况，就是求拓扑序的数量，直接状压即可。

对于更一般的情况，我们考虑将连续的一段缩成一个点，这样只需要每种点数对应的图的数量即可求出答案。

具体地，我们先对于每个 SS 表示集合 SS 的拓扑序个数，然后设 dpS,idp _ {S, i} 表示只考虑集合 SS，有 ii 个点的 DAG 数量。

怎么求 dpdp 先放一放，考虑求出来之后怎么算答案。

首先是合法方案数：

∑i=1k+1dpU,ii!k!(k+1i)\sum\limits _ {i = 1} ^ {k + 1} dp _ {U, i} i! k! \binom{k + 1}{i}

然后考虑总方案数，设 fi,jf _ {i, j} 表示前 ii 个数切了 jj 刀（只能切在数的前面），考虑切的顺序时的方案，转移是简单的，最终结果就是 fn+1,kn!f _ {n + 1, k} n!。

剩下的就是本题最大的难点，如何求解 dpdp 的值。

这里需要一个结论：对于一张 DAG，每次选择一个零度点的集合删去并将贡献加上 −1-1 的集合大小 +1+1 次，则所有删点方案的贡献总和为 11。

于是考虑设 gS,ig _ {S, i} 表示集合 SS 构成 ii 个点，且这些点之间没有边的方案数，则有状态转移方程：

dpS,i=∑T∈S,T≠∅,preT∩S=∅∑j=0∣T∣dpS∖T,j−igT,jdp _ {S, i} = \sum\limits _ {T \in S, T \ne \varnothing, pre _ T \cap S = \varnothing} \sum\limits _ {j = 0} ^ {|T|} dp _ {S \setminus T, j - i} g _ {T, j}

其中 preTpre _ T 表示所有 TT 的前驱。

暴力转移，前两部分的复杂度是 O(3n)/O(3nn)O(3 ^ n) / O(3 ^ n n)，最后求 dpdp 的复杂度是 O(3nn2)O(3 ^ n n ^ 2)。

发现转移很像卷积的形式，考虑设 DPS(x)=∑i=0ndpS,ixi,GS(x)=∑i=0ngS,ixiDP _ S(x) = \sum _ {i = 0} ^ n dp _ {S, i} x ^ i, G _ S(x) = \sum\limits _ {i = 0} ^ n g _ {S, i} x ^ i，则 DPS,GSDP _ S, G _ S 都是 nn 次多项式，且有：

DPS=∑T∈S,T≠∅,preT∩S=∅DPS∖T×GTDP _ S = \sum\limits _ {T \in S, T \ne \varnothing, pre _ T \cap S = \varnothing} DP _ {S \setminus T} \times G _ T

考虑拉格朗日插值，任意取 n+1n + 1 个点值，多项式卷积就是点值相乘，多项式加法就是点值相加，因此可以 O(3nn)O(3 ^ n n) 转移，而我们只需要 DPUDP _ U 的系数，因此求出 DPUDP _ U 的 n+1n + 1 个点值后再用拉格朗日插值暴力求出系数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int n, m, k, U;
int pre[1 << 15], ts[1 << 15], g[1 << 15][25], gv[1 << 15][25], dp[1 << 15][25];
int tmp[1 << 15];
int fac[25], C[25][25], f[25][25];

void toposort(int S) {
	tmp[0] = 1;
	vector<int> sub;
	for (int T = S; T >= 1; T = (T - 1) & S) sub.push_back(T);
	reverse(sub.begin(), sub.end());
	for (int T : sub) {
		tmp[T] = 0;
		for (int TT = T; TT; TT -= TT & -TT) {
			int i = TT & -TT;
			if (((T ^ i) & pre[i]) == (pre[i] & S)) tmp[T] = (tmp[T] + tmp[T ^ i]) % mod;
		}
	}
	ts[S] = tmp[S];
	return ;
}
int power(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = (long long)ans * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}
vector<int> pls(vector<int> a, vector<int> b) {
	if (a.size() < b.size()) a.swap(b);
	vector<int> ans(a.size());
	for (int i = 0; i < (int)ans.size(); i++)
		if (i < (int)b.size()) ans[i] = (a[i] + b[i]) % mod;
		else ans[i] = a[i];
	return ans;
}
vector<int> mul(vector<int> a, vector<int> b) {
	vector<int> ans(a.size() + b.size() - 1);
	for (int i = 0; i < (int)a.size(); i++)
		for (int j = 0; j < (int)b.size(); j++) ans[i + j] = (ans[i + j] + (long long)a[i] * b[j]) % mod;
	return ans;
}
vector<int> mul(vector<int> a, int b) {
	for (int i = 0; i < (int)a.size(); i++) a[i] = (long long)a[i] * b % mod;
	return a;
}
vector<int> div(vector<int> a, int b) {
	if (!b) {
		for (int i = 1; i < (int)a.size(); i++) swap(a[i - 1], a[i]);
		a.pop_back();
		return a;
	}
	vector<int> ans(a.size());
	int c = power(mod - b, mod - 2);
	ans[0] = (long long)a[0] * c % mod;
	for (int i = 1; i < (int)ans.size(); i++) ans[i] = (long long)(a[i] - ans[i - 1] + mod) * c % mod;
	ans.pop_back();
	return ans;
}

int main() {
	// freopen("timeline.in", "r", stdin);
	// freopen("timeline.out", "w", stdout);

	scanf("%d%d%d", &n, &m, &k);
	U = (1 << n) - 1;
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		pre[1 << v] |= 1 << u;
	}
	for (int S = 1; S < 1 << n; S++) {
		int lowbit = S & -S;
		pre[S] = (pre[S ^ lowbit] | pre[lowbit]) & (U ^ S);
	}
	for (int S = 1; S < 1 << n; S++) toposort(S);

	g[0][0] = 1;
	for (int S = 1; S < 1 << n; S++)
		for (int i = 1; i <= n; i++)
			for (int T = S; T; T = (T - 1) & S)
				if ((T & -T) == (S & -S) && !(pre[T] & (S ^ T)) && !(pre[S ^ T] & T))
					g[S][i] = (g[S][i] + (long long)g[S ^ T][i - 1] * ts[T]) % mod;
	for (int S = 1; S < 1 << n; S++)
		for (int i = 0; i <= n; i++)
			for (int j = 0, pw = 1; j <= n; j++, pw = (long long)pw * i % mod)
				if (j % 2) gv[S][i] = (gv[S][i] + (long long)g[S][j] * pw) % mod;
				else gv[S][i] = (gv[S][i] + mod - (long long)g[S][j] * pw % mod) % mod;
	for (int i = 0; i <= n; i++) dp[0][i] = 1;
	for (int S = 1; S < 1 << n; S++)
		for (int T = S; T; T = (T - 1) & S)
			if (!(pre[T] & S))
				for (int i = 0; i <= n; i++)
					dp[S][i] = (dp[S][i] + (long long)dp[S ^ T][i] * gv[T][i]) % mod;
	vector<int> poly, tmp;
	poly.push_back(0);
	tmp.push_back(1);
	for (int i = 0; i <= n; i++) {
		vector<int> tmpm;
		tmpm.push_back(mod - i), tmpm.push_back(1);
		tmp = mul(tmp, tmpm);
	}
	for (int i = 0; i <= n; i++) {
		int c = dp[U][i];
		for (int j = 0; j <= n; j++)
			if (j != i) c = (long long)c * power((i - j + mod) % mod, mod - 2) % mod;
		poly = pls(poly, mul(div(tmp, i), c));
	}
	poly.push_back(0);

	for (int i = 0; i <= k + 1; i++)
		for (int j = 0; j <= i; j++)
			if (j == 0 || j == i) C[i][j] = 1;
			else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % mod;
	int ans = 0;
	for (int i = 1; i <= k + 1; i++)
		ans = (ans + (long long)poly[i] * fac[i] % mod * fac[k] % mod * C[k + 1][i]) % mod;

	f[0][0] = 1;
	for (int i = 1; i <= n + 1; i++)
		for (int j = 0; j <= k; j++) {
			if (j == 0) {f[i][j] = 1; continue;}
			if (j == 1) {f[i][j] = (long long)i * (k - j + 1) % mod; continue;}
			for (int o = 0; o <= i; o++) f[i][j] = (f[i][j] + f[o][j - 1]) % mod;
			f[i][j] = (long long)f[i][j] * (k - j + 1) % mod;
		}

	ans = (long long)ans * power((long long)fac[n] * f[n + 1][k] % mod, mod - 2) % mod;
	printf("%d\n", ans);

	return 0;
}

Day2T3 最长待机 sleep

还不会。

留言