游记 - PKUSC 2024

相比冬季，没啥意思，估计是心里放着 whk 吧。前情提要是，一模白挂 30+ 分，传统弱势政治和历史反而相对高名次。

飞过来才发现明明在学军文渊的比赛，机场却在宁波栎社，好像是搞成余姚中学导致的，所以辗转，晚上到 1:00 才睡。

Day 0

2024.5.13.

睡了一场开幕式，然后试机，发现四个月前不会的 PKUWC D2T2 现在还是不会，搜了个题解，挺有意思的，但是还挺难写的，就去吃饭了。饭盒体量有点小了。

T1：给两行长为 $n$ 的字符串，任意始终，每步向右或向下，要走出最长的回文串，求其长度。$n\le 10^5$。

T2：给格点 $n$ 边形的每个顶点坐标，求有多少种选大小为四的格点集合的办法，使得四个点均在多边形内或上，且形成一个正方形。$3\le n\le 8$，$0\le x_i,y_i\le 2000$。

T3：给一棵树，求给每个点赋权值 $[1,m]$ 的 $m^n$ 种方案，最大独立集的总和。$0\le n\le 2000$，$0\le m\le 10^8$。

一开始断定 T1 是可做题，然后尝试 KMP、Manacher、字符串哈希等，做了两小时发现读错题了（读成结束在点 $(2,n)$），没有快速地挽回，打 50 pts 跑路。

断定 T3 是不可做题，打了最低档暴力 11 pts 跑路。

T2 非常有想法，觉得是 $O(2000^2)$ 枚举第一条边的向量，然后按这样形成正方形四个点的方位，把原 $n$ 边形复制平移 4 份，求交的格点数。那就只要把横坐标离散化，然后上……上什么呢？

怎么是上类欧啊？？？怎么是半平面交啊？？？

然后就开始推一万年没推过的类欧和尝试简化半平面交了。先冲了一会长方形 10 pts ，嫌 $O(500^3)$ 档分有点繁琐（其实好写的要命）就接着推三角形。等到还剩十几分钟才推上正路，刚要把修正后的类欧交上去，就撞上结束页。

丢人场。首先没有把签到题搞出来，然后没有把有思路题的部分分打够，状态完全不在，跟一模感觉差不多。

出场发现 T1 纯纯签到，T2 原来可以用 Pick 定理，小丑竟是我自己？

Day 1

2024.5.14.

由吉老师上课，讲“自动 AC 机”：其实是让电脑写算法的领域。既基础又有意思，挺好的。但是没有抢到回答问题的机会，没能拿到 pku 校徽，呜呜。

T1：给一个由点 $1\sim n+1$ 组成的 DAG，点 $1\sim n$ 每个都有两条出边指向 $f_{i,0/1}$，且 $i<f_{i,0/1}\le n+1$。对点 $1\sim n$ 每个维护 0/1 变量 $b_i$。假设有一个货物，初始在点 $1$，在每个点就走向 $f_{i,b_i}$，然后 $b_i$ 取反，直到货物到达点 $n+1$ 就终止。输入 $f,b$，输出最小的 $t$，满足 $t$ 个货物经过后，$b$ 变回原样。

T2：给一个长为 $n$ 的二元组序列 $(l_i,r_i)$，$q$ 次询问，每次询问给出 $(L_i,R_i)$，求 $f_{R_i}(f_{R_i-1}(\ldots f_{L_i+1}(f_{L_i}(0))))$，其中 $f_i(x)=x+[x\in [l_i,r_i]]$。$0\le l_i,r_i\le n$，$1\le L_i,R_i\le n$，$n\le 10^6$。

T3：给 $n,m,q$ 和一个随机数生成种子，用 std::mt19937 均匀随机生成 $n$ 点 $m$ 边的有向图，并 $q$ 次询问，每次问 $s_i$ 到 $t_i$ 的最短路。$n\le 2\times 10^5$，$m\le 3\times 10^6$，$q\le 10^4$。

我不知道为什么就瞪出来 T1，可以用 $c_i$ 表示货物经过点 $i$ 向两个支路各走了 $c_i$ 次，然后可以用 $c_1$ 表示所有 $c_i$，令所有 $c_i$ 为整即可，答案就是最大的 $c_i$ 的分母 $\times 2$。为什么就瞪出来了？为什么写个 std::deque<bool> 一遍就过了？啊？此时过了 1h。

T2，一开始觉得是线段树，想不通又觉得是分块，又想不通信息的合并，又觉得是平衡树，又感觉很难维护。然后突然想起来可以算每个点的贡献，然后调了 1h 主席树，然后发现自己小丑，然后把可持久化删了，然后就过了？啊？此时过了约 2.5h。

T3 断定不可做，先把白送的 5 pts 拿了，然后写了这样的骗分：随机若干个点 $p$，跑它为源的最短路和反图最短路，用 $d'_s+d_t$ 更新每个答案，然后就莫名其妙过了一个 10 pts 的 subtask，是 $m\le n$。莫名其妙。在冲 $n\le 3000$ 的 15 pts Subtask，很诱人，胡了一个随机选中转点跑 Floyd 的东西，卡不过去，有点坐牢。

达成成就：第二天的分数高于第一天的三倍。

但凡第一天来点感觉，整个的分数就很稳了。哎。

听说 T3 可双向 Dijkstra，考场上居然没想到，不太行。