2025.1.14-1.15 PKUWC

szt100309 · 2025-01-14 18:41:20 · 个人记录

Day 1

早晨同张黄赵，四人一起前往龙山书院。按陈的路线，先地铁坐一站用了一两分钟，然后走了一公里多花了半小时，大约 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

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

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

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

比赛

T1 电池检测

等价于 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)

代码

T2 Ancestors

给定 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

答案可以表示为

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

特殊地，若 dep_u\le x 则 ls_{x,u}=\infty

则答案为 \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)，因为树剖和树状数组常数小，所以可以过

代码

参考

T3 基础博弈练习题

给定 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 得到

直接做时间复杂度 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)，常数极大

代码

参考

Day 2

早上到达学校，两场讲座都是 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 不要再这样了

比赛

T1 网友小 Z 的树

给定 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

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

令 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)

代码

参考

T3 数字变换

初始 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

final

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