2021训练联盟热身训练赛第一场

字数统计: 3k字   |   阅读时长: 15分
训练题解
solved A B C D E F G H I J K
8 / 11 O Ø · O Ø O · O Ø O ·
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

REPLY： 参与了三题TLE，收获很大[doge] —— lllllan

比赛链接

A. Weird Flecks, But OK

solved by Tryna. 0:52(+)

题意： 在一个三维的立方体中有nn个点，我们有一个圆锥，想要碰到所有点，并且只能平行三个坐标轴插入。问这个圆锥的最小横截面的直径。

题解： 从xx轴，yy轴，zz轴三个方向跑三遍二维的最小圆覆盖取minmin就是答案了

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
const int maxn = 5e3 + 10;
#define inf 0x3f3f3f3f
int n;
int sgn(double x) {
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}
struct Point{
	double x, y, z;
}p[maxn], pp[maxn];
double Distance(Point A, Point B) {
	return hypot(A.x - B.x, A.y - B.y);
}
Point circle_center(const Point a, const Point b, const Point c) {
	Point center;
	double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
	double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
	double d = a1 * b2 - a2 * b1;
	center.x = a.x + (c1 * b2 - c2 * b1) / d;
	center.y = a.y + (a1 * c2 - a2 * c1) / d;
	return center;
}
void min_cover_circle(Point *p, int n, Point &c, double &r) {
	random_shuffle(p, p + n);
	c = p[0]; r = 0;
	for(int i = 1; i < n; i++) {
		if(sgn(Distance(p[i], c) - r) > 0) {
			c = p[i]; r = 0;
			for(int j = 0; j < i; j++) {
				if(sgn(Distance(p[j], c) - r) > 0) {
					c.x = (p[i].x + p[j].x) / 2;
					c.y = (p[i].y + p[j].y) / 2;
					r = Distance(p[j], c);
					for(int k = 0; k < j; k++) {
						if(sgn(Distance(p[k], c) - r) > 0) {
							c = circle_center(p[i], p[j], p[k]);
							r = Distance(p[i], c);
						}
					}
				}
			}
		}
	}
}
int main() {
	Point c; double r;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%lf %lf %lf", &pp[i].x, &pp[i].y, &pp[i].z);
	double ans = inf;
	for(int i = 0; i < n; i++) {
		p[i].x = pp[i].x;
		p[i].y = pp[i].y;
	}
	min_cover_circle(p, n, c, r);
	ans = min(ans, r * 2);
//	printf("%.10f\n", ans);
	for(int i = 0; i < n; i++) {
		p[i].x = pp[i].y;
		p[i].y = pp[i].z;
	}
	min_cover_circle(p, n, c, r);
	ans = min(ans, r * 2);
//	printf("%.10f\n", ans);
	for(int i = 0; i < n; i++) {
		p[i].x = pp[i].x;
		p[i].y = pp[i].z;
	}
	min_cover_circle(p, n, c, r);
	ans = min(ans, r * 2);	
	printf("%.10f\n", ans);
	return 0;
}

B Code Names

solved by Sstee1XD & lllllan. (-)

题意： 两个不相同的字符串，如果可以通过调换某个字符串中两个字符的位置而使得两个字符串相同的，属于swap-free。现在要求从若干个不相同的字符串中选择尽可能多的字符串，满足两两之间都不满足swap-free的概念。

题解： 逆向思维！！！题目要求找不满足swap-free的字符串，我们就反过来找满足swap-free的字符串。除了所有能满足swap-free的字符串，剩下的所有字符两两之间一定都不满足swap-free。而且还可以把所有满足swap-free的字符串对拆开，选择其一即可。

做法就是求满足swap-free的最大二分图匹配maxx，而题目的答案则为n−maxx/2n - maxx / 2

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e2 + 10;

#define pb push_back
#define rep(i,a,n) for (int i = (a); i <= (n); ++i)

int n;
char G[maxn][30];
int vis[maxn];
int match[maxn];
vector<int> V[maxn];

int dfs (int u) {
	for (int v : V[u]) {
		if (vis[v]) continue;
		vis[v] = 1;
		if (!match[v] || dfs(match[v])) {
			match[v] = u;
			return 1;
		}
	}
	return 0;
}

int main () {
	scanf("%d", &n);
	rep (i, 1, n) scanf("%s", G[i]);
	
	int len = strlen(G[1]);
	rep (i, 1, n) rep(j, i + 1, n) {
		int num = 0;
		rep (k, 0, len - 1) num += (G[i][k] != G[j][k]);
		if (num == 2) V[i].pb(j), V[j].pb(i);
	}
	
	int ans = 0;
	rep (i, 1, n) {
		memset(vis, 0, sizeof vis);
		if (dfs(i)) ans++;
	}
	printf("%d\n", n - ans / 2);
	return 0;
}

D. Some Sum

solved by Tryna. 0:11(+)

题意： 给出一个nn，问nn个连续的和是什么数，如果是奇数输出OddOdd, 如果是偶数输出EvenEven, 如果都有可能就是EitherEither

题解： 对nn取模44，答案是22输出OddOdd, 答案是00输出EvenEven,其他情况则是EitherEither。

AC代码 
1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
	cin>>n;
	if(n % 4 == 2) puts("Odd");
	else if(n % 4 == 0) puts("Even");
	else puts("Either");
	return 0;
}

E. Early Orders

Solved by Sstee1XD. (-)

题意： 有nn张纸牌，你需要从中不改变顺序的情况下取出kk个，要求满足是11~kk的一种排列，并且字典序最小。

思路： 考虑建立一个答案数组，我们遍历纸牌数组，每次选择要不要让当前这张纸牌加入答案里面。那么选择的依据是什么呢？不太好想。那能否考虑先放进去再调整呢？如果答案序列里还没有当前这张纸牌数字的纸牌，我们就先将这张纸牌加入到我们的答案里，同时对已经在答案里的纸牌进行调整。如果当前答案最后的纸牌数字比我们要加入的纸牌数字要大，而且后面还有当前答案最后的纸牌数字的纸牌，我们肯定能贪心地让这张纸牌出去，之后再放进来。由此形成了一个单调栈。

AC代码 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

int ans[N], tot;
int n, k, a[N], num[N], vis[N];

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		num[ a[i] ]++;
	}
	for (int i = 1; i <= n; ++i) {
		while (tot && !vis[ a[i] ] && a[i] <= ans[tot] && num[ ans[tot] ]) {
			vis[ ans[tot] ]--;
			tot--;
		}
		num[ a[i] ]--;
		if (!vis[ a[i] ]) {
			ans[++tot] = a[i];
		    vis[ a[i] ]++;
		}
		
	}
	for (int i = 1; i <= k; ++i) {
		printf("%d%c", ans[i], " \n"[i == k]);
	}
	return 0;
}

F. Pulling Their Weight

Solved by lllllan & Sstee1XD. 0:54(+)

题意： 现有n个动物，每个动物有它的体重，我们要求出一个最小的体重，满足所有严格小于这个体重的动物的体重和，等于严格大于这个体重的动物的体重和。

思路： 将动物的体重从小到大排列，考虑前缀和与后缀和，O(n)checkO(n)check或者二分checkcheck均可。

AC代码 
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
#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 7;
const int M = 1e5 + 7;

int m;
int num[N], pre[N], suf[N];

int main() {
	int ans = 0;
	scanf("%d", &m);
	for (int i = 1, t; i <= m; ++i) {
		scanf("%d", &t);
		num[t]++;
	}
	for (int i = 1; i <= 20000; ++i) {
		pre[i] = pre[i - 1] + num[i] * i;
	}
	for (int i = 20000; i >= 1; --i) {
		suf[i] = suf[i + 1] + num[i] * i;
	}
	int l = 1, r = 20000, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (pre[mid - 1] >= suf[mid + 1]) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	printf("%d\n", ans);
	return 0;
}

H On Average They’re Purple

solved by lllllan. 00:35(+)

题意： n点m边的无向图，如果有路径1->2->3上两条边的染色不同，则称为一次“变色”。要求给这个图染色，使得从点1出发到点
n的变色次数最多，输出次数。

题解： 一道披着染色面纱的最短路题目。决定最后答案的，其实只有从点1到点n的最短路，因为你其他路径设置的再好，人家只走最短路你也没辙。在最短路径上，两两相邻的边染成不同颜色即可，如此一来变色次数即为最短路距离- 1.

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int n, m;

int vis[maxn];

int cnt, head[maxn];
struct edge { int v, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}; head[u] = cnt;
	e[++cnt] = {u, head[v]}; head[v] = cnt;
}

struct node { int id, dis; } ;

void BFS () {
	queue<node> Q;
	
	Q.push({1, 0}); vis[1] = 1;
	
	while (Q.size()) {
		node u = Q.front(); Q.pop();
		if (u.id == n) return (void)(printf("%d\n", u.dis - 1));
		for (int i = head[u.id]; i; i = e[i].next) {
			int v = e[i].v;
			if (vis[v]) continue;
			vis[v] = 1;
//			printf("%d -> %d\n", u.id, v);
			Q.push({v, u.dis + 1});
		}
	}
	printf("0\n");
}

int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	BFS();
	return 0;
}

I Full Depth Morning Show

solved by lllllan. (-)

题意： 一棵树上，既有点权tit_i，也有边权wiw_i。点i到点j的花费等于点i到点j路上的所有边权和∗(i的点权+j的点权)点i到点j的花费等于点i到点j路上的所有边权和*(i的点权 + j的点权)，记为costi,j=∑ki−>jwk∗(ti+tj)cost_{i,j} =\sum_k^{i->j}w_k * (t_i + t_j)。求每个点到所有点的花费和。

题解： 信誓旦旦地去写了LCA，通过LCA求每两点间的边权和，然后求花费。呵呵，1e5个点，不TLE才怪

要利用树形DP求解，为了方便状态转移，就需要将花费拆成两个部分，点u去到所有点的花费为：

  • dp[0][u] =点u去到所有点需要花费的所有边权和
  • dp[1][u] =点u去到所有点需要花费的（所有边权和 * t[v])的和
  • cost[u] = dp[0][u] * t[u] + dp[1][u]
AC代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;

int n;
ll t[maxn];
ll sz[maxn];
ll sum_t[maxn];
ll dp[2][maxn];

int cnt, head[maxn];
struct edge { int v, w, next; } e[maxn << 1];
void add (int u, int v, int w) {
	e[++cnt] = {v, w, head[u]}; head[u] = cnt;
	e[++cnt] = {u, w, head[v]}; head[v] = cnt;
}

void dfs (int u, int fa) {
	sz[u] = 1, sum_t[u] = t[u];
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (v == fa) continue;
		dfs(v, u);
		dp[0][u] += dp[0][v] + sz[v] * w;
		dp[1][u] += dp[1][v] + sum_t[v] * w;
		sz[u] += sz[v];
		sum_t[u] += sum_t[v];
	}
}

void DFS (int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (v == fa) continue;
		dp[0][v] = dp[0][u] + (sz[1] - 2 * sz[v]) * w;
		dp[1][v] = dp[1][u] + (sum_t[1] - 2 * sum_t[v]) * w;
		DFS(v, u);
	}
}

int main () {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%lld", t + i);
	for (int i = 1; i <  n; ++i) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
	}
	dfs(1, 0);
	DFS(1, 0);
	for (int i = 1; i <= n; ++i) printf("%lld\n", dp[0][i] * t[i] + dp[1][i]);
	return 0;
}

J. This Ain’t Your Grandpa’s Checkerboard

Solved by Sstee1XD. 0:13(+)

思路： 签到，这里没多想直接暴力模拟了。

AC代码 
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
#include <bits/stdc++.h>

using namespace std;

int n;
char s[107][107];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", s[i] + 1);
	}
	
	int num = -1;
	for (int i = 1; i <= n; ++i) {
		int tmp = num;
		for (int j = 1; j <= n; ++j) {
			if (s[i][j] == 'B') tmp--;
		}
		if (num != -1 && tmp != 0) {
			puts("0");
			return 0;
		}
		if (num == -1) num = -tmp - 1;
	}
	
	num = -1;
	for (int j = 1; j <= n; ++j) {
		int tmp = num;
		for (int i = 1; i <= n; ++i) {
			if (s[i][j] == 'B') tmp--;
		}
		if (num != -1 && tmp != 0) {
			puts("0");
			return 0;
		}
		if (num == -1) num = -tmp - 1;
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n - 2; ++j) {
			int num = 1;
			for (int k = j + 1; k <= j + 2; ++k) {
				if (s[i][k] != s[i][k - 1]) break;
				if (k == j + 2) {
					puts("0");
			    	return 0;
				}
			}
		}
	}
	
	for (int j = 1; j <= n; ++j) {
		for (int i = 1; i <= n - 2; ++i) {
			int num = 1;
			for (int k = i + 1; k <= i + 2; ++k) {
				if (s[k][j] != s[k - 1][j]) break;
				if (k == i + 2) {
					puts("0");
			    	return 0;
				}
			}
		}
	}
	puts("1");
	return 0;
}
文章目录
  1. A. Weird Flecks, But OK
  2. B Code Names
  3. D. Some Sum
  4. E. Early Orders
  5. F. Pulling Their Weight
  6. H On Average They’re Purple
  7. I Full Depth Morning Show
  8. J. This Ain’t Your Grandpa’s Checkerboard
|