联合省选 2024 翻一半记

连夜赶的，等有时间再稍微润色一下（

Day -1

Lynkcat & zhh 逆天模拟赛，没想到省选最后一次模拟赛还吃了依托大的。

然而竟然打到了比较高的名次，果然我只会打答辩场啊……

但是不得不说确实涨信心了（

Day 0

上午不想写题了，鉴赏了几首 hitorie 的歌，然后写了个凸包板子就去吃午饭了。

下午一点上车去杭州，车上看了一下洛谷省选计划的模拟赛题，然后打算听会歌，结果耳机没连上直接外放了！！！当场社死。

到酒店之后借 Gold 的板子打了会 Phigros。

（这里应该有一张图）

好评如潮，说明我省选会打得非常好（确信。

然后出去吃了个晚饭，晚上又看了一下之前校内模拟赛的题，发现有些题一点印象都没了。

看完之后继续打摆，最后复习了一下矩阵相关就睡觉了。

Day 1

杭师大的显示屏终于不是傻逼的 4 : 3 了，感动中国！

先看完三个题然后开始做 T1，看数据范围就知道是 $O(n)$ 的，然后就考虑对于答案 ${} \bmod n$ 同余的部分放一起求。刚开始假了一会，然后仔细思考发现旋转 $45 ^ \circ$ 转切比雪夫距离之后两维就独立了，那么设 $X, Y$ 表示所有 $n$ 个向量加在一起的值，设当前答案为 $t n + m$，令 $(x', y')$ 为终点减去前 $m - 1$ 个向量后的值，则答案合法当且仅当 $t X - t n k - m k \le x' \le t X + t n k + m k, t Y - t n k - m k \le y' \le t Y + t n k + m k$，转化成 $[t (X - n k), t (X + n k)] \cap [x' - m k, x' + m k] \ne \varnothing$。剩下的问题就是求合法的 $t$ 的去见使得 $[tl, tr] \cap [l', r'] \ne \varnothing$，随便分讨一下就做完了。然后写完 T1 大概过了一个半小时。

接下来看 T2，先扔 Trie 上，然后考虑 $\min _ {i \in U \setminus S}(a _ i \oplus x)$ 的值就是在 Trie 上 dfs，然后考虑每次走一个儿子，如果这一位要是 $1$ 就需要把另一个儿子全扔到 $S$ 里。以为做完了就直接开写，写完发现寄了，原来是走右儿子的时候不一定这一位是 $1$ 是最优的，抑郁症。

然后想了很久都不会做，而且还有点困，就先洗了把脸，然后写了两种都跑一遍的暴力，但是显然只能过第一档，此时心态稍微有点崩。看了下 T3，发现一档暴力一档 $n!$，后面不会了，就先写了一下。

回来看 T2，发现 A 性质直接按之前假做法来是对的，B 性质由于 $S$ 里的点是确定的，所以对于有两种决策的地方可以先不做，等走到叶子的时候再考虑，此时发现每个贡献对两边都等价于直接加，因此从大到小贪心就对了，因为是 $O(n k ^ 2)$，但是跑起来很快就没管。

算了下分发现竞争力不足，尝试找 T3 的性质，找了半天置换的性质也没啥进展，突然发现 $m = 1$ 可以直接在图上考虑，那么相当于每个环都要与另一个长度相同的环匹配，然后随便算算贡献系数就行，于是就写了。

$100 + 40 + 32 = 172$，感觉应该很多人过 T2，自闭了。

出考场问 wc 几分，他说他 164，遇到 psz，150-，houzhiyuan 竟然只有 144，lynkcat 也只有 164，当时直接吓坏了，不会让我翻掉了吧？！

出考场询问了一下其他人，好像我校只有 xr 和 fhq 比较高，其他都爆了。

出去吃了个午饭，下午测了一下大样例发现过 T2 大样例的有一车人，感觉危险了。

晚上吃地锅鸡，肉好少。
shaber xr 被辣死了，然而并不是特别辣，乐。他还声称自己是他家最能吃辣的。

菜就多练，吃不起就别吃，家里是家里，外面是外面，后面忘了。

结果他家做菜放的最辣的东西是胡椒，乐麻了。
而且 xr 吃完辣的和喝醉了一样，太乐了。

听说云斗有 T1 T2 数据了，回酒店测了一下，结果 T1 70, T2 16，wtf？！心态彻底崩了，这我还打个屁啊，似了算了。

拿别人的码拍了一下，结果两题都屁都拍不出来，抑郁症。
询问了一下那老师，那老师让我测测 T2 B 性质所有 $b _ i = 2$，然后一测发现真 T 了，仔细一看发现我数据点分治写挂了，这下真爆完了。

但是还不知道 T1 和 T2 性质 A 啥情况，以及 B 性质即使数据点分治修好也还有 WA。

最后睡前又看了一眼云斗，发现 T2 变 32 了，应该是之前数据有点小锅，现在性质 A 没问题了，但还是翻盘无望，感觉回家就要被我妈强制退役了，瞬间连 Day2 都不想打了。

再看一眼 QQ，发现大家都没睡在交流病情，于是我也加入，最后以让批话哥闭嘴结束。

Day 2

看完三个题感觉好难，先想一下 T1 暴力，那么就是考虑设 $f _ {i, j}$ 表示子树 $i$ 内要让排列的第一个数是 $j$ 的最小代价，转移就直接来，然后发现满二叉树所以做完了？这把不会 swap Day1 Day2 吧？

然后写写写，调调调，过完大样例挂上拍子大概 1h 多一点，然后看 T2。

T2 看数据范围就很 $O(3 ^ n n)$，然后考虑 $k = 0$ 就直接状压拓扑序计数，接下来考虑 DAG 计数，尝试在 DAG 和拓扑序间建立双射，这样就是设 $dp _ {S, i}$ 表示填完集合 $S$ 中的数，用了 $i$ 个点，然后枚举子集转移。胡了个假做法直接冲，写完调好前三个样例花了 1h，然后大样例直接 WA，尝试调了调发现调不动，然后想了想暴力怎么写，发现是依托答辩，但还是写了，然后拍了很久又改了很久，最后发现做法假了，心态彻底崩了，润去写 T3 暴力。

然后想了一会还是看不懂题，一分也拿不到，考虑回去补救一下 T2，发现假做法虽然假但是能过 $k = 0, m = 0, m = \frac{n (n - 1)}{2}$ 和性质 B，这样拼上暴力就是 40 分，稍微安心了点。

然后继续 T3 抑郁症，最后剩半个小时尝试乱猜性质 A 结果没猜出来，抑郁了。

出来一问小猴 216，T2 分拆数 60，我直接心态崩了！这我还打个屁啊？！

然后问了下其他人，发现最高好像也就 140，漏雨也没读懂 T3，大家都爆完了。

回去路上仔细分析了一下，发现好像 Day1 少 F 一点就能打 D。问 ducati 要了云斗 D1T1 数据，发现是少判了一个 corner case，导致算时间区间的时候会把上界变大，然后随机数据下不太会有 -1，就算有这个东西也不太会变成答案。

晚上出了云斗榜，发现我 F 成云斗这样还是能有 D，瞬间有信心了。

Day 6

出分了，$90 + 28 + 32 + 100 + 40 + 0$，ZJ rank 42，F 得比云斗少，感恩，不知道有没有 D。

Day 9

补 Day1T2，拿考场代码改，发现哪里 F 了。

if (sum <= m) {
	__int128 res = 1;
	for (int i = 1; i <= n; i++) res = min(res, a[i]);
	ans = max(ans, res + ((__int128)1 << k) - 1);
}

这下笑点解析了。