2022“杭电杯”中国大学生算法设计超级联赛（7）

Black Magic

题意
一共 n 个盒子，每个盒子左右两面分别为黑色或者白色。

如果两个相邻盒子的相邻面都是黑色，那么这两个盒子可以合为一个。

给定每个盒子左右面的颜色，问如何排列能够使得合并后的盒子个数最少或最多？
分别输出合并后，盒子的最小个数和最多个数。

$n<1e6$

思路
用 (0, 0), (1, 0), (0, 1), (1, 1) 来分别表示各个种类的盒子，1 代表黑色，0 代表白色。

先考虑最小：
让合并的盒子数尽可能多，那么就把 (1,1) 都合并成一个，然后 (0, 1)(1, 0) 合并成一个。如果存在一对 (0, 1)(1, 0) 的话，就把 (1, 1) 放到中间凑成一个。
最后不成对的 和 (0, 0) 单独加上。

再考虑最大：
有两种策略：
一种是 (1,1) | (0,1)(0,1)(0,1)... | (0,0) | (1,0)(1,0)(1,0)... | (1,1) | (0,0)(1,1)(0,0)...
另一种是 (1,0)(1,0)(1,0)... | (1,1) | (0,1)(0,1)(0,1)... | (0,0)(1,1)(0,0)(1,1)...
哪种策略更优呢？
如果此时有三个盒子 (1, 0) (0, 1) (1, 1)，如果按照第一种策略将会被合并成两个盒子，而按照第二种策略仍然是三个，所以用第二种策略来构造。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		
		if(b == 0 && c == 0){
			if(d) cout << a + 1 << " ";
			else cout << a << " ";
		}
		else{
			cout << min(b, c) + max(b, c) - min(b, c) + a << " ";
		}
		
		if(b && !c)
		{
			if(d <= a) cout << b + d + a << endl;
			else cout << b + 2 * a + 1 << endl;
		}
		else if(!b && c)
		{
			int ans = c;
			if(d) d--, ans ++;
			if(d <= a) ans += d + a;
			else ans += 2 * a;
			cout << ans << endl;
		}
		else
		{
			int ans = b + c;
			if(d) d--, ans ++;
			if(d <= a) ans += d + a;
			else ans += 2*a;
			cout << ans << endl;
		}
	}
	
	return 0;
}
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

---

Counting Stickmen

题意
给定一棵树，问该树中一共有多少种构成火柴人的方案？
一个火柴人：一个节点作为头，一个节点作为脖子，脖子相连四个节点作为手臂，脖子相连一个节点作为身体，身体连接两个节点作为腿。

思路
因为是无根树，任意选择一个节点作为根节点，那么火柴人的形状就不固定了，头不一定在深度最小的地方，手臂也可能在上面。

将根节点固定后，设每个点的儿子个数为其度数 -1。

枚举所有点 x 当作脖子，对于所有相邻节点 tx：

• 如果 tx 的儿子数大于等于 2 那么其可以作为身体，从所有儿子中选择两个作为两条腿；或者作为手臂，从所有儿子中选择两个作为手；或者作为头。
• 如果 tx 的儿子数大于等于 1，那么可以作为手臂。
• 如果 tx 没有儿子，那么只可以作为头。

对于节点 x 的相邻节点来说，从所有儿子数大于等于 2 的节点中选出一个当作身体，从其余的所有儿子数大于等于 1 的节点中选出两个作为手臂，再从其余的所有节点中选出一个作为头。作为身体的那个节点的所有儿子中要选出两个作为腿，作为手臂的两个节点要分别从所有儿子中选出一个作为手。

所以，遍历所有相邻节点作为身体，答案累加 作为身体的那个节点的所有儿子中要选出两个作为腿的方案数 * 从其余的所有儿子数大于等于 1 的节点中选出两个作为手臂并分别从其儿子中选出一个作为手的方案数 * 从剩下节点选一个作为头的方案数。

第一项 和 最后一项 好处理，关键在于第二项如何在 O(n) 的复杂度内完成。

预处理出所有节点两两作为手臂的方案，然后再减去以当前的身体 x 作为手臂的方案贡献，便是其余点两两作为手臂的方案：
把所有的儿子数大于等于1的节点存下来，手臂从这些点中产生，编号为 1 到 m。两两配对，那么总的方案数为 1 和 2 的儿子数相乘 + 1,3 儿子数相乘 + 1,4 + … + 1,m + 2,3 + 2,4 + …，即 a[1]*a[2] + a[1]*a[3] * a[1]*a[4] + a[2]*a[3] + a[2]*a[4] + a[3]*a[4] = a[1]*(a[2]+a[3]+a[4]) + a[2]*(a[3]+a[4]) + a[3]*(a[4])，预处理后缀 O(n)。
如果当前节点 x 作为手臂，那么应该删除 a[x] 的贡献。假设 x = 3，那么应删除 a[3] * (a[1] + a[2] + a[4])，预处理出总和便可O(1)求出以当前点作为身体时，其余所有点构成手臂的方案数。

因为是树，所以每个点最多遍历两次，时间复杂度 O(n)。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 500010, mod = 998244353;
int T, n, m;
int a[N];
int cnt_son[N];
int s[N];
int ans;
vector<int> e[N];
int f[N];

void init()
{
	for(int i=1;i<=n;i++) e[i].clear(), f[i] = 0;
}

int C(int x, int y)
{
	y = 2;
	return x * (x-1) / 2;
}

void bfs()
{
	queue<int> que;
	que.push(1);
	f[1] = 1;
	
	while(que.size())
	{
		int x = que.front(); que.pop(); //当前 x 作为脖子
		
		int idx = 0;
		for(int tx : e[x]){
			a[++idx] = tx;
			if(f[tx]) continue;
			f[tx] = 1;
			que.push(tx);
		}
		
		if(e[x].size() < 3) continue;
		
		int sum = 0, ss = 0;
		s[idx + 1] = 0;
		for(int i=idx;i>=1;i--) s[i] = s[i+1] + cnt_son[a[i]], ss += cnt_son[a[i]]; //预处理后缀和和总和
		for(int i=1;i<=idx;i++) sum = (sum + cnt_son[a[i]] * s[i+1] % mod) % mod; //两两配对作为手臂的总方案数
		
		for(int i=1;i<=idx;i++) //遍历所有节点作为身体
		{
			int tx = a[i];
			if(cnt_son[tx] >= 2)
			{
				int shou = (sum - cnt_son[tx] * (ss - cnt_son[tx]) % mod + mod) % mod; //其他所有点构成手臂的方案数为总方案数减去以当前点作为手臂时对手臂方案数的贡献
				int tans = C(cnt_son[tx], 2) % mod * shou % mod * (e[x].size() - 3) % mod; //身体节点的所有儿子中选两个的方案数 * 其余点作为手臂的方案数 * 其余点作为头的方案数
				ans = (ans + tans) % mod;
			}
		}
	}
}

signed main(){
	scanf("%lld", &T);
	while(T--)
	{
		scanf("%lld", &n);
		
		init();
		
		for(int i=1;i<n;i++)
		{
			int x, y; scanf("%lld%lld", &x, &y);
			e[x].push_back(y);
			e[y].push_back(x);
		}
		
		for(int i=1;i<=n;i++) cnt_son[i] = e[i].size() - 1;
		
		ans = 0;
		
		bfs();
		
		cout << ans << endl;
	}
		
	return 0;
}

/*
1
11
1 2
2 3
2 11
3 4
3 5
3 9
4 6
5 7
5 8
9 10

10
*/
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