2020 CCPC 秦皇岛站感想和部分题解

第一次参加 CCPC，开局不到一小时愉快地签完了 A、G、F，rank 银区偏高，然后就开始了三小时多的自闭调试，队友我分别开了 C 和 E 两题，都在出问题。最后两题调完还剩二十多分钟，K 这种傻逼题都搞不出来，最后耻辱地打铜了（之前敲错成银了🌚）。

由于第一次打比较正式的比赛，之前没有对 codeblocks 等 IDE 进行适应也是一个问题（我日常 Emacs + 大量插件，一个队友日常 VS），感觉时间上面多少吃了些亏。

A A Greeting from Qinhuangdao

签到题，取两个，都是红色，C2rC2r+bCr2Cr+b2 即可，注意约分，红球少于两个则为 00。

C Cameraman

题意：Bob 的房间为矩形，长宽已知；里面有若干私人物品，Bob 自身和私人物品均视为点，位置已知固定。Alex 给 Bob 拍照，位置自选，角度范围自定（可超过 180°）。要求拍到 Bob，不拍到私人物品，求可以拍到的最大墙壁总长度。如下图绿色部分。

这题大清再次背锅，只能靠样例来猜测 Alex 和 Bob 在同一个位置时最优，否则似乎不可做。

然后，利用极角排序，找到一个方向，让直线和它两边的点紧贴，计算出结果。

由于队伍内计算几何比较薄弱，这题虽然不算难但还是在细节上出了不少问题，再加上平台上 C 题的自测是坏的（估计是因为自测没有 spj），导致比赛期间怀疑评测机有问题，浪费了大量时间。

E Exam Results

题意：有若干学生考试，每人有可能获得一高一低两个成绩（可能相等），且无法预测。本次考试的及格线为 最高分×ratio最高分×ratio，求所有情况中，可能的最多及格人数。

对于一个人的成绩 xx，在最高分不高于 x/ratiox/ratio 时，他可以及格。当然，最高分不可能低于 xx，否则他自己的成绩将成为最高分，又因为他可能有两种成绩 a,ba,b，所以当最高分位于 [a,a/ratio]∪[b,b/ratio][a,a/ratio]∪[b,b/ratio] 时，他可以及格。

然后，我们把所有人的可能的较低分数取一个最大值，最高分至少等于它，而比它高的每个成绩也都可能作为最高分。然后枚举这个最高分，判断它在多少个人的可及格区间内，找出最大值即为答案。

数区间数量可以用线段树或者树状数组，区间更新+单点查询解决。

由于输入是百分比整数，且所有人成绩是整数，可以成绩乘 100100（int 溢出警告）再除，向下取整作为右端点。区间范围太大，需要离散化。

本人由于在开始写代码时忘记，“所有人的可能的较低分数取一个最大值，最高分最小时就等于它”的性质，导致耗费大量时间。

F Friendly Group

题意：组内的若干学生参加学术会议。全组的友好值初始为 00。组内有若干对朋友，如果一对朋友同时参加，则友好值加 11，如果有且仅有其中一人参加，则减 11。最后，每个参加的人都会让友好值减 11。从中选择任意一部分人（可能一个都不选）参加，求可能的最高友好值。

把学生看作点，关系看作边，则友好值等于 内部边数−跨内外边数−内部点数内部边数−跨内外边数−内部点数。假如对于一个联通块，我们选了一部分人，那么连通块的其他部分的 内部点数−内部点数内部点数−内部点数 最少为 −1−1，加上它与已选部分之间的边，把整个连通块选进来结果一定不会比只选当前部分差。

因此，可以把整个连通块视为整体，用上面的公式计算，然后根据其值正负决定是否选择，最后对所有正结果取和即可得出最终结果。

G Good Number

题意：不大于 nn 的正整数中，有多少个可以被它的 kk 次方根（向下取整）整除。

对于每一个数 ii，[ik,(i+1)k)[ik,(i+1)k) 开根向下取整均为 ii，所以可以用该区间长度除以 ii 即可得到可被 ii 整除的个数。由于区间的第一个数就可被整除，所以有余数时向上取整。

由于 n≤109n≤109，当 k≥30k≥30 时，所有数开根都是 11。

I Interstellar Hunter

题意：在一个无限制的二维空间内，Alex 一开始在原点，他会不断获得按照一个二维向量进行移动的能力，利用每个能力可以正向或反向移动无限次。询问是否可以到达特定的位置。存在多次询问，获得能力和询问可交替出现，每次询问附带价值，最后输出可到达的询问的价值之和。

对于二维向量 aa 和 bb，利用它们能走到的位置，也就是它们的线性组合。进行变换 a=a−ba=a−b，它们的线性组合并不会改变。因此我们可以对它们进行辗转相除。如 a=(x0,y0),b=(x1,y1)a=(x0,y0),b=(x1,y1)，对其 xx 进行辗转相除，计算（加减乘）时使用整个向量。这样就会得到 a=(gcd(x0,y0),y′0),b=(0,y′1)a=(gcd(x0,y0),y0′),b=(0,y1′) 。这样我们就可以利用询问的 xx 坐标轻易得出 aa 的系数，或是不能整除直接得出不可达，然后再判断 yy。然后出现新的向量的话，我们先将它与 aa 进行辗转相除，使其 xx 为 00，再与 bb 对 yy 辗转相除，这样它就变成无用的零向量了。

为了使当 aa 与新的向量进行辗转相除时在 yy 方向上最优，需要在 y′0≥y′1y0′≥y1′ 时对其相减，也就是取模。另外本题部分写法需要对 00 进行特殊考虑。

K Kingdom’s Power

题意：在一个战略游戏中，地图为树形，国王在根部（点 11），有无限的士兵，开始全部在点 11。每周可以让一个军队移动到一个相邻点。求他们走一遍所有地区（可重复）至少需要的周数。

首先，对于每个非叶子节点，它都在从根节点到它对应子树的各点的必经之路上。因此只需考虑遍历所有叶子节点。

一个必然可行的方案是，对每个叶子节点，由一支军队从根部走过去。所需时间是所有叶子节点深度之和，以此作为基准值，考虑如何节省时间。

如果对某个有多个子节点的节点 XX，如果 XX 的某个军队在走到了某个叶子节点 AA 后回来，再进入 XX 下面的另一个子树，则对另一个子树的某一个叶子节点来说，从根（记作 RR，下同）到 XX 的路径 dRXdRX 被替换为了 dAXdAX，节省的时间为 dAX−dRXdAX−dRX。

对于某个节点 XX，如果它下面的某个子树下有两个叶子节点 A,BA,B，有两个军队分别从根部走到 A,BA,B 再回到 XX，则可节省的时间为 dRX−dAX+dRX−dBXdRX−dAX+dRX−dBX。此时，设 A,BA,B 的 LCA 为 YY，则改用如下方案：一个士兵走到 AA 后回到 YY，再进入 BB，然后回到 XX，则可节省的时间是 dRY−dAY+dRX−dBXdRY−dAY+dRX−dBX。而 YY 在 XX 和 AA 之间，dAY<dAXdAY<dAX，dRY>dRXdRY>dRX，后者节省的时间更多。该情况可类推到更多叶子节点的情况，从而可得到性质：对于每个子树，最多只会有一个军队从它返回到它的根节点的父节点。

然后，对于刚刚的情况，假如都要返回 XX，则交换 A,BA,B 的位置，总的结果不变。但如果最后不返回 XX，那么设最后的点为 BB，设返回 XX 的情况下总共节省的时间为 TT，则不返回的情况就要减去那一部分，则为 T+dBX−dRXT+dBX−dRX（BB 越深，该值越大），如果它优于 TT，则不用返回。因此，我们在考虑子树时，把最深的放到最后，在返回父节点的情况下不影响结果，在不返回父节点的情况下结果优于其他顺序。因此，我们应在子树内计算时优先考虑较浅节点，最后把最深节点的深度用于父节点判断是否需要该子树返回。

这样我们可以对整个树进行一次 dfs，dfs 过程中判断军队是否要从当前点下面的各个子树返回到当前点。根据上一段的分析，用各子树的最深节点判断，则在 dfs 过程中获取子节点的高度（叶子为 11，记作 height）即可。同时传一个参数表示遍历深度（根为 00，记作 dep）。则对于每个子树，如果要返回，节省的时间为 dep−heightdep−height，该值大于 00 则返回，把结果减去该值。

最后，如果某节点下的所有子树都选择返回，则意味着不存在最后进入的叶子节点，这样得到的结果显然是不合理的，需要让某一个不返回。很显然，让减少的时间最少（深度最大）的一个不返回即为最优。

核心部分代码：

int dfs(int pos = 1, int dep = 0) {
  if (ch[pos].empty()) {
    ans += dep;
    return 1;
  }
  int height = 0;
  bool flag = 1;
  for (auto p : ch[pos]) {
    auto tmp = dfs(p, dep + 1);
    height = max(height, tmp);
    if (tmp < dep)
      ans -= dep - tmp;
    else
      flag = 0;
  }
  if (flag) ans += dep - height;
  return height + 1;
}