https://vjudge.net/contest/413133

A - 9102

 

题意：有 n 个家庭，初始时每个家庭独自成为一个部落，m 个事件，5种事件：a 和 b 所在的部落合并；a 家庭被消灭；a 家庭从原本部落中离开并加入 b 所在部落；查询 a，b 是否在同一个部落；查询 a 所在部落的家庭数。每个事件还给出了这个事件所在的时间线，事件中的 kk 表示该事件发生在第 kk 个事件后。

dfs+离线+可撤销并查集

可持久化的结构可以尝试离线。

根据事件的依赖关系建出一棵树，dfs，当进入节点时让事件生效，当离开子树时撤销事件。

可撤销并查集通过给每个点建立一个马甲，并每次都对马甲操作，当某点的合并操作被撤销时，只要再新建一个马甲并舍弃旧的即可。

可撤销并查集不能路径压缩，例如，a 合并到 b 上，a 的子树中某个节点 c 又路径压缩直接连到了 b，这时撤销 a 的合并操作，但是 c 却仍然连在 b 上。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m;
vector<int>G[N];
int op[N], a[N], b[N], k[N], ans[N];
int par[N], f[N], rk[N], siz[N], tot;
void init(int n) {
	for (int i = 1; i <= n; i++)
		par[i] = f[i] = i, siz[i] = 1, rk[i] = 1; 
	tot = n;
}
int find(int x) { 
	if (x == -1)return -1;
	return par[x] == x ? x : find(par[x]);
}
void dfs(int u) {
	if (u == 0) {
		for (int v : G[u])dfs(v);
		return;
	}
	if (op[u] == 1) {
		if (f[a[u]] == -1 || f[b[u]] == -1) {
			for (int v : G[u])dfs(v);
			return;
		}
		int x = find(f[a[u]]), y = find(f[b[u]]);
		if (x == y) {
			for (int v : G[u])dfs(v);
			return;
		}
		if (rk[x] > rk[y])swap(x, y);
		par[x] = y;
		siz[y] += siz[x];
		int equ = 0;
		if (rk[x] == rk[y])rk[y]++, equ = 1;
		for (int v : G[u])dfs(v);
		par[x] = x;
		siz[y] -= siz[x];
		if (equ)rk[y]--;
	}
	else if (op[u] == 2) {
		if (f[a[u]] == -1) {
			for (int v : G[u])dfs(v);
			return;
		}
		int tmp = f[a[u]];
		siz[find(tmp)]--;
		f[a[u]] = -1;
		for (int v : G[u])dfs(v);
		f[a[u]] = tmp;
		siz[find(tmp)]++;
	}
	else if (op[u] == 3) {
		if (f[a[u]] == -1 || f[b[u]] == -1) {
			for (int v : G[u])dfs(v);
			return;
		}
		int fa = find(f[a[u]]), fb = find(f[b[u]]);
		if (fa == fb) {
			for (int v : G[u])dfs(v);
			return;
		}
		siz[fa]--;
		int tmp = f[a[u]];
		f[a[u]] = ++tot;
		siz[f[a[u]]] = 1;
		siz[fb]++;
		par[f[a[u]]] = fb;
		for (int v : G[u])dfs(v);
		f[a[u]] = tmp;
		siz[fa]++;
		siz[fb]--;
	}
	else if (op[u] == 4) {
		if (f[a[u]] == -1 || f[b[u]] == -1) {
			ans[u] = 0;
			for (int v : G[u])dfs(v);
			return;
		}
		ans[u] = (find(f[a[u]]) == find(f[b[u]]));
		for (int v : G[u])dfs(v);
	}
	else {
		if (f[a[u]] == -1) {
			ans[u] = 0;
			for (int v : G[u])dfs(v);
			return;
		}
		ans[u] = siz[find(f[a[u]])];
		for (int v : G[u])dfs(v);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	init(n);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &op[i]);
		if (op[i] == 1 || op[i] == 3 || op[i] == 4)scanf("%d%d%d", &k[i], &a[i], &b[i]);
		else scanf("%d%d", &k[i], &a[i]);
		G[k[i]].push_back(i);
	}
	dfs(0);
	for (int i = 1; i <= m; i++) {
		if (op[i] == 4)puts(ans[i] ? "Yes" : "No");
		else if (op[i] == 5)printf("%d\n", ans[i]);
	}
	return 0;
}

 

B - A Funny Bipartite Graph

 

题意：给定两个点集，每个点集 nn 个点，不同点集之间有连边，左边的点集有点权，保证左边每个点只会与右边下标比它大或等于它的点连边，且左边的点的度数在 11 到 33。给出了一些点对，要求子图中这些点对不能同时出现。要求选出一个子图，包含所有右边的点，子图的代价为子图中左边被选中的点的点权的度数幂次之和。问最小代价。

状压dp

很妙的状压。

如果要状压的话，肯定两边点集的状态都要状压，但这不可行。

但是可以发现由于左边的点只与下标比他大或等于他的点连边，所以对于第 ii 个点，考虑它时必须要保证右边 11 到 i−1i-1 都已经被连上了。

所以按顺序考虑左边的点如何连边时，右边下标小于它的点的状态就不需要保存了。

所以可以把两个状态压在一起，当考虑左边第 ii 个点时，S[1,i−1]S[1,i-1] 表示左边点集中有连边的点，S[i,n]S[i,n] 表示右边点集中被连边的点。

再由于每点度数很小，所以可以暴力分类讨论。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int T;
int n;
char G[100][100], a[100][100];
int dp[20][N];
int b[N];
vector<int>vc[100], bd[100];
int main() {
	scanf("%d", &T);
	while (T--) {
		memset(dp, 0x3f, sizeof(dp));
		scanf("%d", &n);
		for (int i = 0; i < n; i++)vc[i].clear(), bd[i].clear();
		for (int i = 0; i < n; i++)scanf("%s", G[i]);
		for (int i = 0; i < n; i++)scanf("%s", a[i]);
		for (int i = 0; i < n; i++)scanf("%d", &b[i]);
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (G[i][j] == '1')vc[i].push_back(j);
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (a[i][j] == '1')bd[i].push_back(j);
		for (int i = 0; i < n; i++)sort(vc[i].begin(), vc[i].end());
		if (G[0][0] != '1') {
			puts("-1");
			continue;
		}
		dp[0][1] = b[0];
		if (vc[0].size() == 2) {
			dp[0][1 | (1<<vc[0][1])] = min(dp[0][1 | (1 << vc[0][1])], b[0] * b[0]);
		}
		if (vc[0].size() == 3) {
			dp[0][1 | (1 << vc[0][1])] = min(dp[0][1 | (1 << vc[0][1])], b[0] * b[0]);
			dp[0][1 | (1 << vc[0][2])] = min(dp[0][1 | (1 << vc[0][2])], b[0] * b[0]);
			dp[0][1 | (1 << vc[0][1]) | (1 << (vc[0][2]))] = min(dp[0][1 | (1 << vc[0][1]) | (1 << (vc[0][2]))], b[0] * b[0] * b[0]);
		}
		for (int i = 1; i < n; i++) {
			for (int s = 0; s < (1 << n); s++) {
				if (s >> i & 1) {
					dp[i][s ^ (1 << i)] = min(dp[i][s ^ (1 << i)], dp[i - 1][s]);
					bool ck = 1;
					for (int v : bd[i])if ((s >> v & 1) && v < i) { ck = 0; break; }
					if (!ck)continue;
					for (int v : vc[i])dp[i][s | (1 << v)] = min(dp[i][s | (1 << v)], dp[i - 1][s] + b[i]);
					if (vc[i].size() == 2)
						dp[i][s | (1 << vc[i][0]) | (1 << vc[i][1])] = min(dp[i][s | (1 << vc[i][0]) | (1 << vc[i][1])], dp[i - 1][s] + b[i] * b[i]);
					if (vc[i].size() == 3) {
						dp[i][s | (1 << vc[i][0]) | (1 << vc[i][1])] = min(dp[i][s | (1 << vc[i][0]) | (1 << vc[i][1])], dp[i - 1][s] + b[i] * b[i]);
						dp[i][s | (1 << vc[i][0]) | (1 << vc[i][2])] = min(dp[i][s | (1 << vc[i][0]) | (1 << vc[i][2])], dp[i - 1][s] + b[i] * b[i]);
						dp[i][s | (1 << vc[i][1]) | (1 << vc[i][2])] = min(dp[i][s | (1 << vc[i][1]) | (1 << vc[i][2])], dp[i - 1][s] + b[i] * b[i]);
						dp[i][s | (1 << vc[i][0]) | (1 << vc[i][1]) | (1 << vc[i][2])] = min(dp[i][s | (1 << vc[i][0]) | (1 << vc[i][1]) | (1 << vc[i][2])], dp[i - 1][s] + b[i] * b[i] * b[i]);
					}
				}
				else {
					if (vc[i][0] != i)continue;
					else {
						bool ck = 1;
						for (int v : bd[i])if ((s >> v & 1) && v < i) { ck = 0; break; }
						if (!ck)continue;
						dp[i][s | (1 << i)] = min(dp[i][s | (1 << i)], dp[i - 1][s] + b[i]);
						if (vc[i].size() == 2) {
							dp[i][s | (1 << i) | (1 << vc[i][1])] = min(dp[i][s | (1 << i) | (1 << vc[i][1])], dp[i - 1][s] + b[i] * b[i]);
						}
						if (vc[i].size() == 3) {
							dp[i][s | (1 << i) | (1 << vc[i][1])] = min(dp[i][s | (1 << i) | (1 << vc[i][1])], dp[i - 1][s] + b[i] * b[i]);
							dp[i][s | (1 << i) | (1 << vc[i][2])] = min(dp[i][s | (1 << i) | (1 << vc[i][2])], dp[i - 1][s] + b[i] * b[i]);
							dp[i][s | (1 << i) | (1 << vc[i][1]) | (1 << vc[i][2])] = min(dp[i][s | (1 << i) | (1 << vc[i][1]) | (1 << vc[i][2])], dp[i - 1][s] + b[i] * b[i] * b[i]);
						}
					}
				}
			}
		}
		int ans = INF;
		for (int i = 0; i < (1 << n); i++)ans = min(ans, dp[n - 1][i]);
		printf("%d\n", ans == INF ? -1 : ans);
	}
	return 0;
}

 

C - And and Pair

 

题意：给定一个01串形式的 n，0≤j≤i≤n，i&n=i,i&j=00\leq j\leq i\leq n，i\& n=i,i\&j=0，求满足条件的数对 (i,j)(i,j)。

二项式定理

发现 ii 必须要是 nn 的子集，且 i≤ni\le n 必定成立。

对于确定的 ii，要使得 i&j=0i\&j=0，则 jj 只能有 2cnt02^{cnt0} 种可能，其中 cnt0cnt0 为 ii 中 00 的个数。

所以枚举 nn 的每一位，作为 ii 的最高位，再选出几位为 11 变成 00，就确定了 ii，此时数对的个数为 ∑j=0cnt1[i+1]Ccnt1[i+1]j⋅2cnt0[i+1]+j\sum_{j=0}^{cnt1[i+1]}C_{cnt1[i+1]}^j\cdot 2^{cnt0[i+1]+j}。其中 cnt1[i]cnt1[i] 表示 s[i⋯n]s[i\cdots n] 中 11 的个数。

∑j=0cnt1[i+1]⋅2cnt0[i+1]+j=2cnt0[i+1]∑j=0cnt1[i+1]Ccnt1[i+1]j⋅2j=2cnt0[i+1]⋅3cnt1[i+1]\begin{align} & \sum_{j=0}^{cnt1[i+1]}\cdot 2^{cnt0[i+1]+j}\\ &= 2^{cnt0[i+1]}\sum_{j=0}^{cnt1[i+1]}C_{cnt1[i+1]}^j\cdot 2^j\\ &= 2^{cnt0[i+1]}\cdot 3^{cnt1[i+1]}\\ \end{align}

最后一步用二项式定理化简。

二进制枚举子集的复杂度也是二项式定理化简得到的。

看到 ∑\sum，CC，aia^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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int T;
char s[N];
ll p2[N], p3[N];
int main() {
	scanf("%d", &T);
	p2[0] = p3[0] = 1;
	for (int i = 1; i < N; i++)p2[i] = p2[i - 1] * 2 % mod, p3[i] = p3[i - 1] * 3 % mod;
	while (T--) {
		scanf("%s", s + 1);
		int n = strlen(s + 1);
		int cnt1 = 0, cnt0 = 0;
		ll ans = 1;
		for (int i = n; i >= 1; i--) {
			if (s[i] == '1') {
				ans = (ans + p2[cnt0] * p3[cnt1] % mod) % mod;
				cnt1++;
			}
			else {
				cnt0++;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

 

K - Tree

 

题意：给定一棵有根树和 kk，点权 0≤ai≤n0 \le a_i \le n，问有几个点对 (u,v)(u,v) 满足：LCA(u,v)≠u≠vLCA(u,v)\neq u\neq v，au+av=2⋅aLCA(u,v)a_u+a_v=2\cdot a_{LCA(u,v)} ，dist(u,v)≤kdist(u,v)\le k。

树上启发式合并+动态开点线段树

启发式合并先计算轻儿子，再计算重儿子，再计算轻儿子。最后一次计算轻儿子时统计答案。

对于每一个权值开一棵线段树，记录权值为它的点的深度，dfs每一个点作为 LCA(u,v)LCA(u,v)，则对于 uu，符合条件的 vv 的深度是一个区间，线段树维护区间上点的个数。

第一次计算轻儿子后要递归去除痕迹，第二次算轻儿子的时候更新答案并递归合并进线段树。

动态开点线段树其实只是在普通线段树外显式维护左右儿子，只有当用到时才开点。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n, k;
int a[N];
vector<int>G[N];
#define mid ((l+r)>>1)
#define lson l,mid,lc[rt]
#define rson mid+1,r,rc[rt]
int T[N], tr[N * 40], lc[N * 40], rc[N * 40], tot;
int siz[N], dep[N], son[N];
ll ans;
void up(int rt) {
	tr[rt] = tr[lc[rt]] + tr[rc[rt]];
}
void upd(int q, int x, int l, int r, int& rt) {
	if (!rt)rt = ++tot;
	if (l == r) {
		tr[rt] += x;
		return;
	}
	if (q <= mid)upd(q, x, lson);
	else upd(q, x, rson);
	up(rt);
}
int qry(int ql, int qr, int l, int r, int rt) {
	if (!rt)return 0;
	if (ql <= l && qr >= r)return tr[rt];
	int ans = 0;
	if (ql <= mid)ans += qry(ql, qr, lson);
	if (qr > mid)ans += qry(ql, qr, rson);
	return ans;
}
void dfsdel(int u) {
	upd(dep[u], -1, 1, n, T[a[u]]);
	for (int v : G[u]) {
		dfsdel(v);
	}
}
void dfsadd(int u) {
	upd(dep[u], 1, 1, n, T[a[u]]);
	for (int v : G[u]) {
		dfsadd(v);
	}
}
void ask(int u, int z) {
	int r = 2 * dep[z] + k - dep[u];
	if (r < 1)return;
	ans += 2 * qry(1, r, 1, n, T[2 * a[z] - a[u]]);
	for (int v : G[u]) {
		ask(v, z);
	}
}
void dfs1(int u) {
	siz[u] = 1;
	for (int v : G[u]) {
		dep[v] = dep[u] + 1;
		dfs1(v);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])son[u] = v;
	}
}
void dfs2(int u) {
	for (int v : G[u]) {
		if (v == son[u])continue;
		dfs2(v);
		dfsdel(v);
	}
	if (son[u])dfs2(son[u]);
	for (int v : G[u]) {
		if (v == son[u])continue;
		ask(v, u);
		dfsadd(v);
	}
	upd(dep[u], 1, 1, n, T[a[u]]);
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 2; i <= n; i++) {
		int f;
		scanf("%d", &f);
		G[f].push_back(i);
	}
	dep[1] = 1;
	dfs1(1);
	dfs2(1);
	printf("%lld\n", ans);
	return 0;
}