Educational Codeforces Round 95

十月 23, 2020 8863

做题情况

这场有一小半的题是以前做过的，这次把没做的补了一下。

A. Buying Torches

题意简述

假设你在玩 mc，背包里有 1 根棍子。现在你要和村民交易来造火把，村民支持以下两种交易：

  • 用 1 根棍子换取 x 根棍子
  • 用 y 根棍子换取 1 个木炭

一个火把需要一根棍子和一个木炭。现在你需要造 k 个火把，求最小交易次数。

解题思路

简单数学题，推一推柿子就好了。

k torches = k coals + k sticks
= k(y + 1) sticks

合成 k(y + 1) sticks 需要 \lceil \frac{k(y + 1) - 1}{x - 1} \rceil 次合成，另外还需要 k 次合成 k coals

总答案

\left\lceil \frac{k(y + 1) - 1}{x - 1} \right\rceil + k

代码实现

1
2
3
4
5
6
7
8
9
10
11
long long int t, x, y, k;

int main() {
	scanf("%lld", &t);
	while (t --> 0) {
		scanf("%lld %lld %lld", &x, &y, &k);
		long long int T = std::ceil((long double) (k * (y + 1) - 1) / (x - 1)) + k;
		printf("%lld\n", T); 
	}
	return 0;
}

B. Negative Prefixes

题意简述

给定一个长为 n 的序列，其中有些位置是不能动的，现在让你重排其他能动的位置（也可以不排），最小化前缀和为负的最大下标（如果前缀和恒非负就是 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
const int MAXN = 100 + 10;

int T;
int n, aa[MAXN], lock[MAXN];
int extract[MAXN], ext;

int main() {
	scanf("%d", &T);
	while (T --> 0) {
		ext = 0; memset(extract, 0, sizeof extract);
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) scanf("%d", aa + i);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", lock + i);
			if (!lock[i]) extract[++ext] = aa[i];
		}
		if (ext == 0) {
			for (int i = 1; i <= n; ++i) printf("%d ", aa[i]); puts("");
			continue;
		}
		int sumofext = std::accumulate(extract + 1, extract + 1 + ext, 0);
		std::sort(extract + 1, extract + 1 + ext, std::greater<int>());
		for (int i = 1, j = 1; i <= n; ++i) {
			if (!lock[i]) aa[i] = extract[j++];
		}
		for (int i = 1; i <= n; ++i) printf("%d ", aa[i]);
		puts("");
	}
	return 0;
}

C. Mortal Kombat Tower

题意简述

你和你朋友要按照顺序打 n 个怪。怪物按照强弱分为大怪和小怪。由于你朋友不常锻炼，他只能打小怪，遇到大怪会直接跳过，但是你小怪大怪都可以打。由于打怪会很累，所以无论是大怪还是小怪，你和你朋友都只能连续打不超过两个，然后换另一位上。你朋友首先开始打，现在问你最少的跳过次数是多少。

解题思路

一个挺显然的结论：

一定可以构造出一个方案，使得（除了最开始）所有连续大怪的开头都是你先打。

例如，对于怪物序列 Small Small Big Big Big Small Big Big，你可以让你朋友打两个，你打两个，你朋友打两个，你打两个，这样所有连续大怪的开头——第三个怪、第七个怪，都是你打。

有了这个结论，我们就可以很方便地构造方案了。
具体地，对于一长串（假设有 k 个）大怪，头两个先你上，然后让你朋友打一个，然后你再打两个，朋友打一个，如此循环往复直到大怪全打完，这时这群大怪需要的跳过次数就是 \lfloor \frac{k}{3}\rfloor 。

把除了开头的所有一串大怪都这么算一遍加起来就差不多了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int MAXN = 2e5 + 10;

int n, aa[MAXN]; 

int main() {
	int T; scanf("%d", &T);
	while (T --> 0) {
		scanf("%d", &n); int ans = 0;
		for (int i = 1; i <= n; ++i) scanf("%d", aa + i);
		ans += aa[1];
		for (int i = 2; i <= n; ++i) {
			if (aa[i] == 0) continue;
			// 总是存在一个方法能跳过所有 0
			// 而且可以让“我”来打第一个 boss
			int j = i;
			for (; j <= n && aa[j] == 1; ++j); --j;
			ans += (j - i + 1) / 3; i = j; 
			// “我”打两个 boss，我朋友打一个 boss
			// 三个 boss 对答案的贡献是 1 
		}
		printf("%d\n", ans);
	}
	return 0;
}

D. Trash Problem

题意简述

现在有很多堆的垃圾排成了一列，第 i 堆的坐标是 x_i 。你看不下去了，决定做一次清理。定义一次扫动为将某一堆的全部垃圾合并到它相邻的一堆垃圾中，花费为两堆垃圾的距离，合并完成后数轴上就少了一堆的垃圾。定义一次大扫除是把所有垃圾通过扫动合并成不超过两堆垃圾，花费为最小化的所有扫动花费的总和。输出大扫除的花费。

另外给你 q 次操作，每次可以在一个坐标上放置一堆垃圾，或者清除一个坐标上的所有垃圾（询问不独立），每次操作生效之后，输出大扫除的花费。

解题思路

先看看大扫除的花费。

可以发现，如果要把所有垃圾合成一堆，花费是两个最远的垃圾堆的距离。那么合成两堆呢？

显然，所有相邻的垃圾堆中，不合并最远的那一堆最优。

所以大扫除的花费就是：最远的两个垃圾堆之间的距离 减掉 相邻的垃圾堆中最远的距离

然后看看操作怎么做。

需要维护的信息有：两两的间距中最大值，整体的最大间距。
需要支持的操作有：插入并修改间距，删除并修改间距

这个东西可以用一个 std::set 和一个 std::multiset 实现。
具体地，建一个 std::set<int> 存储所有的垃圾的下标，这样可以 O(1) 求出整体的最大间距，支持 O(\log n) 插入和删除；建一个 std::multiset<int> 存储所有相邻的垃圾间距，这样可以 O(1) 求出两两的间距中最大值，并支持 O(\log n) 修改间距。

代码实现

友情提示：请在神智清醒的情况下听一些比较激昂的歌曲（推荐 AJR）写此代码，否则手控 iterator 可能不是非常简单。

代码看起来很长，但是整体结构非常清晰，可读性应该不差。

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
inline int read() {
	int s = 0, x = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
	while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
	return s * x;
}

int n, q;

std::set<int> trash;
std::multiset<int> dist;

int maxmultiset(const std::multiset<int> &s) {
	return (int) (*s.rbegin());
}
int maxset(const std::set<int> &s) {
	return (int) (*s.rbegin());
}
int minset(const std::set<int> &s) {
	return (int) (*s.begin());
}
void totalCleanUp() {
	if (trash.size() <= 2) puts("0");
	else printf("%d\n", maxset(trash) - minset(trash) - maxmultiset(dist));
}
void erasedist(int dis) {
	dist.erase(dist.find(dis));
}

int main() {
	n = read(); q = read();
	for (int i = 1; i <= n; ++i) {
		trash.insert(read());
	}
	int _last = 0;
	for (auto v : trash) {
		if (_last) dist.insert(v - _last);
		_last = v;
	}
	totalCleanUp();
	while (q --> 0) {
		int t = read(); int x = read();
		if (t) {
			// add
			if (trash.size() == 0) {
				trash.insert(x);
				totalCleanUp();
				continue;
			}
			int premin = minset(trash);
			int premax = maxset(trash);
			if (x < premin) {
				// +x+ a b c d e f ...
				dist.insert(premin - x);
				trash.insert(x);
			} else if (premax < x) {
				// ... c d e f +x+
				dist.insert(x - premax);
				trash.insert(x);
			} else {
				// ... c d +x+ e f ...
				auto it = trash.upper_bound(x);
				auto tit = it; it--;
				// it -> &d, tit -> &e
				dist.erase(dist.find((*tit) - (*it)));
				dist.insert(x - (*it)); dist.insert((*tit) - x);
				trash.insert(x);
			}
		} else {
			// remove
			if (trash.size() == 1) {
				trash.erase(x);
				totalCleanUp();
				continue;
			}
			int premin = minset(trash);
			int premax = maxset(trash);
			if (x == premin) {
				// -x- a b c d ...
				auto it = trash.begin(); it++; // &a
				erasedist((*it) - x);
				trash.erase(x);
			} else if (premax == x) {
				// ... c d e f -x-;
				auto it = trash.rbegin(); it++; // &f
				erasedist(x - (*it));
				trash.erase(x);
			} else {
				// ... c d -x- e f ...
				auto it = trash.find(x); // &x
				auto previt = it; --previt;
				auto nextit = it; ++nextit;
				erasedist((*nextit) - x);
				erasedist(x - (*previt));
				dist.insert((*nextit) - (*previt));
				trash.erase(x);
			}
		}
		totalCleanUp();
	}
	return 0;
}

E. Expected Damage

题意简述

又要打怪了。现在有 n + m 个怪物，每个怪物有能力值，仍然按能力值分为大怪和小怪。不同的是，这次没有队友陪你，只有一把耐久为 d 的剑。对于当前遇到的怪物，有三种可能的情况：

  • 如果你的剑还有耐久而且是小怪，那么什么都不会发生
  • 如果你的剑还有耐久而且是大怪，那么你的剑会掉一格耐久
  • 如果你的剑没耐久了，那么你会受到伤害，伤害值为怪物的能力值

怪物可以等概率地排成 n! 种顺序来打你，请求出你获得的伤害的期望。

解题思路

没法硬算，那就套一波期望的线性性。

这里假定大怪有 n 个，小怪有 m 个。

对于一个能力值为 a_i 的大怪，如果它在剑耐久没掉完的情况下来了，那么伤害为 0，概率为 \frac{d}{n} ，期望伤害为 0；如果它在剑耐久掉完的情况下来，那么伤害就是 a_i ，概率为 \frac{n - d}{n} ，期望伤害为 a_i \cdot\frac{n-d}{n} 。根据期望的线性性，所有大怪的伤害为：

\frac{n - d}{n}\sum_{i = 1}^{n}a_i

对于一个能力值为 b_i 的小怪，它在哪对大怪的伤害没啥影响，那么就可以放心插板，一共 n + 1 种方案，造成伤害的概率为 \frac{n + 1 - d}{n + 1} 。同样地，根据期望的线性性，所有小怪的伤害是：

\frac{n + 1 - d}{n + 1}\sum_{i = 1}^{m}b_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
34
35
36
37
38
39
const int MAXN = 200000 + 10;
const int ha = 998244353;

int n, m;
int d[MAXN];
long long int pref[MAXN];

long long int fastpow(int a, int b = ha - 2, int p = ha) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % p;
		a = 1ll * a * a % p;
		b >>= 1;
	}
	return ret;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", d + i);
	std::sort(d + 1, d + 1 + n);
	for (int i = 1; i <= n; ++i) pref[i] = (pref[i - 1] + d[i]);
	while (m --> 0) {
		long long int dura, rat; scanf("%lld %lld", &dura, &rat);
		long long int possmall = 0;
//		for (; possmall <= n && rat > d[possmall]; ++possmall); --possmall;
		possmall = (std::lower_bound(d + 1, d + 1 + n, rat) - d - 1);
//		debug(possmall);
		long long int sumsmall = pref[possmall], sumbig = pref[n] - pref[possmall];
		if (dura > n - possmall) puts("0"); 
		else printf("%lld\n", (1ll * (
				sumbig 
				+ sumsmall 
				- 1ll * sumbig * dura % ha * fastpow(n - possmall) % ha 
				- 1ll * sumsmall * dura % ha * fastpow(n - possmall + 1) % ha 
				+ ha + ha) % ha) % ha); 
	}
	return 0;
}