早晨同张黄赵，四人一起前往龙山书院。按陈的路线，先地铁坐一站用了一两分钟，然后走了一公里多花了半小时，大约 $9:00$ 到。这居然是赵第一次坐地铁。领了胸牌，照了合照，然后五人一起逛校园，顺便为 $NOIWC$ 的宿舍踩点，三个室友都不认识。逛太久了，开幕式没找到位置，只能坐在楼梯上听了一个小时，感觉内容和去年差不多

中午吸取教训，快速到达餐厅。午餐还是相当丰盛的，两荤两素。在报告厅里休息一个小时后，来到棒垒球馆

试机 $30min$。第一题之前做过，想了一会儿才写出来，但是 $0pts$。第二题是交互题，看了一下是简单二分，但没有写。剩下时间只写了一份不太正确的 $NTT$。休息 $10$ 分钟时，突然发现没拿笔，来不及取了，只能借了一支

下午 $1:00$ 正式开始

先开了 $T1$，从数据范围看初步感觉是数学题或 $dp$ 题，于是思考了一会儿，只想出了 $a>b+1$ 时 $5pts$ 的部分分：答案为 $b+1$

之后转向 $T2$，一开始看错题，以为是简单三维偏序，写了一部分时发现不对，重新看题。感觉是大 $ds$，只写了 $n,m\le10^3$ 的暴力查询祖先然后去重，此时对 $10^4$ 级已经有大致构想了，但没有写

看了一下 $T3$，基本没有想法，于是继续磨 $T1$

题意可以转化选出若干二元组 $(x,y)\;(1\le x<y\le a+b)$，要求对于任意 $a$ 个 $1$ 和 $b$ 个 $0$ 的序列 $v_{1\sim a+b}$，有 $\operatorname{or}_{(x,y)} (v_x\land v_y)=1$。当时想到类似之前模拟赛“原始人起洞”那题，从几何上考虑，想了许久想到了一个错的公式，连样例都没过

于是又去看 $T2$，做 $10^4$ 级的一档，一开始想长剖 $O(1)$ 求 $k$ 级祖先，但快写完才想到有更优且更加有优化前途的做法：对 $x$ 扫描线，于是快速写完过了

再回来看 $T1$，想了相当长时间，只过了 $a=2$ 的 $5pts$，写了一大堆暴力，发现 $a,b\le4$ 都跑不了，一度想放弃了，然后想到可以从序列的角度思考，相当于 $a+b$ 个点，选择若干对连无向边，要求从中选出 $a$ 个点必有两个为同一边的两端点，要求边数最小。这等价于 $a+b$ 点的无向图，要使最大独立集 $\le a-1$，求最小边数。由于前段时间网络流做多了（连做网络流 $24$ 题），想成二分图了，然后从最大流的方式考虑，发现样例都解释不了。之后想到一个构造方法，样例过了，$a>b+1$ 和 $a=2$ 的也可以解释，但交了只有 $10pts$。于是用暴力程序跑出 $a=3,b=4$，画出来思考了一会儿，终于想到正解，过的时候已经下午 $4:07$ 了

立刻转到 $T2$，想了一会儿下一档没有思路，去思考 $T3$

$T3$ 花了一段时间才看懂题，写了 $n,m,k\le 100$ 的 $dp$，尝试卡过 $3000$，没有 $T$ 但是 $WA$ 了，想了半天没找到原因，尝试写出了缩点的 $O(mk)$ 做法，但是样例都过不了，此时已经来不及调了

最终 $100+24+10$

出来之后同几人交流，张 $100+26+0$，黄 $100+41+0$，$cyf$ $300$，诸 $100+24+20$，唐 $160+$，范和赵 $T1$ 都没过

由于晚高峰，回来时还是那条路。出地铁站时，张拿单程票在闸机上刷了四五次，才意识到是插进去，被笑话了许久

今天被 $T1$ 卡了至少两三个小时

$a$ 个有电电池，$b$ 个没电电池，每次从中选出两个，求最优策略、最坏情况下，第一次同时取到两个有电电池的最小次数，$a,b\le1000,a\ge 2,b\ge 1$，多测 $T\le1000$

等价于 $a+b$ 个点，选择尽量少的边，使其最大独立集 $\le a-1$

将 $a+b$ 个点划分为 $a-1$ 个团，显然这样是合法的，考虑最小化总边数

令 $A=a+b$，$B=a-1$

发现 $A\bmod B$ 个团为 $\lfloor\frac AB\rfloor+1$ 个点，$B-(A\bmod B)$ 个团为 $\lfloor\frac AB\rfloor$ 个点时最优

赛场上写了单次询问 $O(a)$ 模拟的做法，实际答案为 $(A\bmod B)f(\lfloor\frac AB\rfloor+1)+(B-(A\bmod B))f(\lfloor\frac AB\rfloor)$（其中 $f(x)=\frac{x(x-1)}2$），不难做到 $O(1)$

给定 $n$ 点的树，$m$ 次询问每次给定 $l,r,x$，求 $|\{fa^x(i)\mid l\le i\le r\}|$，其中 $fa^x(i)$ 表示 $x$ 的第 $i$ 级祖先，若不存在则忽略该元素，$n\le10^5,m\le10^6,l,r,x\le n$

答案可以表示为 $\sum_{u=l}^r[dep_u>x][\forall l\le v<u,dep_u=dep_v(dep_{lca(u,v)}< dep_u-x)]$

令 $ls_{x,u}$ 表示最大的 $v$，满足 $v<u,dep_u=dep_v$，且 $dep_{lca(u,v)}\ge dep_u-x$，不存在则为 $0$

则答案为 $\sum_u[l\le u\le r][ls_{x,u}<l]$，为二维数点的形式，可 $CDQ$ 分治做

考虑计算 $ls$ 数组

对于每个 $u$，若 $v<u$ 且 $dep_u=dep_v$，则 $v$ 对 $ls_{\ast,u}$ 的影响是令 $ls_{x,u}\;(x\ge dep_u-dep_{lca(u,v)})$ 对 $v$ 取 $\max$

对于每个深度分别处理。按编号从小到大扫描该深度的所有点，令当前扫到的点为 $u$，每次令 $u$ 到 $1$ 的链上所有点赋值为 $u$，则 $ls_{x,u}$（在赋值之前计算）等于 $x$ 的第 $x$ 级父亲的值，若没有第 $x$ 级父亲则为 $\infty$

（该技巧类似于 P4211 [LNOI2014] LCA，比赛前两天刚做过，但赛场上没想到，可悲）

每个数组 $ls_{i,\ast}$ 中相同的并为一段，通过树链剖分，转化为 $O(n\log n)$ 次区间赋值，每次将异色两段合并为一段代表 $ls$ 的一段，可以颜色段均摊做到总段数 $O(n\log n)$

离线所有询问，转化为 $O(n\log n)$ 次单点修改和矩形查询，$CDQ$ 分治即可

总时间复杂度 $O((n\log n+m)\log (n\log n+m)\log n)=O(n\log^2 n\log m+m\log n\log m)$，因为树剖和树状数组常数小，所以可以过

给定 $n$ 点 $m$ 边的有向图，点有点权 $a_i$。定义一次对 $s$ 和 $b_{1\sim k}$ 进行一次游戏为进行 $k$ 轮博弈，一个物体初始在 $s$，第 $i$ 轮中选择一个当前物品所在点可达的点（至少移动一步），满足那个点的点权等于 $b_i$，并将物品移过去。给定 $b_{1\sim k}$，对于每个 $1\le s\le n$，求出最小的 $0\le r<k$，使得仅取 $b_{r+1\sim k}$ 进行游戏先手可胜，若不存在则为 $-1$。$n,k\le10^6,m\le2.2\times10^6$

考虑 $dp$

令 $f_{i,j}$ 表示取 $i$ 和 $b_{j\sim k}$ 进行游戏先手是否必胜

则 $f_{i,k+1}=0$，令 $to(x)$ 为 $x$ 的所有可达点，转移为 $f_{i,j}=\operatorname{\mathop{or}}_{u\in to(i)} [b_j=a_u](\lnot f_{u,j+1})$

答案容易从 $f$ 得到

直接做时间复杂度 $O(n^2k)$，可 bitset 优化到 $O(\frac{n^2k}\omega)$

对于同一强连通分量中的 $i,j$，对于 $1\le s\le k$ 有 $f_{i,s}=f_{j,s}$

于是对原图进行缩点，每个联通块为单位处理，转移时按照拓扑序递推，可做到 $O(nm)$

考虑优化状态设计

显然同一 $SCC$ 中 $f$ 值相同

令 $F_i$ 表示最小的 $x$ 使得 $f_{u,x}=1$，其中 $u$ 为编号为 $i$ 的 $SCC$ 中的节点，容易由其得到答案

将原图 $SCC$ 缩点，在反向图上拓扑排序的同时计算 $F$

初始所有 $F_i=k+2$

若当前处理节点 $i$ 对应的 $SCC$ 中节点数 $>1$，则可以在该 $SCC$ 内部移动若干次

令 $mnps_v$ 为 $v$ 在数组 $b$ 中第一次出现的位置

令 $mp$ 为 $mnps_{a_i}$ 的最小值，其中 $i$ 为当前处理 $SCC$ 中的点，其表示 $b_{mp}$ 在当前 $SCC$ 中有对应点

若 $mp\ge F_i$ 显然没有必要跟新

若 $mp=F_i-1$，则相当于令后手必胜，显然不优，此时也不需要更新

否则显然以当前 $SCC$ 开始，可以从 $b_{mp}$ 开始移动

若从 $b_{mp}$ 开始先手必胜，则 $F_i\gets mp$，否则 $F_i\gets mp+1$，考虑如何判断

令 $ct$ 为满足 $\{b_{mp\sim ct}\}\subseteq S_a$ 的最大值，其中 $S_a$ 表示当前 $SCC$ 中所有节点的 $a$ 构成的集合

若 $\min(ct,F_i-1)-mp$ 为奇数则先手必胜，否则后手必胜，可分类讨论证明

对于反图上 $i$ 的后继节点 $v$，有 $F_v\gets \min(F_v,F_i)$，因为先手可由 $v$ 进入 $i$

当 $i$ 对应 $SCC$ 大小为 $1$ 时，只能在其上停留最多一个 $b_s$

令 $p$ 为该 $SCC$ 中唯一点

若 $mnps_{a_p}<F_i-1$，则在点 $i$ 从 $b_{mnps_{a_p}}$ 开始且 允许第一步可移动 $0$ 的距离的情况下（因为题目要求至少移动一步，对于 $SCC$ 大小大于 $1$ 的可以绕一圈回来，不影响，但是对于 $SCC$ 大小等于 $1$ 的，其不符合要求，但从 $v$ 出发就合法了） 必胜，$F_v\gets \min(F_v,mnps_{a_p})$

时间复杂度可以做到 $O(n+m)$，常数极大

早上到达学校，两场讲座都是 $45min$，都和 $AI$ 有关，感觉很有意思

中餐仍然两荤两素。在报告厅休息一会儿后开始下午的考试

昨天试机 $T2$ 放交互不是没有原因的，$Day2$ $T1$ 就是交互。想了一会儿没有思路，于是看了一下 $T2$。同样没有思路

转到 $T3$，先写了 $B\le 40,r\le 10^6$ 的，然后狄利克雷卷积优化过了 $r\le 5\times10^6$ 的，最后暴力搜索过了 $l=r,B\le 4$ 的一档，总计 $44pts$

之后转战 $T2$，写了一个做法结果 $0pts$，想了一会儿成功把自己 $hack$ 了。应该想到了 $c=1$ 的正解，优化了暴力，但没有调出来

由 $T1$ 想到了之前做的一题，那题是其弱化版，树换成序列，于是尝试从 $T1$ 拿分。思路是先找到相近的两个点，然后由其找到直径的一端，再由其找到直径的另一端。写的过程中想到相当多的特殊情况，不知道如何解决。写了一大段满是 $bug$ 的代码，调了许久，过了所有样例和自己造的数据，但仍然一分未得

大约 $4:30$ 左右又回来调 $T2$，$WA$ 了几次后回去继续磨 $T1$，但一直到结束都没有做出来

最终 $0+0+44$，最惨的一次

张第二题拿了七八十，其余一样；范好像只有 $30$ 多；唐逸然 $120+$；其余人大都分数比我高一个数量级

死磕 $T1$ 应该是做的最错误的一个决定

两天都死在 $T1$ 上，但愿之后的 $NOIWC$ 不要再这样了

给定 $n$，存在一个 $n$ 点的树。交互库支持两种操作，操作一为给定 $i,j,k$ 返回 $query(i,j,k)=dis(i,j)+dis(i,k)+dis(j,k)\;(i\ne j\ne k)$，操作二是给定 $i,j,k$ 返回 $i$ 是否在链 $j-k$ 上。前者调用不超过 $3\times10^5$，后者调用不超过 $2$ 次，求出树的任意一条直径的两端点。$n\le10^5$，多测 $T\le10^4$，$\sum n\le10^6$，$4s$，保证 $2\times10^7$ 次操作一和 $2\times10^4$ 次操作二交互库耗时不超过 $3s$

$n\le 4$ 时特判

$n\ge 5$ 时，设 $\binom 52$ 个未知元，分别表示 $1\sim 5$ 中两点的距离，然后 $\binom 53$ 次询问设出 $\binom 53$ 个方程，解出 $1\sim 5$ 两两之间的距离（高斯消元），从而求出前 $5$ 个点的直径的两端

假设前若干点的直径为 $x-y$，$z$ 为一个不等于 $x$ 和 $y$ 的点，且 $x,y,z$ 两两之间的距离已知，要加入下一个点 $i$，则根据直径的性质，加入下一个点后的直径一定为 $x-i$ 或 $y-i$，询问 $(i,x,y)$，$(i,x,z)$，$(i,y,z)$，可解出 $i$ 到 $x,y,z$ 三点的距离，即 $x,y,z,i$ 两两距离已知，更新信息即可

总询问次数为 $3(n-5)+\binom 53=3n-5$，时间复杂度 $O(n)$，常数略大

给定 $a_{1\sim n},m,k,c$，每次花 $1$ 的代价令某个 $a_i$ 减一，或花 $c$ 的代价选择一个长为 $m$ 的区间，令区间中的数减少，减少总量不超过 $k$，求令 $a$ 全部变为 $0$ 的最小代价，多测 $\sum n\le5\times10^5,1\le a_i,k,c\le10^9,c\le k$

显然存在一种最优方案，对于每个操作二的连续段（将操作二修改的区间从左到右排序，若相邻一对有交则并入同一连续段），满足操作二取走了它的一个前缀，剩余部分及所有连续段以外的部分用操作一清除

令 $rp_i$ 表示只用操作二（且每次操作都用尽 $k$ 个数），最多能清除 $[i,rp_i)$，令 $f_i$ 表示清除 $[i,n]$ 的最小代价，令 $S(l,r)=\sum_{i=\max(l,1)}^{\min(r,n)}a_i$，令 $s$ 为 $a$ 的前缀和数组

假定已经求出 $rp$，考虑如何计算 $f$，显然 $f_{n+1}=0$，在 $f_i$ 处先清除 $[i,rp_i)$ 一定最优，若 $rp_i=n+1$ 则 $f_i=c\cdot \frac{S(i,n)}k$，否则已经用了 $c\cdot \left\lfloor\frac{S(i,rp_i+m-1)}k\right\rfloor$，此时 $[rp_i,rp_i+m-2]$ 中还剩下一部分，若使用操作一清除则 $f_i\gets f_{rp_i+1}+c\cdot \left\lfloor\frac{S(i,rp_i+m-1)}k\right\rfloor+{S(i,rp_i+m-1)}\bmod k-S(rp_i+1,rp_i+m-1)$，否则用一次操作二即可清除，转移为 $f_i\gets f_{\min(rp_i+m,n+1)}+c\cdot \left\lfloor\frac{S(i,rp_i+m-1)}k\right\rfloor+c$

问题转化为如何计算 $rp$

显然 $rp_i=\min_{t=1}^n \{t\mid S(i,t+m-1)\bmod k>S(t+1,t+m-1)\}$（若不存在符合条件的 $t$ 则 $rp_i=n+1$）

直接计算为 $O(n^2)$ 的，无法接受

该过程可以替换为先令所有 $rp$ 赋值为 $n+1$，然后从 $n$ 到 $1$ 枚举 $t$，对于所有满足 $1\le i\le t,S(i,t+m-1)\bmod k>S(t+1,t+m-1)$ 的 $i$ 令 $rp_i$ 赋值为 $t$

而

若 $St\ge k$ 显然对 $rp$ 无影响，否则显然 $-k<U-x<k$，分类讨论得

相当于有数组 $v_{0\sim k-1}$，初始全为 $n+1$，然后将区间 $(U,U+k-St)$ 和 $[0,U-St)$ 赋值为 $t$，然后令 $rp_t=v_{s_{i-1}\bmod k}$

用 $\text{ODT}$ 维护 $v$ 即可

时间复杂度 $O(\sum n\log n)$

初始 $x=1$，每次 $x\gets x+1$，或 $x\gets x-1$，或 $x\gets xk(k>1)$，保持 $x$ 全程为正，求对于每个 $l\le i\le r$，在不超过 $b$ 步内得到 $i$ 的方案数取模，$b\le100,r-l\le30000,r\le3\times10^9$

预计优异要 $400pts$ 左右，我才 $178$，$44\%$