据说之前就有一次 PKUWC2019 了
这次暂且叫 PKUWC2019-2 吧（
Day0
飞机上无聊……颓颓颓……
一出飞机就感受到北京扑面而来的寒冷
看到草坪里有些没化的雪顿时暴露出孤陋寡闻的南方人的本质
中午吃了些馄饨（好吃！）
下午报到，赶地铁，北京地铁的安检是真的水
教室门口排了半天队，几名学长在那儿斗地主（OIer 传统艺能）
居然给了两张临时饭卡，不过这个打孔的工艺有种十多年前的感觉（说不定是几十年前的操作？不过我记得我小时候是遇到过打孔卡的）。
晚上还是在那家餐馆吃，味道是真的好（也有可能是我吃食堂吃多了）
晚上颓颓颓
Day1
冷冷冷
早上去参加开营仪式，因为楼上在考研（？）所以不让鼓掌，特别不习惯
不过开营仪式十分简短（比预定时间提前一个多小时好评）
之后去找考场，结果绕了半天发现整个是一栋楼中间一块空地，又绕了半天发现这其实是日字形的楼（？！！）
跟着 PKU 学长在 PKU 闲逛，听学长导游 吹牛 讲注意事项。
未名湖已经结冰，还在冰上走了几步（南方人第一次在冰面上走）
在未名湖附近绕了一圈然后去燕园吃饭
PKU 的菜品分量很足啊……不过辣椒是假的石锤了
PKU 食堂居然有 $15\%$ 的税，这意味着 $150$ 元的饭卡其实只有 $27.5$ 元
考试
机房电脑各种软件都有我选择 VSC
先敲了个读优，登录到系统发现用的 openjudge，大概是只有传统题了
13:00 开始
大致题意：
- T1：给一个 $[1\dots n]$ 的排列 $P$，将字典序不大于 $P$ 的所有 $[1\dots n]$ 的排列收尾依次相接，问得到的序列的本质不同的子序列有多少种（含本身/空串）？答案 $\bmod 998244353$。$n\leq 50$
- T2：有 $n$ 个集合 ${a_1},{a_2},\dots,{a_n}$，记 $f(k)$ 为每次合并随机两个集合直到剩 $k$ 个集合后，$\sum\limits_{i=1}^k (\max S_i-\min S_i)^2$ 的期望。求 $\sum\limits_{i=l}^r f(i)^{97376}\bmod 998244353$。$n\leq 2\times10^5$
- T3：一个 $n\times m$ 的表格。先做 $q_1$ 次操作：给定 $s,l,r,x$，把所有 $\gcd(a,s)=1,\ l\leq b\leq r$ 的位置 $(a,b)$ 加上 $x$。再做 $q_2$ 次询问：给定 $s,l,r$，求所有 $\gcd(a,s)=1,\ l\leq b\leq r$ 的位置 $(a,b)$ 之和 $\bmod 2^{32}$。$n,m,q_2\leq 5\times 10^4,q_1\leq 10^5$，$s$ 在 $1$ 到 $n$ 间随机生成。
看到题目的反应：
- T1 数数；
- T2 还是数数？是不是要 $\min-\max$ 容斥之类的？
- T3 还……好吧不是数数了，应该是莫反（或者说容斥——容斥系数为 $\mu$）+数据结构？
看了看部分分感觉都不太好写，先把 T2 的 $l=r=1$ 的 $1$ 分写了，一阵冷静分析+前缀和优化之类的操作把 $l=r=n-1$ 的 $8$ 分写了，然后枚举集合划分把 $n\leq 7$ 的 $9$ 分写了（假算法）。交上去——$1$ 分。
弄了几次都是 $1$ 分，决定先写 T3 $n,m,q_1,q_2\leq 100$ 的暴力修改。两点半左右敲完。
草稿纸上推了一下觉得这个的确可以莫反，于是花半个多小时写了一个 $O(\text{能过而且跑得挺快})$ 的算法把 $m=1$ 的 $24$ 分写了。
回过头看 T1，想到了个 $O(n!n)$ 的算法——$f_i=2f_{i-1}-f_{a_i\text{ 上次出现的位置}-1}$，就花了半小时写了 $n\leq 8$ 的 $21$ 分
看了看 T2，发现 task3 是一个地方忘用 long long 了，调了一下又弄了 $8$ 分过来，接着突然发现集合划分概率不等，放弃治疗。
然后冷静分析，想不到什么好的数据结构，就先强行差分数组写了一个 $O(nm\log n)$ 的做法把 $n,m,q_1,q_2\leq 1000$ 的 $13$ 分写了。调好已经是四点钟了。
接着感觉差分数组应该填不满，于是开始用 map<int,int>[30000] 写数据范围 $30000$ 的部分分，结果 MLE 又 TLE，优化了几次也没卡过去，荒废了半个多小时。然后又想不到什么数据结构支持区间加，快速把两个序列加在一起，最后查询区间和。
又去修 T2，拿 $n^nn^2$ 的 DP 把每种划分的概率算出来，调调调半天，还有 $10$ 分钟时终于把那 $9$ 分捞到了。
总计：$21+18+43=82$
晚上又去燕园吃饭，吃完饭拍面试安排，然后走迷路了走到了未名湖。
回宾馆写游记……
Day2
早上去面试，没有 SCOI 那么坑……
（第二个教室之前的同学似乎吹牛吹得有点久，时间不准）
你们“石室联合中学”的“联合”是什么意思?
刚刚有个石室中学的同学……你们石室联合中学与石室中学是什么关系？
答：没有关系
中午吃完饭就去考场了。
考试
大致题意：
- T1：你有 $n$ 只鱼（剧毒鱼和小鱼）（有顺序，已给定），对方有圣盾鱼与大鱼，大鱼被剧毒鱼攻击后消失，圣盾鱼被任何鱼攻击后变为大鱼；$Q$ 次询问 $(x,k)$：你进行 $k$ 次攻击，第 $i$ 次用自己的第 $i$ 条鱼攻击对方的任意一条鱼，求最大的 $y$ 使得对方有 $x$ 只大鱼，$y$ 只圣盾鱼时你能消灭对方所有鱼，不存在 $y$ 的话输出 $-1$。$n,q\leq 4\times 10^5$。
- T2：定义 $f(a[0\dots n],p[1\dots n])$ 为将 $a$ 自上而下写出来，中间依次画上长为 $p$ 的分数线后得到的分数值（如 $f([2,3,4],[1,2])=\dfrac{\ \dfrac{2}{3}\ }{4}=\dfrac{1}{6}$）。给出长为 $n+1$ 的序列与 $[1\dots n]$ 的排列 $a,p$，$Q$ 次询问 $f(a[l-1\dots r],p[l\dots r])\bmod 998244353$。$n,Q\leq 5\times 10^5$。
- T3：给出带权无向图 $G$，在其基础上添加 $(i,i\bmod n+1,10^9)$ $n$ 条边（一圈）；求两两节点之间最小割大小之和 $\bmod 998244353$。$n\leq 7000,m\leq 10^5$。
第一感觉比起昨天要可做得多，于是先把 T1 的二分+暴力判断的暴力写了 $20$ 分；
接着颓 T2，建了个二叉树，然后就水过 $O(n^2)$ 的点和随机数据的点了。
细节处理半天处理不好，自闭了/kk
然后玄学 ST 表+二分套二分+前缀和把 T1 写了，写完才 15:12
分析一波 T2 分析不动，写 T3 网络流暴力，写半天有跑不快/写不对，又去看 T2……就这样循环了剩下大半个考试，最后 $165$ 滚粗/kk
一大堆提前 AK 离场的，wzbl/kk
吃完饭回宾馆写游记/kk