Aly_

解题报告

D1T1 卡牌游戏

​ 考虑二分答案 $X$，枚举最小值 $mi$，于是确定最大值 $mx$。在 $a_i$ 中找出最小值最大值的位置，则中间的都不用翻，两边的都要翻。判断翻后是否合法以及翻的张数是否小于 $m$ 即可。

D1T2 矩阵游戏

​ 首先随意确定一组合法解，不要求满足 $0\leq a_i\leq 10^6$。

​ 现考虑对一行 / 一列做一个变换，把所有奇数 / 偶数位置上的数减 1，偶数 / 奇数位置上的数加 1。容易发现这样做后依然合法。同时还发现一点，这种操作使所有合法状态两两可达。

​ 注意到这是一张网格图，于是交错地对每一行加 / 减数。具体地，对于奇数行设在第一列加上的量 $c_i$，偶数行在第一列减去的量为 $c_i$，奇数列，偶数列为 $d_i$。

​ 则有 $a_{i,j}\leq c_i-d_j\leq b_{i,j}$ 的形式，容易发现这是一个差分约束问题。建图跑最短路即可。

D1T3 图函数

​ 原式改写为

$\sum_i\sum_{j\leq i}t(i,j)=\sum_j\sum_{i\geq j}t(i,j)$

​ 其中 $t(i,j)$ 表示删除 $1\sim j-1$ 后是否有 $i\rightarrow j\&\& j\rightarrow i$。

​ 发现对于一对 $(i,j)$，其必定在答案的一个前缀产生贡献。

​ 枚举 $j$，把边一条一条加进去并 BFS。若当前加入的边：

• 出发点未被遍历：加入该边。
• 出发点已被遍历，结束点未被遍历：加入该边并从结束点 BFS。
• 出发点结束点都已被遍历：不加入该边。

​ 在正图反图上都跑一遍，记录每个点最早遍历时间的 $\min$。注意及时删无用边。

​ 复杂度 $O(nm)$。

D2T1 宝石

​ 在树上 DFS，设一个点 $i$ 的权值为 $p_i$，记录其祖先链上深度最大的，权值为 $p_j=p_i+1$ 的点为 $nxt_i=j$。

​ 建立倍增数组。

​ 把一条链拆成向上向下两部分。向上部分找到深度最大的 $1$ 倍增向上跳，向下部分二分答案，二分一个答案后尽可能往小的跳，看能否和向上部分的最大值接轨。

​ 复杂度 $O(n\log^2 n)$。

D2T2 滚榜

​ 首先对于确定的 $\{a_i\}$ 序列，贪心地取 $b_i$ 使之达到最优。

​ 策略是：$b_i=\max(b_{i-1},a_{i-1}-a_i)$。

​ 于是 $\sum b_i=\sum\max(a_{i-1}-a_i,0)(n-i+1)$。

​ 记 $DP_{\{S\},i,j}$ 表示当前选了 $\{S\}$ 中的元素，最后一个是 $i$，总和为 $j$ 的可行排列数。直接转移即可。

D2T3 支配

​ $x$ 的支配集中，$fa_x$ 是支配集大小最大的那个点。

​ 加入一条边后，$x$ 的支配集发生改变时，要么 $fa_x$ 的支配集发生改变**，**要么 $fa_x$ 不再是 $x$ 的支配点。

​ 加入一条边 $p\rightarrow q$ 后，$fa_x$ 不再是 $x$ 的支配点，当且仅当删除 $fa_x$ 后 $1$ 可达 $p$，$q$ 可达 $x$。可能有一些诸如 $q=fa_x$ 的边角情况，特殊判掉即可。

​ 依次遍历所有点，看看把它删掉后哪些点不再可达。这样可以求出每个点的支配集。构建支配树。构建完后，对于每个点 $x$，我们把它的父亲删掉，看看哪些点仍从 $1$ 可达，哪些点仍可达 $x$。暴力 BFS，复杂度 $O(n^2)$。

​ 查询时在树上 DFS，综合判定即可。单次复杂度 $O(n)$。

​ 总复杂度 $O(n^2+nq)$。空间 $O(n^2)$。

总结

Day 1

​ 不知道吃了什么，有点拉肚子。晕车。

​ 开始看 T1 感觉有点想法，发现是取前缀后缀。于是打了 $O(m^2)$ 暴力。又想了想发现如果给定前缀可以用一些凸函数技巧找到后缀位置，但很难写。然后开始写，写了 2 个小时没调出来然后炸了。

​ T2。大概有这些思路：差分约束，网络流，DP，线性规划，直接构造。差分约束发现是和，以为不可做就弃了；网络流推测是一个上下界流模型但没建出图，原因是存在一个流量控制多条路的现象；DP 完全没有思路；线性规划对偶后的结果毫无特征，单纯形我又不会；最后没构造出来。打了随机化贪心和 $m=2$ 部分分。

​ T3。开始把题读错了以为是无向图然后想着用并查集可以拿到 80 分的高分，写完后才发现连样例都过不去。此时时间已经不多了，就随便打了一个 $O(nm^2)$ 暴力。

​ 然后把剩下所有时间都用来做 T1，但直到考试结束都没调出来。心态越来越崩了。

​ 考完后才发现大家 T1 都是半小时切的，想着自己怎么这么蠢。哭了一车，感觉没希望了。

Day 2

​ 在考试地点附近的旅馆住下了，这样可以不用坐车。

​ 看 T1 很快想到了一个链上的做法，类似区间数颜色的模型，但不能推广到树上。树上问题的一般处理方法：树剖，点分治，树上差分，树形 DP，虚树。纯询问问题的一般做法：莫队，离散化+扫描线，整体二分。一个一个都试了一遍，唯独唯独没有想到最简单的联赛知识点树上倍增+二分答案。心态又崩了。

​ 接着开 T3 因为我之前看了一点支配树相关内容。首先对每个询问暴力建支配树有 80 分。然后发现自己不会建支配树。心态崩没了。尝试快速建支配树无果后开始想一些很歪的点子。如果一开始暴力建了一棵支配树，之后每次都只加一条边，推测新支配树会有某些性质。想着自己已经没希望了然后开始推。居然真的推出来了。匆忙打完过样例，发现样例很水。又打了一个对拍，调了好久才过。

​ 只剩一个小时了。T2 看错题以为求总方案数，想了大概 30 分钟想出来了，然后开始打，发现怎么都过不去。仔细阅读样例解释后才发现问题所在。只有 20 分钟了，于是打了最暴力的搜索。

​ 然后结束了。大家又都做出了 T1，但没人做出 T3，所以略微有了一些希望。

Day ？

​ 然后因为各种人的各种挂分居然真的进了，感觉巨幸运。

​ D1T1 的乱搞做法被 CCF 的奇葩出题人对着卡（然后放过了其他所有错误做法）只剩 80-20=60 分。

​ D1T2 考场上一直没有看到 $a_i\leq 10^6$ 的条件，所幸小数据水把我放过去了。50-20=30 分。

​ D1T3 20 分。华师一电脑上是 44 分。发现申诉了不会提高名次感觉是浪费钱就没申诉。

​ D2T1 标准 45 分。

​ D2T2 标准 60 分。

​ D2T3 居然真的拿了 100 分。第二天的考试没怎么挂分，还是很正常的。

​ 总分：60+30+20+45+60+100=315

​ 无挂分理论总分：80+50+44+45+60+100=379

​ 良好发挥但正常挂分的情况下，理论总分：100+30+44+100+60+100=434。

​ 很遗憾，但还是很幸运的。

And

为什么 8 个共处 2 年的同学要互相逼着对方退役？