Educational Codeforces Round 115 解题报告

Educational Codeforces Round 115

A – Computer Game

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

B – Groups

nn范围较大,所以我们考虑从“每个星期只有55”入手。

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

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

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 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

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

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

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 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

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

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

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

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

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

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 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

待更。

  • 2021年11月17日