thusc & pkusc & apio 游记 & 部分题解

· · 个人记录

5-10

到了余姚。没有别的

5-11

t 营 d1，省流，100+100+100+79=379

开场看 t2，想想 abc..z*k 是合法的，然后给的前缀可以替代若干个循环节和最后一个循环节的一部分，dp 一下完了。

看 t4，提交答案题，先看 sub1-3，用快速加可得 7+5+4=16 分，sub4 打出系数，扔计算器发现二进制末尾一堆 1，结合模数 998244353 的结尾是一堆 0 和一个 1，加起来就是 2^{30}，直接加 30 次可过。

开 t1，4^d 的 dp 是显然，3^d 的 dp 也是容易的，2^d 的 dp 还是不难，关键是我把最后这玩意叫做轮廓线 dp 然后不想写，写了才发现一点也不难写。

开 t3，对于一条边，发现如果定向之后，直径就是三个部分的 max，如果考虑连叶子的边，也是两个部分，很不好求。考虑二分答案，然后进行树形 dp，保证子树直径满足条件的情况下，从根往下正向和反向的最长链的最小值，转移 sort 完贪心选，就是 2log，交上去直接过。

还有 2h+，继续看 t4，sub5 是求区间和，用线段树过了，sub6是卡时间，用前缀和和负的前缀和加起来就行，sub7 卡空间，只用前缀和，用 32 次可以给一个数乘 998244352，相当于求逆。sub8 是子集前缀和，直接 n\log n 加可过，sub9 是因子和，n\log\log n 加，时限正好卡上，空限差两个，但是注意到 8191 是素数，8192 是 2 的幂，这两个不用另外占空间。

最后前三 sub 再可以 1111,11111,11110,11011 省一次，没发现 10111 可以少一次，最后是 9+6+4+10+10+10+10+10+10+0=79

5-12

t 营 d2，省流，100+100+100+100+77(.92)=477(.92)，括号是因为小数点后可能记错

工程题，wordle，不好评价，太典了。

t1 写交互库，t2 写 hard 模式的交互库，t3 给定交互过程求可能作为答案的个数，别看错规则，都很简单。t4 告诉你信息熵的定义，让你给出最优决策，直接对着式子写，但我写的太差导致 t5 让你直接玩 wordle，跑不出来，交了好多发 t 掉的，然后交了发随机选，61 分，然后 srand(time(0))，多好几分，再 srand 了【数据删除】的生日，又多了 4 到 5 分，最后只写出来了个简单版的基于信息熵的做法，把 15 发提交用完了。

下午讲了啥不知道，然后讲题，d1t1 正解居然是 4^d 的，cdw 上去讲了 d\log v 的做法。d1t4 前三sub是搜，最后是把0去掉可过，没写可惜了。

没公布分数，前面写的是场上的分，反正是 1=，不管了

听说 yrq 姐姐 d2 499.91 是非满分最高分，zyf 499.75，怎么都这么高的。

还有一个事情，我两次 srand(time(0)) 得到的分数完全相同，很好奇评测鸭内部的 time(0) 是不是常数。对了，考试期间 10 点钟拉警报了。

晚上做火车去杭州

5-13

p 营 d1，100+100+48=248

看 t1，一眼二分然后枚举中点然后转化成 lcp，然后二分哈希，2log 果然 t 了，然后大力卡常，把进制哈希改成倍增哈希，然后交换数组两维顺序，900+ms 贴着时限过了。

t2 计算几何，显然有容易想到的 O(V^2n\log V) 的暴力枚举正方形的形状然后半平面交+类欧可做，但是巨难写。考虑枚举形状是必需的，先处理出内部的整点，枚举其中一个顶点的位置，就可以 O(V^4) 的小常数做法，过了 300 的包，然后用 bitset 可以优化一个 \omega，再注意到这个 bitset 存的是一个连续区间，直接记录左右端点就可以做到 O(V^3)，加 #pragma GCC optimize(3) 就过了。最后还删了注释和重构了代码，甚至短到只要 827 byte。

t3 的暴力有一个 dp in dp 的做法，设 dp[i][x][y] 为以 i 为根的子树，i 选的最大独立集是 x，i 不选是 y 的方案数，复杂度很高，能过 20 的点，注意到 x 和 y 是不重要的，只需知道 x-y 的值，且只需考虑在 0 到 m 之间的，这样是 O(nm^2) 的，可过 500 的点。感觉 m 大应该是维护多项式之类的，也见过类似的题，但是不会。

后来讨论发现 t1 直接贪心就行了，外层的二分是完全没用的，就成单 log 了。

晚上跟 yrq 和 zyz 去吃饭。

5-14

p 营 d2，100+100+15=215

上午有讲座，jiry 老师的自动 AC 机，感觉很厉害。

原来食堂负一楼有小卖部，还有冷饮卖，羡慕所有有小卖部的学校。

t1 一看不是好做的，搓个暴力程序，根据数据范围猜测答案是 2^n 级别的，手搓几个数据发现答案确实是 2 的幂且不会无解。这样就好做了，假设答案是 s，那么 1 号点经过了 s 次，1 号的两个出边分别 s/2 次，这样一路往下递推，由于每个点必须经过偶数次，手写一个 bitset，把 1 号的权值赋成 2^{50000}，每次除以二然后加过去，找最低位，然后暴力转十进制。是 O(\frac{n^2}{\omega}) 的，跑 50000 正好。

t2 先写个暴力，瞪出每个位置有贡献的时候左端点一定属于一段区间，交上去 assert 一下这是对的，然后考虑把它差分下画在一个平面上，可以离线这样其中【右端点】的一维是单调的，在【左端点】一维建树状数组，一次查询就是查前缀和，考虑怎样求出当前位置的区间，发现答案是单调的可以直接二分，这样就有了 O(n\log^2n+q\log n) 的做法，赛场上写的就是这个，跑了 1.5s 左右。据说好多人 2log 被卡常了，可能我是 1.5h 之前交的，评测机还没被 t3 卡死。当然 1log 做法只需把二分换成树状数组上二分。

t3 sub1 和 3 写个 dij 跑得飞快，其他都不会，罚坐 2.5h。

虽然但是，发现我这次做的四个题两个题是多个 log 卡常的，一个是直接 2000^3 卡常的，还有一个是 \frac{n^2}{\omega} 的，大家怎么说。