2019杭电多校第八场

发表于 分类于 阅读次数： 本文字数： 9k 阅读时长 ≈ 8 分钟

这场又变得快乐了起来，首页最后一名，很快乐

1003. Acesrc and Good Numbers

solved at 02:48(+1)

不是很懂，队友oeis了9个数列打个表就过了... ## 1004. Acesrc and Hunting

solved at 04:16(+1)

给你一个\(n \ast m(1<=n, m<=100)\)的格点图，你可以任意选择起点，找到一条经过这\(n \ast m\)个点的汉密尔顿路，两点之间有边当且仅当它们的欧几里得距离在\((1,3)\)之间（不包含）

我们是这样做的，首先令\(n\)是\(n,m\)中的较小值，然后一些较小的情况特判掉(\(n\)为1的情况，n, m均为\(2\)的情况，m为5的情况)

然后把n分解成\(2 \ast x+3 \ast y\)其中\(y\)为0或1, 把m分解成\(3p+4q\)

如果\(y\)为1, 令3为最下面的横条（横坐标从左往右，纵坐标从下往上）

然后你会得到若干个\(2 \ast 3,2 \ast 4,3 \ast 3,3 \ast 4\)的矩形，对于这些矩形，分别找到一种方案可以遍历矩形内所有的点并且起点是左下角终点是右上角

然后从整个图的左下角开始（这时横条的长度可能是3或者是2)，从左往右处理当前横条，每次从小矩形的左下角遍历到右上角，再跳到右边的小矩形的左下角（这两点的距离是\(\sqrt　2\)或\(\sqrt 5\)，都是可以的），直到当前横条处理完毕，然后从当前横条的右上角跳到上面一个横条的右上角（距离肯定是\(2\))，然后把刚才的方法倒过来葱油往左遍历完这一横条，然后就可以继续按上述方法处理上面的横条一直到处理完了

一开始没输出YES wa了一发...

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
#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;

int n, m, f, T;
vector<pair<int, int>> ans;

pair<int, int> p23[6] = {mp(0, 0), mp(1, 1), mp(0, 2), mp(1, 0), mp(0, 1), mp(1, 2)};
pair<int, int> p24[8] = {mp(0, 0), mp(1, 1), mp(0, 3), mp(1, 2), mp(0, 1), mp(1, 0), mp(0, 2), mp(1, 3)};
pair<int, int> p33[9] = {mp(0, 0), mp(2, 1), mp(0, 2), mp(1, 1), mp(2, 0), mp(1, 2), mp(1, 0), mp(0, 1), mp(2, 2)};
pair<int, int> p25[10] = {mp(0, 0), mp(0, 2), mp(0, 4), mp(1, 3), mp(1, 1), mp(0, 3), mp(0, 1), mp(1, 0), mp(1, 2), mp(1, 4)};
pair<int, int> p34[12] = {mp(0, 0), mp(1, 2), mp(1, 0), mp(2, 1), mp(0, 2), mp(2, 0), mp(0, 1), mp(2, 2), mp(1, 3), mp(1, 1), mp(0, 3), mp(2, 3)};
pair<int, int> p35[15] = {mp(0, 0), mp(2, 1), mp(0, 2), mp(1, 1), mp(2, 0), mp(1, 2), mp(1, 0), mp(0, 1), mp(2, 2), mp(0, 3), mp(1, 4), mp(2, 3), mp(0, 4), mp(1, 3), mp(2, 4)};

void process(int dx, int dy, int f, int sz, pair<int, int> a[]) {
	if(f) {
		for(int i = sz - 1; ~i; --i)
			ans.push_back(mp(a[i].X + dx, a[i].Y + dy));
	}
	else {
		for(int i = 0; i < sz; ++i) 
			ans.push_back(mp(a[i].X + dx, a[i].Y + dy));
	}
}

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		f = 0;
		ans.clear();
		if(n > m) {
			swap(n, m);
			f ^= 1;
		}
		if(n == 1 && m == 1) {
			puts("YES");
			printf("1 1\n");
			continue;
		}
		if(n == 1) {
			puts("NO");
			continue;
		}
		if(n == 2 && m == 2) {
			puts("NO");
			continue;
		}
		if(n == 2 && m == 5) {
			process(1, 1, 0, 10, p25);
		}
		else if(n == 3 && m == 5) {
			process(1, 1, 0, 15, p35);
		}
		else if(n == 4 && m == 5) {
			process(1, 1, 0, 10, p25);
			process(3, 1, 1, 10, p25);
		}
		else if(n == 5 && m == 5) {
			process(1, 1, 0, 15, p35);
			process(4, 1, 1, 10, p25);
		}
		else {
			if(n & 1) {
				int p, q;
				for(p = 0; ; p++) {
					q = (m - 3 * p) / 4;
					if(3 * p + 4 * q == m)
						break;
				}
				int x = 1, y = 1;
				for(int i = 1; i <= p; ++i) {
					x = 1; y = 3 * (i - 1) + 1;
					process(x, y, 0, 9, p33);
				}
				for(int i = 1; i <= q; ++i) {
					x = 1; y = 3 * p + 4 * (i - 1) + 1;
					process(x, y, 0, 12, p34);
				}
				for(x = 5; x <= n; x += 4) {
					for(int i = q; i; --i) {
						y = 3 * p + 4 * (i - 1) + 1;
						process(x - 1, y, 1, 8, p24);
					}
					for(int i = p; i; --i) {
						y = 3 * (i - 1) + 1;
						process(x - 1, y, 1, 6, p23);
					}
					if(x + 2 <= n) {
						for(int i = 1; i <= p; ++i) {
							y = 3 * (i - 1) + 1;
							process(x + 1, y, 0, 6, p23);
						}
						for(int i = 1; i <= q; ++i) {
							y = 3 * p + 4 * (i - 1) + 1;
							process(x + 1, y, 0, 8, p24);
						}
					}
				}
			}
			else {
				int p, q;
				for(p = 0; ; p++) {
					q = (m - 3 * p) / 4;
					if(3 * p + 4 * q == m)
						break;
				}
				int x = 1, y = 1;
				for(; x <= n; x += 4) {
					for(int i = 1; i <= p; ++i) {
						y = 3 * (i - 1) + 1;
						process(x, y, 0, 6, p23);
					}
					for(int i = 1; i <= q; ++i) {
						y = 3 * p + 4 * (i - 1) + 1;
						process(x, y, 0, 8, p24);
					}
					if(x + 3 <= n) {
						for(int i = q; i; --i) {
							y = 3 * p + 4 * (i - 1) + 1;
							process(x + 2, y, 1, 8, p24);
						}
						for(int i = p; i; --i) {
							y = 3 * (i - 1) + 1;
							process(x + 2, y, 1, 6, p23);
						}
					}
				}
			}
		}
		puts("YES");
		if(f) {
			for(auto &t: ans) {
				printf("%d %d\n", t.Y, t.X);
			}
		}
		else {
			for(auto &t: ans) {
				printf("%d %d\n", t.X, t.Y);
			}
		}
	}
	return 0;
}

1006. Acesrc and Travel

solved at 03:06(+1)

有一颗树，每个点有两个权值\(a, b\)，两个人\(A, B\)用它玩游戏，有一个棋子，一开始\(A\)可以将棋子放在树上任意一个位置，然后\(B,A\)轮流移动，每次棋子到达一个点\(i\)(包括一开始放的位置)，\(A\)会获得\(a_i\), \(B\)会获得\(b_i\)，棋子不能重复到达同一位置，两人都想使得自己获得的总和比对方的尽可能地大，两人均采用最佳策略，求最后的差值

树型\(dp\)

第一遍\(dfs\)，处理出从每一个点开始，只能往子树方向走的最大值次大值最小值次小值以及取得它们时走的是哪个儿子

考虑到可能往父亲方向走是更优的，还需要第二遍\(dfs\)处理（这是就需要记录的次大值以防父亲的最优方案是往当前位置走）

注意到第二遍\(dfs\)时如果处理到叶子节点则只能往上走

tips:我的叫mx的数组实际上存的是最小值/次小值，mn是最大值/次大值

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

vector<int> G[N];

int a[N], b[N], T, n;

long long mxa[N][2], mnb[N][2], ans;
int posmxa[N][2], posmnb[N][2], f[N], x, y, root;

void dfs(int rt, int fa) {
	mxa[rt][0] = mxa[rt][1] = 1e18;
	mnb[rt][0] = mnb[rt][1] = -1e18;
	posmxa[rt][0] = posmxa[rt][1] = -1;
	posmnb[rt][0] = posmnb[rt][1] = -1;
	f[rt] = fa;
	for(auto j : G[rt]) {
		if(j == fa) continue;
		dfs(j, rt);
		if(mnb[j][0] + a[rt] - b[rt] < mxa[rt][1]) {
			mxa[rt][1] = mnb[j][0] + a[rt] - b[rt];
			posmxa[rt][1] = j;
		}
		if(mxa[rt][1] < mxa[rt][0]) {
			swap(mxa[rt][1], mxa[rt][0]);
			swap(posmxa[rt][1], posmxa[rt][0]);
		}
		if(mxa[j][0] + a[rt] - b[rt] > mnb[rt][1]) {
			mnb[rt][1] = mxa[j][0] + a[rt] - b[rt];
			posmnb[rt][1] = j;
		}
		if(mnb[rt][1] > mnb[rt][0]) {
			swap(mnb[rt][1], mnb[rt][0]);
			swap(posmnb[rt][1], posmnb[rt][0]);
		}
	}
	if(posmxa[rt][0] == -1) {
		mxa[rt][0] = mnb[rt][0] = a[rt] - b[rt];
	}
	// printf("mx[%d][0], mx[%d][1], px[%d][0], px[%d][1] = %lld, %lld, %d, %d\n", rt, rt, rt, rt, mxa[rt][0], mxa[rt][1], posmxa[rt][0], posmxa[rt][1]);
	// printf("mn[%d][0], mn[%d][1], pn[%d][0], pn[%d][1] = %lld, %lld, %d, %d\n", rt, rt, rt, rt, mnb[rt][0], mnb[rt][1], posmnb[rt][0], posmnb[rt][1]);
}

void dfs2(int rt, int fa) {
	if(fa != 0) {
		long long val, tmp = fa;
		if(posmnb[fa][0] == rt) {
			val = mnb[fa][1] + a[rt] - b[rt];
		}
		else {
			val = mnb[fa][0] + a[rt] - b[rt];
		}
		if(val < mxa[rt][1]) {
			mxa[rt][1] = val;
			posmxa[rt][1] = tmp;
		}
		if(mxa[rt][1] < mxa[rt][0]) {
			swap(mxa[rt][1], mxa[rt][0]);
			swap(posmxa[rt][1], posmxa[rt][0]);
		}
		if(posmxa[fa][0] == rt) {
			val = mxa[fa][1] + a[rt] - b[rt];
		}
		else {
			val = mxa[fa][0] + a[rt] - b[rt];
		}
		if(val > mnb[rt][1]) {
			mnb[rt][1] = val;
			posmnb[rt][1] = tmp;
		}
		if(mnb[rt][1] > mnb[rt][0]) {
			swap(mnb[rt][1], mnb[rt][0]);
			swap(posmnb[rt][1], posmnb[rt][0]);
		}
		// printf("mx[%d][0], mx[%d][1], px[%d][0], px[%d][1] = %lld, %lld, %d, %d\n", rt, rt, rt, rt, mxa[rt][0], mxa[rt][1], posmxa[rt][0], posmxa[rt][1]);
		// printf("mn[%d][0], mn[%d][1], pn[%d][0], pn[%d][1] = %lld, %lld, %d, %d\n", rt, rt, rt, rt, mnb[rt][0], mnb[rt][1], posmnb[rt][0], posmnb[rt][1]);
	}
	if(posmxa[rt][0] == -1) {
		swap(mxa[rt][0], mxa[rt][1]);
		swap(posmxa[rt][1], posmxa[rt][0]);
	}
	ans = max(ans, mxa[rt][0]);
	for(auto j : G[rt]) {
		if(j == fa) continue;
		dfs2(j, rt);
	}
}

int main() {
	scanf("%d", &T);
	while(T--) {
		ans = -1e18;
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i) {
			scanf("%d", &a[i]);
		}
		for(int i = 1; i <= n; ++i) {
			scanf("%d", &b[i]);
			G[i].clear();
		}
		for(int i = 1; i < n; ++i) {
			scanf("%d%d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		if(n <= 2) {
			ans = 0;
			for(int i = 1; i <= n; ++i)
				ans += a[i] - b[i];
			printf("%lld\n", ans);
			continue;
		}
		for(int i = 1; i <= n; ++i) {
			if(G[i].size() >= 2)
				root = i;
		}
		dfs(root, 0);
		dfs2(root, 0);
		printf("%lld\n", ans);
	}
	return 0;
}

1008. Andy and Maze

upsolved

在一张无向图中找到一条经过\(k\)个点（不含重复点）长为\(k-1\)的路径，使得边权和最大\(1<=n,m<=1e4,2<=k<=6\)

题解是随机染色，即给每一个点一个颜色，一共\(k\)种，然后假设答案的路径上的每一个点颜色都不一样，状压\(dp\)即可，假设正确的几率是\(k!/k^k\), 因为\(k\)很小时限又很长(15s)，跑个几百次就好了

还有一种做法是枚举起点每次\(dfs\) \(k\)层寻找答案，出题人说数据没造好 ，这种做法跑的飞快...

1009. Calabash and Landlord

solved at 01:52(+5)

给你两个横平竖直的矩形，问它们将平面分成了多少个区域

离散化\(dfs\)连通块数量就好了，再也不想分类讨论了....

1010. Quailty and CCPC

solved at 00:32(+2)

队友做的，不懂

1011. Roundgod and Milk Tea

solved at 00:42(+1)

\(n\)个班，每个班有\(a_i\)个人，一共制造了\(b_i\)杯奶茶，每人最多喝一杯奶茶，不能喝自己班制造的奶茶，求最多有多少个人能喝上奶茶

出题人说数据造弱了，并不知道自己是不是对的

我就是两个指针一个从左往右扫\(a\)一个从右往左扫\(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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

long long aa, bb, ans;

int T, n, a[N], b[N];

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		ans = aa = bb = 0;
		for(int i = 1; i <= n; ++i) {
			scanf("%d%d", &a[i], &b[i]);
		}
		int i = 1, j = n;
		while(i < j) {
			long long tmp = 0;
			while(i < j && a[i]) {
				if(b[j] >= a[i]) {
					b[j] -= a[i];
					tmp += a[i];
					a[i] = 0;
				}
				else {
					a[i] -= b[j];
					tmp += b[j];
					b[j] = 0;
					j--;
				}
			}
			ans += tmp;
			if(i == j) break;
			i++;
		}
		// cout << i << " " << j << endl;
		// cout << ans << endl;
		for(int k = 1; k < i; ++k) bb += b[k];
		for(int k = i + 1; k <= n; ++k) aa += a[k];
		long long tmp = min(bb, a[i] * 1LL);
		a[i] -= tmp; bb -= tmp; ans += tmp;
		tmp = min(aa, 1LL * b[i]);
		b[i] -= tmp; aa -= tmp; ans += tmp;
		ans += min(aa, bb);
		printf("%lld\n", ans);
	}
	return 0;
}