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

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

A A Greeting from Qinhuangdao

签到题,取两个,都是红色,$\frac{C_r^2}{C_{r+b}^2}$ 即可,注意约分,红球少于两个则为 $0$。

C Cameraman

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

094ce15a-4794-4088-b232-c3a1cf1015ac.png

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

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

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

E Exam Results

题意:有若干学生考试,每人有可能获得一高一低两个成绩(可能相等),且无法预测。本次考试的及格线为 $最高分 \times ratio$,求所有情况中,可能的最多及格人数。

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

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

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

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

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

F Friendly Group

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

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

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

G Good Number

题意:不大于 $n$ 的正整数中,有多少个可以被它的 $k$ 次方根(向下取整)整除。

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

由于 $n \leq 10^9$,当 $k \geq 30$ 时,所有数开根都是 $1$。

I Interstellar Hunter

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

对于二维向量 $\boldsymbol a$ 和 $\boldsymbol b$,利用它们能走到的位置,也就是它们的线性组合。进行变换 $\boldsymbol a = \boldsymbol a - \boldsymbol b$,它们的线性组合并不会改变。因此我们可以对它们进行辗转相除。如 $\boldsymbol a = (x_0,y_0), \boldsymbol b = (x_1,y_1)$,对其 $x$ 进行辗转相除,计算(加减乘)时使用整个向量。这样就会得到 $\boldsymbol a = (gcd(x_0,y_0), y_0'), \boldsymbol b = (0,y_1')$ 。这样我们就可以利用询问的 $x$ 坐标轻易得出 $\boldsymbol a$ 的系数,或是不能整除直接得出不可达,然后再判断 $y$。然后出现新的向量的话,我们先将它与 $\boldsymbol a$ 进行辗转相除,使其 $x$ 为 $0$,再与 $\boldsymbol b$ 对 $y$ 辗转相除,这样它就变成无用的零向量了。

为了使当 $a$ 与新的向量进行辗转相除时在 $y$ 方向上最优,需要在 $y_0' \geq y_1'$ 时对其相减,也就是取模。另外本题部分写法需要对 $0$ 进行特殊考虑。

K Kingdom’s Power

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

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

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

如果对某个有多个子节点的节点 $X$,如果 $X$ 的某个军队在走到了某个叶子节点 $A$ 后回来,再进入 $X$ 下面的另一个子树,则对另一个子树的某一个叶子节点来说,从根(记作 $R$,下同)到 $X$ 的路径 $d_{RX}$ 被替换为了 $d_{AX}$,节省的时间为 $d_{AX} - d_{RX}$。

对于某个节点 $X$,如果它下面的某个子树下有两个叶子节点 $A,B$,有两个军队分别从根部走到 $A,B$ 再回到 $X$,则可节省的时间为 $d_{RX} - d_{AX} + d_{RX} - d_{BX}$。此时,设 $A,B$ 的 LCA 为 $Y$,则改用如下方案:一个士兵走到 $A$ 后回到 $Y$,再进入 $B$,然后回到 $X$,则可节省的时间是 $d_{RY} - d_{AY} + d_{RX} - d_{BX}$。而 $Y$ 在 $X$ 和 $A$ 之间,$d_{AY} < d_{AX}$,$d_{RY} > d_{RX}$,后者节省的时间更多。该情况可类推到更多叶子节点的情况,从而可得到性质:对于每个子树,最多只会有一个军队从它返回到它的根节点的父节点。

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

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

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

核心部分代码:

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;
}