难绷

Nemonade · 2023-10-02 19:09:42 · 个人记录

20230928

开 T1，给定矩阵，多次三角形加，单次查询。多次修改，单次查询，考虑差分。发现直接每一行暴力差分只有 3\times10^8，加上评测机换成神机了，所以直接写，写完在本地老爷机上极限数据跑了 3 秒，那这就肯定过了。

开 T2。给定原序列和操作序列，两人分别操作，每次可选择删去或只保留操作数的倍数，先手想要和最小，后手想要和最大，求最后的结果。

看到博弈论，发现自己不会 SG 函数，对抗搜索也没有打过，但好在最后还是写出来了。\alpha-\beta 剪枝想都不用想肯定不会。但是写了个判断全空的剪枝，然后发现大样例跑贼快就没管了。

update：赛后知道这样一剪复杂度就成 O(nq) 了，大受震撼。

update：改题时看了一分钟发现会 SG 函数了。

开 T3。如果两点的权值的 gcd 是合数就说明有边，求删去一个点使得剩下的连通块大小最大的最小。显然有 O(n^2q) 的暴力，写个筛随便打了就过了。

开 T4。给一棵有颜色的树，生成两条链使得它们不重叠，而且各自的端点颜色必须一样。每次有一个节点不能用，求方案数。当然直接一波 O(qn^5) 暴力。

出分。T1 卡常了 70 分；T2 写挂了加上捆绑保龄了；T3 卡常暴力只有 16；T4 暴力都卡保龄。总分 86，\text{rank}+\infty。

T2 就这样写卡卡常就可以过……

T3 神仙题。考虑所有两个质数的积，发现这样连通性不受影响。如果把寻找最大连通块换成并查集依次加边就过了。

Why not 重测？