The 18th Zhejiang Provincial Collegiate Programming Contest

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

比赛链接

A - League of Legends

solved by Tryna.0:04(+)

题解： 签到题

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double eps = 1e-8;
const int maxn = 1e2 + 10;
const int mod = 1e9 + 7;
int n;

void solve(){
	ll b = 0, r = 0;
	for(int i = 1; i <= 5; i++) {
		ll x;
		scanf("%lld", &x);
		b += x;
	}
	for(int i = 1; i <= 5; i++) {
		ll x;
		scanf("%lld", &x);
		r += x;
	}
	if(b >= r) puts("Blue");
	else puts("Red");
}

int main() {
    // freopen("tests.in","r",stdin);
	int t = 1;
	// scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

C - Cube

solved by Tryna.0:26(+)

题意： 给出三维空间中的88个点，问能不能构成正立方体。

题解： 我们枚举每两个点之间的距离，一共有5656条，边的长度只有三种情况，他们的比例为1：2:31：\sqrt{2} : \sqrt{3}, 且它们的数量分别为24、24、824、24、8。

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;
typedef long long ll;

const int maxn = 1e5 + 7;
const double eps = 1e-8;

int sgn(double x) {
	if(fabs(x) < eps) return 0;
	if(x < 0) return -1;
	else return 1;
}

struct Point{
	double x, y, z;
	Point(double _x = 0, double _y = 0, double _z = 0) {
		x = _x;
		y = _y;
		z = _z;
	}
	Point operator - (const Point &b)const{
		return Point(x - b.x, y - b.y, z - b.z);
	}
	double distance(Point b) {
		return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y) + (z - b.z) * (z - b.z));
	}	
}p[20];



void run() {
	for(int i = 1; i <= 8; i++)
		scanf("%lf %lf %lf", &p[i].x, &p[i].y, &p[i].z);
	map<double, int>mp;
	for(int i = 1; i <= 8; i++) {
		for(int j = 1; j <= 8; j++) {
			if(i == j) continue;
			double tmp = p[i].distance(p[j]);
			mp[tmp]++;
		}
	}
	int flag = 0;
//	for(auto g : mp) {
//		printf("*%f %d\n", g.first, g.second);
//	}
	for(auto g : mp) {
		if(g.second == 24) flag++;
		if(g.second == 8 && flag == 2) flag++;
	}
	if(flag < 3) {
		puts("NO");
		return ;
	}
	double last = 0;
	flag = 0;
	for(auto g : mp) {
		if(last == 0) {
			last = g.first;
			continue;
		}
//		printf("*%f\n", last);
		if(sgn(last * sqrt(2) - g.first) == 0 || sgn(last * sqrt(3) - g.first) == 0)
			flag++;
	}
	if(flag == 2) puts("YES");
	else puts("NO");
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) run();
	return 0;
}

D - Shortest Path Query

solved by lllllan.(-)

题意： 给定一个有向图，两点的最短距离。给定的图中的所有边，其中min(u,v)min(u,v)二进制下是max(u,v)max(u,v)的前缀

题解： 全部的有效信息就是这个前缀了。

  • 利用这个信息，将无向边留下一条从min(u,v)min(u,v)到max(u,v)max(u,v)的优先边即可。
  • 如此一来，拎起点1，整个图就变成了一棵有向树。再依次对所有的节点，求出到子树中的所有点的最短路。
  • 问某两个点的最短路，该最短路必定经过他们的lca，至于是那个lca，一共不过20个，此处暴力即可。

细节看代码，真学习还得上VJ偷学大佬的优秀代码

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

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 10;

int n, m, q;
ll d[maxn];
ll dis[maxn][20];
vector<pair<int, ll> > G[maxn];

void init (int u) {
	if (u > n) return; d[u] = 1e16;
	init(u << 1); init(u << 1 | 1);
}

void dfs (int u, int dep = 0) {
	if (u > n) return; dis[u][dep] = d[u];
	dfs(u << 1, dep + 1); dfs(u << 1 | 1, dep + 1);
}

void Dij (int s) {
	init(s);
	priority_queue<pair<ll, int>> Q;
	Q.emplace(0, s); d[s] = 0;
	while (Q.size()) {
		auto [dist, u] = Q.top(); Q.pop();
		dist = -dist;
		if (d[u] < dist) continue;
		for (auto [v, w] : G[u]) {
			if (s <= v && d[v] > d[u] + w) {
				d[v] = d[u] + w;
				Q.emplace(-d[v], v);
			}
		}
	}
	dfs(s);
}

int gao (int x) { return x ? gao(x / 2) + 1 : 0; }

void run () {
	int u, v;
	scanf("%d%d", &u, &v);
	int x = gao(u) - 1;
	int y = gao(v) - 1;
		
	ll ans = 1e16;
	for (; x >= 0 && y >= 0; --x, --y) {
		if ((u >> x & 1) ^ (v >> y & 1)) break;
		ans = min(ans, dis[u][x] + dis[v][y]);
	}
	if (ans > 1e16 / 2) ans = -1;
	printf("%lld\n", ans);
}

int main () {	
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].emplace_back(v, w);
		G[v].emplace_back(u, w);
	}
	
	for (int i = 1; i <= n; ++i) Dij(i);
		
	scanf("%d", &q);
	while (q--) run();
	
	return 0;
}

F - Fair Distribution

solved by Tryna.3:50(+3)

题意： 给出两个数n和mn和m, 我们每次可以对nn进行减一操作或者对mm进行加一操作，问能使m%n=0m\%n = 0的最少操作数量。

题解： 比如样例中的8和208和20，我们这么考虑，首先求出一个倍数mulmul，满足8∗mul>=208 * mul >= 20，这个样例中的mul=3mul = 3，我们设num=mul∗nnum = mul * n，所以我们现在要使num变成20num变成20，我们首先考虑将nn变小，因为nn减一相当于num−mulnum - mul，一步操作就等于mulmul步操作。所以不难得出答案res=(num−m)%mul+(num−m)/mulres = (num - m) \% mul + (num - m) / mul。
但这样就一定是最小的了吗？
比如说3 103\ 10，按照我们的算法，得到的步数是22，但实际上是11，首先将33变成22，他就能被mm整除了。这是因为3和23 和 2对于1010的mulmul是不同的。通过观察7 207\ 20和8 208\ 20这两组样例我们可以发现，n先减和后减是没有区别的，因为他们的mulmul没有改变，而2 102\ 10和3 103\ 10的mulmul发生改变了，所以就得分开运算取minmin。
说到这里就已经很明显了，我们运用除法的性质进行整除分块，就能得到不同的mulmul对应的答案了。时间复杂度为O(T∗n)O(T*\sqrt{n})。

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

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 7;

ll n, m;

void run() {
	scanf("%lld %lld", &n, &m);
	if (n >= m) {
		printf("%lld\n", n - m);
		return;
	}
	if (m % n == 0) {
		puts("0");
		return;
	}
	ll ans = n - 1;
	for(ll l = 2, r; l <= m; l = r + 1) {
		r = m / (m / l);
		r = min(r, n);
		ll tmp = n - r;
		ll mul = 1;
		mul = (m + r - 1) / r;
		ll a = (r * mul - m) / mul;
		ll b = (r * mul - m) % mul;
		ans = min(ans, tmp + a + b);
		if(r == n) break;	
	}
	printf("%lld\n", ans);
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) run();
	return 0;
}

G - Wall Game

solved by Sstee1XD & lllllan. 04:08(+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
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll x, y;

const ll add = 1e9;
const int N = 5e5 + 7;

int del[N];
int id[N];
ll a[N];
ll b[N];
int q;
int op[N];
int ds[N];
int num[N];
int s[N];

int find (int x) {
	if (s[x] != x) {
		s[x] = find(s[x]);

		num[ s[x] ] += num[x];
		num[x] = 0;
		del[ s[x] ] += del[x];
		del[x] = 0;
	}

	return s[x];
}

void un (int a, int b) {
	int sa = find(a), sb = find(b);
	if (sa != sb) {

		num[sa] += num[sb];
		num[sb] = 0;

		del[sa] += del[sb];
		del[sb] = 0;

		s[sb] = sa;
	}

	del[sa] += 1;
}

bool in(ll tmp, int tt) {
	int u = lower_bound(b + 1, b + 1 + q, tmp) - b;
	if (u > q) return false;
	if (b[u] != tmp) return false;
	if (ds[u] > tt) return false;
	
	return true;
}

ll dir[][2] = {{1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 0}, {-1, 1}};
void run(int tt) {

	if (op[tt] == 1) {
		int u = id[tt];
		num[u] = 1, del[u] = 0;
		ll val = a[tt];
		for (int i = 0; i < 6; ++i) {
			ll tmp = val;
			if (dir[i][0] == 1) {
				tmp += add;
			} else if (dir[i][0] == -1){
				tmp -= add;
			}
			if (dir[i][1] == 1) {
				tmp += 1;
			} else if (dir[i][1] == -1){
				tmp -= 1;
			}
			
			if (in(tmp, tt)) {
				un(u, lower_bound(b + 1, b + 1 + q, tmp) - b);
			}
		}
	} else {
		int u = find(id[tt]);
		printf("%lld\n", num[u] * 6 - del[u] * 2);
	}

}

int main() {
	int t = 1;
	scanf("%d",&t);
	for (int i = 1; i <= t; ++i) {
		scanf("%d%lld%lld", &op[i], &x, &y);
		x += add;
		y += add;
		ll tem = (x - 1) * add + y;
		a[i] = tem;
		b[i] = tem;
		s[i] = i;
	}
	sort(b + 1, b + 1 + t);
	q = unique(b + 1, b + 1 + t) - b - 1;
	
	for (int i = 1; i <= t; ++i) {
		id[i] = lower_bound(b + 1, b + 1 + q, a[i]) - b;
		if (!ds[ id[i] ]) ds[ id[i] ] = i;
	}
	for (int i = 1; i <= t; ++i) run(i);
	return 0;
}

J - Grammy and Jewelry

solved by lllllan. 01:10(+1)

题意： 给定一个无向图，每个点都有对应权值。规定每过一条边花费一个体力，并且一次只能携带一个点的权值，每个点的权值可以无限获取。拥有K点体力从点1出发收集权值回到点1，最多可以收集多少权值。

题解：

  • 一次携带一个点的权值，但是每个点的权值都可以重复获取。
  • 拥有一定的体力，走一条边花费一点体力。
  • 多重背包。 先跑一遍BFS，记录到达每个点能获得的权值以及需要消耗的体力。再套一个完全背包即可。
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
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 3e3 + 10;

int n, m, q;

int a[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;
}

int vis[maxn];
int dis[maxn];
int val[maxn << 1];
void BFS () {
	queue<int> Q;
	
	Q.push(1); vis[1] = 1;
	while (Q.size()) {
		int u = Q.front(); Q.pop();
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if (vis[v]) continue;
			vis[v] = 1;
			dis[v] = dis[u] + 1;
			if (val[dis[v] * 2] < a[v]) val[dis[v] * 2] = a[v];
			Q.push(v);
		}
	}
}

int dp[maxn];
int v[maxn << 1];
int w[maxn << 1];

void run() {
	
	scanf("%d%d%d", &n, &m, &q);
	
	for (int i = 2; i <= n; ++i) scanf("%d", a + i);
	
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	
	BFS();
	
	int tot = 0;
	for (int i = 1; i <= n << 1; ++i) {
//		printf("%d\n", val[i]);
		if (val[i]) {
			++tot;
			v[tot] = i;
			w[tot] = val[i];
		}
	}
		
	dp[0] = 0;
	for (int i = 1; i <= tot; ++i) {
		for (int j = v[i]; j <= q; ++j) {
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	
	int ans = 0;
	for (int i = 1; i <= q; ++i) {
		ans = max(ans, dp[i]);
		printf("%d ", ans);
	}
}

int main() {
	int t = 1;
//	scanf("%d", &t);
	while (t--) run();
	return 0;
}

M - Game Theory

solved by Tryna.0:40(+)

题解： 签到题，答案样例都给出来了。

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 7;

void run() {
	int n;
	scanf("%d", &n);
	puts("0.0000");
}

int main() {
	int t = 1;
//	scanf("%d", &t);
	while (t--) run();
	return 0;
}
文章目录
  1. A - League of Legends
  2. C - Cube
  3. D - Shortest Path Query
  4. F - Fair Distribution
  5. G - Wall Game
  6. J - Grammy and Jewelry
  7. M - Game Theory
|