Educational Codeforces Round 115 解题报告

Educational Codeforces Round 115

A – Computer Game

由题意可知这是一个八连通的$2 \times n$网格。故我们扫描一遍，发现某列的两个格子均无法通过则失败。复杂度$\mathrm{O}(n)$。

B – Groups

$n$范围较大，所以我们考虑从“每个星期只有$5$天”入手。

因为安排课程的两天互不相同，所以我们可以$\dbinom{5}{2} = 10$次枚举安排课程的日期。假定我们枚举第$x,y (x \neq y)$天上课，设能够参加第$x,y$天上课的学生的集合分别为$X, Y$，则这种安排符合条件，当且仅当$|X \cup Y|=n \land |X|\geq\dfrac{n}{2} \land |Y|\geq\dfrac{n}{2}$。容易证明，这代表着：全体学生能够参加这两天的课程之一；能够在安排完成第$x$天课程的学生后，剩下的学生均能参与第$y$天的课程。

可以$\mathrm{O}(n)$地统计实现。

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;
 
int T, n, cnt[8];
bool f; bitset <100000> g[6];
 
int main () {
	/*  */
scanf ("%d", &T);
while (T--) {
	scanf ("%d", &n);
	memset (cnt, 0, sizeof cnt);
	for (int i = 1; i <= 5; ++i) g[i].reset ();
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= 5; ++j) {
			scanf ("%d", &f);
			cnt[j] += f;
			if (f) g[j][i] = 1;
		}
	}
	for (int i = 1; i < 5; ++i) {
		for (int j = i + 1; j <= 5; ++j) {
			if (cnt[i] >= n>>1 && cnt[j] >= n>>1 &&
				(g[i] | g[j]).count () == n) goto SUC;
		}
	}
	puts ("NO"); continue;
	SUC: puts ("YES");
}
 
	return 0;
}

C – Delete Two Elements

由题可知，删除前与删除后的平均数$k$相等。则$k(n-2)+a+b=kn$，得到删除的两个元素$a,b$之和为$2k$。则对于一个确定的$a$，只需要找到序列中$b$的数量即可。可以通过 STL map 或者手动离散化后实现。

注意题目中$a,b$的下标是有序的。注意特判$2k$不是整数的情况。复杂度$\mathrm{O}(n \log n)$。

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
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 10;
int T, n, a[N], g[N], m, cnt[N];
long long sm, ans, ave; double f;
 
int look_for (int x) { return lower_bound (g + 1, g + m + 1, x) - g; }
 
int main () {
	/*  */
scanf ("%d", &T);
while (T--) {
	scanf ("%d", &n);
	sm = ans = 0;
	for (int i = 1; i <= n; ++i) {
		scanf ("%d", a + i);
		g[i] = a[i], sm += a[i];
	}
	f = double (sm) / n;
	if (floor (f * 2) != f * 2) {
		puts ("0");
		continue;
	} else ave = f * 2;
	sort (g + 1, g + n + 1);
	m = unique (g + 1, g + n + 1) - (g + 1);
	memset (cnt, 0, sizeof cnt);
	for (int i = n; i >= 1; --i) {
		if (g[look_for (ave - a[i])] == ave - a[i])
			ans += cnt[look_for (ave - a[i])];
		cnt[look_for (a[i])]++;
	}
	printf ("%lld\n", ans);
}
 
	return 0;
}

D – Training Session

正如题解里面所说，“最简单的方法就是从所有可能的方案中减去不合法方案的总数”。一开始我分了$3$个大类$5$个小类，计算每个小类中的合法方案数。在这个过程中同时已经辅助计算了不合法的方案，最后发现——总答案只需要用“不合法方案”计算。

具体来讲，不合法的方案组合是：三个方案的topic有两个相同，difficulty有两个相同。同时，由于题目保证了不存在topic和difficulty同时相同的两个项目，则我们可以肯定，当我们钦定两个topic相同的项目$(top_1, dif_1),(top_1, dif_2)$，我们选择$dif_1$，则再任意在difficulty为$dif_1$中的项目中选择一个（排除已经钦定的$(top_1, dif_1)$），加入当前方案的组合，都有其$(top_1, dif_1),(top_1, dif_2), (top_2, dif_1)$。所以，计共有$b$个difficulty为$dif_1$的项目，则在前两个项目钦定的基础上，可以贡献$b-1$个不合法的方案。钦定两个项目的difficulty相同时同理。

所以，现在我们可以分别以topic和difficulty作为关键字存储项目。枚举topic作为第一关键字。对于每个项目数$a \geq 2$的topic，我们枚举其第二关键字difficulty。对于每个确定的项目数为$b \geq 2$的difficulty，由乘法原理得其将对不合法方案数贡献$(a-1)(b-1)$。枚举difficulty作为第一关键字同理。

注意，$(top_1, dif_1),(top_1, dif_2), (top_2, dif_1)$会分别在以topic和difficulty作为第一关键字扫描时对答案产生$1$的贡献，所以最终不合法方案数应折半。

因为每个项目在每一遍扫描时至多访问一遍，所以其复杂度上限是$\mathrm{O}(n)$，常数较大。

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
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 10;
int n, siz1, siz2, T;
vector<int> s_top[N], s_dif[N];
struct item {
	int topic, dif, id;
} g[N];
long long ans, b;
 
int main () {
	/*  */
scanf ("%d", &T);
while (T--) {
	scanf ("%d", &n);
	b = 0; 
	for (int i = 1; i <= n; ++i) s_top[i].clear(), s_dif[i].clear ();
	for (int i = 1; i <= n; ++i) {
		scanf ("%d%d", &g[i].topic, &g[i].dif);
		s_top[g[i].topic].push_back(g[i].dif), s_dif[g[i].dif].push_back(g[i].topic);
	}
	for (int i = 1; i <= n; ++i) {
		siz1 = s_top[i].size(), siz2 = s_dif[i].size ();
		if (siz1 >= 2)
			for (int j = 0; j < siz1; ++j)
				b += 1ll * (siz1 - 1) * (int (s_dif[s_top[i][j]].size()) - 1);
		if (siz2 >= 2) 
			for (int j = 0; j < siz2; ++j)
				b += 1ll * (siz2 - 1) * (int (s_top[s_dif[i][j]].size()) - 1);
	}
	ans = 1ll * n * (n - 1) / 2 * (n - 2) / 3;
	ans -= b / 2;
	printf ("%lld\n", ans);
}
 
	return 0;
}

E – Staircases

待更。