【总结】学习记录（2024.9.11-10.26）

· · 个人记录

学习中需要记录的东西，遇到的问题等等都记在这里。
要成为像前辈一样的优秀的长篇小说。

2024.9.11 模拟赛

upd on 2024.10.13：
这场没啥可说的。
T2 不是很难，但还是想了一会。但是挂分了，没有注意细节。其实想的时候想到了这一点，实现的时候忘了。后面也有出现这样的问题，不应该。
后两道题确实不会做。以为 T4 有个做法，但是假了，后面的时间都放在了 T4 上，骗到了一个诡异的分数（18）。
这场其实还可以的。主要问题在于 T2 的细节问题，还有后面的时间应该去做更可做的 T3 而不是 T4，最后 T3 只有 5分走人，后面不可以再这样。

2024.9.17 模拟赛

这场写的总结是因为倒三了才写的。
还是有很多问题。后面的比赛都得写总结。

今天比赛打得非常不理想。
（可能有感冒的原因吧，头比较晕，感觉想很多问题的时候比较糊涂）
还是出现了很多问题。

第一点，T1。原来遇到这道题的时候好像在纠结于前面的搜索和期望题，对这题印象不太深，也没有补。
然后今天并没有想起来这是一道原题。
然后前 1.5 小时好像就在 T1 和 T2 之前来回跳，事后觉得当时根本没有进入一个深度思考的状态。
后面稍微清醒一点之后又去想 T1，其实一会就想到了。写代码也很简单。
但是浪费了很多时间。
主要出现的问题：

第二点，关于 T2，知道是搜索，但是真的真的完全没想到折半搜索。
写暴力写的不好导致这题得分是全班最低跟上一段讲的和 T1 有关，以及一直想要弄正解，所以暴力写的也很糟糕。
其次是对正解确实没有头绪。这个可以归结于一些知识漏洞，像折半搜索这个东西我几乎没写过，之前讲过的印象也不深，于是在我的知识大纲里几乎没有这个东西，解题时不会考虑这种做法。

总结：

后面其实没有什么可以说的了。
在 T2 没有做出来的情况下后两题也不会去想正解。

T3 高斯消元很好看出来，但是性价比不高，所以没写。也有原因是高斯消元板子细节有点多，加上有一点遗忘，估计写了也调不过，遂放弃。
至于期望，本来学的就不是很好，只能说可以解决一些较基础的问题，复杂了就不行了。

T4 20 分在预料之中，也没花多少时间，性质有观察到一些，但是也没有继续深入思考了。

总结，这场考试的最大问题在于前半场的状态问题，补题（或至少要理解透，把其中的一些套路和 trick 弄懂）问题，以及一些知识漏洞。
还有后半场感觉没做什么事情。
能感觉到这场模拟赛比正式赛肯定还是难一些，但是也能看出来以上总结的许多问题。
低级错误倒是没有，不过状态确实很重要。
接下来的模拟赛要吸取教训，让正赛不留遗憾。

2024.9.25 模拟赛

这场打的并不好。原因是（下面会讲）T2 卡了太久，把自己正解想假了，然后导致 T3 和 T4 甚至没有来得及打暴力，T4 最低分走人了，其实 60 分（好像是）很好打。整场比赛输麻了。
问题 2 个：

主要在于其中的这一步：
计算一个组合数，在 n 个数中选 m 个数，可重复，方案数显然为 C_{n+m-1}^m。此题求带权，即把每一种方案的和求出来。
有一个结论，在每种方案中，n 个数中每个数出现是等概率的。所以带权算就是 C_{n+m-1}^m\cdot m \cdot mid （其中 mid 为 n 个数的平均数）。

考场上没有想清楚这一点，想到了等概率但是否定了这一想法，以为和大小有关系。
其实是等概率的。警钟长鸣。

T3-斜率优化

模拟赛 T3。复习了一下斜率优化，发现有很多东西忘了。
关于写出斜率优化 dp 式，要点如下：
对 dp 式进行移项变化，变成形如 y=kx+b 的点斜式。

划重点：移项要遵循的原则是：
把含有 function(i)\times function(j) 的表达式看作斜率 k_0 乘以未知数 x，含有 dp_i 的项必须要在 b 的表达式中，含有 function(j) 的项必须在 y 的表达式中。如果未知数 x 的表达式单调递减，最好让等式两边同乘个 -1，使其变为单增。
（摘自辰星凌的斜率优化学习笔记）

还有：

后面两道题还没有来得及补，所以找了题解链接放在这里。忘了可以看。
（因为不让提及，所以题解链接已隐藏。前面好像也算提及，算了不管了）

2024.10.5 模拟赛

这场成绩不理想。没有垫底是因为 T4 打了 n^2 暴力，正好暴力分给的足才没有死亡。距离倒三也没多少分。

这场题目比较极端。
T1 非常水，一眼可以秒的程度。T2 开始就都很难做了。
但是题目质量确实很高，这一场后三道都不错，所以下面都写了题解，这里就不再多提解法。

主要是 T1 很快过了之后，后面的题目开不动，T2 想到了大部分（同学们应该都是），最后一小部分思维也进行不下去了。最后 T2 暴力都没有打，这个问题在 10.8 的模拟赛中也出现了。
时间安排和心态出了很大问题，T2 搞不出来连很多暴力分都放弃了。这种心态问题一定一定要规避。

最近的模拟赛都是比较折磨的题目风格，比 CSP-S 肯定还是难上不少。大概可以估计到是整体向前移了一个题位。所以相当于在正式赛中卡 T3 的话，要把握好比赛策略，千万不能在一棵树上吊死了。

因题目质量都很高，所以后面 3 道都写了题解。

2024.10.5 模拟赛 T2

这道题考场上想到了大部分，但是最后没有做出来。
不太懂为什么 O(nk) 和 O(n^2k\log k) 能过。早知道就写了，说不定能得分。
说正解吧。

首先看到这种前 k 大就很超级钢琴。可以考虑用堆做。
可重集先排序。
接着可以想到把长度在 L\sim R 之间的前缀先放进堆里，这些前缀中一定有最大值。
接下来是重点：每次取出堆顶后，怎样改动，重新放入堆中，可以保证不重不漏。
（因为这个堆的做法不漏很简单，但是如果重复则很难处理。）

首先考虑一种时间复杂度较劣的做法（O(nk)，即每次改动 O(n)）。
用 1 表示该位置选了，0 反之。
举例，对于以下这个数列：

1111100000 \end{aligned}

因为已经将长度在 L\sim R 之间的前缀放进堆中，我们考虑不改变长度，相当于交换一些 0 和 1 的位置。
对于上面这个数列，可以想到将任意一个 1 放到第 6 个位置。
每次这样操作，肯定可以保证不漏，但是会重复。
如下：

1111100000\rightarrow1111010000\rightarrow1011010100 \\1111100000\rightarrow1011100100\rightarrow1011010100

显然只是换了先后顺序，本质相同。
解决办法是每一次交换的 1 的位置单调不降。
详细不证明了，可以感性理解一下。

具体实现：
换了之后会在最后一段 1 前出现一个 0，相当于分隔。所以每次操作后只有最后一段连续的 1 可以再次操作。所以只需要每次将最后一段连续 1 的 l 和 r 放进堆里就好了。
因为每次要枚举 l 到 r 之间的每一个 1 进行交换，所以最劣情况下每次操作 O(n)，总时间复杂度 O(nk)。

不过考场上使用这种写法的 nkl 大佬说跑不满，可以过。但最好还是不要写这种玄学复杂度，容易翻车。

接下来说正解。
前面一样，正解优化了改动的方法，使得改动后的 0 ~ 2 个新的方案是原方案改动一个位置后最大的方案，所以每次操作 O(1)。
考虑下面这种情况：

1111100000

显然更小的方案是 1111010000。
改动的方法即为将最后一个 1 后移 1 位，这种方案一定是次小方案。
下一次改动有两种方式：

1111001000\ \text{or}\ 1110110000

感觉和 next_permutation 函数异曲同工。
next_permutation 函数只有一种字典序次大的方案，而本题要求计算权值和，所以次大有 2 种可能的方案。
应该很好理解：这里就是把权值最小的 2 个地方进行了改动，都是后移 1 位，保证次大。
若要保证不重，和上一种方法差不多的方式：修改的 1 的相对位置单调不升。
也很好理解：先把后面的位置的每一种可能情况都试过，再向前移，对于前面修改。到达某一个状态肯定是唯一路径。
类似于搜索的思路。

关于代码实现：
放入堆中 3 个值（还有一个权值）：l,x,r。

第一种是将 $x$ 继续后移 1 位。第二种是将 $l$ 后移一位。因为 $l$ 在此之前没有修改过，相应的它的前驱也没有修改过，所以前驱就是 $l-1$。 --- 还有一种正解，和上一种差不多。 但是把堆换成了二分答案。 大概就是二分第 $k$ 大的值，然后用搜索检验大于等于这个值的个数是否有 $k$ 个，由此二分答案。 搜索方式就是上述的方法，再加上可行性剪枝可以做到没有冗余的搜索。 --- 用堆求前 $k$ 大的套路倒是掌握了的。考场上没切掉主要还是因为没有想到扩展的方式。还是有一点巧妙的。 然后这个二分答案加搜索的套路没见过。要记住。 PS：nkoj 上莫名其妙 WA91，不知道为什么。代码大体是对的。 ## 2024.10.5 模拟赛 T3 [这道题](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=b)需要一些观察，还是挺难的。 首先一个显然的观察：如果交换了两个物品的价格，则一定有一个选，一个不选。否则交换无效。 所以赛时根据这个性质打了第一档部分分（$k=1$）：枚举不选的物品然后 01 背包，时间复杂度 $O(n^2C)$。 然后就不会做了。这道题 dyh 老师都说很难写文字题解，就只能尽量写了。 --- 根据第一个观察，可知交换了物品价格意味着一对里价格更小的物品被选，价格更大的物品不被选。 那么可以自然地想到根据价格排序，得到价格由小到大的序列。 用 $1$ 表示物品被选，用 $0$ 表示不被选，假设下面这种情况： $$ 011001010011011010 $$ 假设此时 $k=4$，**最优策略一定是将价格最大的 4 个物品与价格最小的 4 个未选的物品交换。** 交换后如下（红色代表被交换价格）： $$ \color{red}\text{0}\color{black}\text{1}1\color{red}\text{0}\color{red}\text{0}\color{black}\text{1}\color{red}\text{0}\color{black}\text10011011010 $$ 可以观察到，在序列的开头一段会被填满，结尾的 $k$ 个物品的价格不会计入贡献。 考虑另一种情况： $$ 01100111011010 $$ 此时 $k=4$，如果按照原来的方式做如下： $$ \color{red}\text0\color{black}\text11\color{red}\text00\color{black}\text111\color{red}\text0\color{black}\text11010 $$ 可以发现选取前 $k$ 个价格最小的未选的物品进行交换不是最优的，因为其与被选物品中价格最大的 $k$ 个物品“有交叉”。 所以分类讨论。 --- 第一种情况，较为简单的，当交换次数小于 $k$ 次时（保证每次交换一定有效），一定是一段前缀填满，并在后缀中取价值前 $k'$ 大的物品（否则可以再交换使得价格更小）。 所以上面例子更优的选法如下： $$ \color{red}\text0\color{black}\text11\color{red}\text00\color{black}\text111011010 $$ 此时 $k'=3$。 枚举 $i$ 和 $k'$，表示当前是第 $i$ 个前缀，交换次数为 $k'$。物品总价格为前 $i$ 个物品的价格和（需判断是否合法），物品总价值为前缀前 $i-k'$ 大价值和加上后缀前 $k'$ 大价值和。对所有这些值取最大值就是这一部分的答案。 时间复杂度为 $O(n^2)$，无需优化。 --- 第二种情况，操作满 $k$ 次。此时应为第一个例子中的情况： $$ \color{red}\text{0}\color{black}\text{1}1\color{red}\text{0}\color{red}\text{0}\color{black}\text{1}\color{red}\text{0}\color{black}\text10011011010 $$ 可以发现分为了 3 段： $$ \color{red}\text01100101\color{black}\text001\color{blue}1011010 $$ 第 1 段为前缀，由若干个被选中的物品和用于交换的物品组成；第 3 段中包含后缀价值前 $k$ 大的物品；第 2 段则是背包剩余体积选择的物品。 前缀价值 $k$ 大价值和以及后缀价值 $k$ 大价值和可以预处理，所以这里需要即时计算的就只有第 2 段的背包部分。 所以得到一个初步做法： 枚举前缀 $i$，从第 $i+1$ 位开始背包，背包到第 $j$ 位时，当前答案即为「后缀 $j+1\sim n$ 的前 $k$ 大价值和+前缀 $i$ 的前 $i-k$ 大价值和+第 2 段体积为 $C-sum_i$ （$sum_i$ 表示前缀 $i$ 的价格和）的背包的价值」。 （前缀 $i$ 的前 $i-k$ 大价值和不好预处理可以反过来预处理前 $k$ 小，然后减一下。） 其中 01 背包的时间复杂度为 $O(nC)$。加上枚举前缀，此做法的时间复杂度为 $O(n^2C)$，需要优化。 --- 可以发现做法的复杂度瓶颈在于 01 背包，每一次都从 $i+1$ 位置开始重新背包，目测有很多冗余。 这里目前听说两种优化方式。 一个是 dyh 老师讲的：将每一个前缀打包成一个物品，前缀 $i$ 在 $dp_{i,0}$ 中加入。 但是这个方法比较怪，就是他说不好写文字题解的原因，只能体感是对的。我大概也没有完全搞懂这里该怎么实现。 **第二种来自大佬@[Austin__Griffin](https://www.luogu.com.cn/user/960181) 的做法，orz！！！** > 其实有个比较好理解的做法是：枚举 $i$ 之后，需要对剩下的后缀进行背包，这里出现计算冗余。 取而代之，可以直接做一个后缀背包，这个背包可以免费选 $k$ 个物品，免费选的一定是价值最大的 $k$ 个物品，所以每次背包在 $dp_{i,0}$ 单独赋值，表示在 $i$ 的后缀里免费选了 $k$ 个物品，会选价值最大的那 $k$ 个，然后继续背包就可以了。 （以上内容选自 Frank 给我的讲解。有改动。） 这样就可以 $O(nC)$ 计算后缀背包，顺便把答案算了。 --- 然后这道题目就讲完了。 最后总时间复杂度为 $O(n^2+nC)$，约等于 $O(nC)$，nkoj 给了 2 秒，可以过。 总的来说，还是挺有难度的。最主要的是需要一些观察，然后进行分类讨论。最后一步 Frank 的优化太厉害啦！ 感觉这道题还是有一些贪心在的。 [code](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1545331)。 ## 2024.10.5 模拟赛 T4 [这道题](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=c)真难。而且抽象。 首先可以考虑部分分解法。当我们钦定 A 中一个区间选时，这个区间里的数对应到 B 中可能是分散的，像这样： $$ 001000111010010001 $$ 然后找相邻两个之间的可选区间价值最大值即可。 若枚举一个区间再算答案是 $O(n^3)$ 的，不够优秀。 稍微优化一点：枚举一个 A 中区间的右端点 $R$，左端点 $L$ 从 $1$ 开始顺推，**每少一个数相当于少一个限制，则合并原本被分隔的区间**。这个过程可以用类似链表的东西实现（并查集会带 $\log$，根本跑不动）。 这样就是 $O(n^2)$ 的做法，可以得到 45 分的好成绩。这道题部分分还是很足的，~~T4 这么轻松能搞到 45 分就可以准备跑路了~~。 接下来是正解。 --- 根据部分分解法，可以看出必须在一个序列中**定点**，对另一个序列求最大值。否则做不了。 而枚举两个点定点就已经是 $O(n^2)$，所以这一步需要优化。 但是对于定点目前想不到好的思路，所以考虑先进行分治，定下一个分治中心，**使得在 A 序列选的区间必须经过这个分治中心**。 设分治中心为 $p$。考虑在 B 序列中选择一个区间 $[l,r]$ 时，结合上面那个暴力的例子理解，A 序列长这样： $$ 001000111010010001 $$ 假设 $1$ 的位置是在 B 序列选的区间中出现的数。 在暴力解法中，原本这里所有极大的连续 $0$ 段都可以选，所以需要选价值最大的。**但是这里由于规定了在 A 序列中必须经过点 $p$，所以就不存在要选价值最大的区间，要选的区间就唯一了，就是经过 $p$ 的极大连续 $0$ 段（因为价值非负）**。 那么考虑这个东西怎样方便的表示。 首先要保证 $p$ 点为 $0$，极大则是向两边扩展，遇到的第 1 个 $1$ 即为边界，所以可以把左右边界分开考虑： 将在 A 序列中位于 $p$ 左边的数看作 1，右边的数看作 -1，未在 A 序列出现的看作 0。并把这些数值在 B 序列中表示出来，当在 B 序列中选择了一个区间 $[l,r]$，所有在此区间中的 1 和 -1 就可能成为 A 序列中的边界。那么显然，**边界即是 1 在 A 序列中位置的最大值和 -1 在 A 序列中位置的最小值构成的开区间**。 所以只要确定了 B 序列选择的区间，且有了分治中心 $p$，就可以确定答案： $$ ans_{l,r} = (sum_a[(\min_{mark_i=-1\wedge i\in[l,r]}{pos_a[b[i]]})-1]- sum_a[\max_{mark_i=1\wedge i\in[l,r] }{pos_a[b[i]]}])+(sum_b[r]-sum_b[l-1]) $$ 到这里在一层分治中仍然是 $O(n^2)$ 的。 但是有很显然的性质： + 当固定 $r$ 时（$l$ 也一样），向左移动 $l$，在 A 序列中选择的区间**长度不升**，所以其**代价也不升**。 + 点 $p$ 左右对应的边界分别具有**单调性**。 所以可以考虑移动 $l$，并对新的 $[l,r]$ 的价值进行**批量修改**。 又因为左右边界具有单调性，所以可以使用单调栈维护每一段相同的 $min/max$ 对应的左右端点。 具体实现： 当 $l$ 加入的时候，如果它为 $p$ 左边的点，就需要**更新左边界最大值**。由于是批量维护 $r$，每一个 $r$ 此刻对应的左边界值并不相同，**而这里的 $l$ 能影响到的只有左边界值小于它的 $r$**。所以使用单调栈，把单调栈中所有**小于 $l$ 对应的边界值**的弹出，并对它们更新答案（即前面的式子中的左边界值对应的前缀和）。所有小于此边界值的弹出后，就得到了当前**此边界值可以影响到的 $r$ 的范围，再将其打包放进单调栈即可**。 当前点为 $p$ 右边的点时执行的操作同理，使用一个单调栈维护右边界最小值。 答案更新由于是区间修改，所以使用线段树，对于当前的 $l$ 维护每一个 $r$ 的答案。 还要注意对于 $l$ 本身单点修改。 对于 $l$ 修改完所有对应的 $r$ 的值后，对当前线段树取一个整体最大值更新答案即可。 这样做，分治的每一层时间复杂度为 $O(n\log n)$，分治 $\log$ 层，总时间复杂度 $O(n\log^2n)$。 --- 到这一步解法已经很优秀了，但是注意到：数据范围 $n\leq 5\times 10^5$。 感觉线段树和单调栈部分已经不能再优化，所以关键在于定点。因为对于定点没有思路，所以是无脑分治定点。 优化定点： 考虑仅选取一个商场里的物品，显然选满，答案为 $max(sum_A,sum_B)$。而我们一定可以在序列中找到两个点： + $i$ 满足 $presumA_{i-1}<\frac{sum_A}{2},sufsumA_{i+1}\leq\frac{sum_A}{2}

那么如果 i 和 j 都不选，只能选取其两边的点，能得到的最大值为 \frac{sum_A+sum_B}{2}，又因为\frac{sum_A+sum_B}{2}\leq max(sum_A,sum_B)，所以 i 和 j 必有一个点被选。

--- 总结：很难，但是也有套路。单调性-单调栈维护-再用线段树维护，其实是一种套路。 很巧妙的是最后的定点。 [](https://www.luogu.com.cn/article/uzyl6gst,NY2025的题解) [code](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1546712). # 2024.10.6 模拟赛 这场打的还行。主要是 T1 给做出来了。 不过也是惊险。恰巧想到了状态如何设，恰巧在第一步就优化了 $\frac{1}{9}$ 的常数。 不过这个恰巧，我也说不太清楚。究竟是实力的体现，还是运气好呢？ 不太明白有些很厉害的题目大佬们是怎么想到的。感觉这次 T1 整个过程虽然也不是很顺畅吧，还是花了2个小时的时间，但是也没有那么艰难。 第一步常数优化是顺理成章地想到的，后面状态先设假了，后来想明白了是表示的信息不够多，改了之后就顺利地写了，后缀和优化这种东西都是没有经过思考的。复杂度的问题确实卡了一下，本来打算先写了暴力，后来想了想发现是对的。 跟之前某一场考试做出来（但是没调过）T3 感受有些相似。 但是明显这种状态不稳定，还是有一些碰运气的成分在，只能说实力还是不够。 而且这两题虽然我是做出的少数人之一，但是也还有很多同学是“临门一脚”的状态。 反正总的说来还是实力不够啊。能感觉到有一些进步（或许也没有，很难说），继续努力，脚踏实地，尽量把每一场模拟赛打好，每一场都要总结问题。 --- ## 2024.10.6 模拟赛 T1 [这道题目](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=d)总的来说并不难。 设计出状态后，转移以及优化都很简单了。 常数的优化也不难。主要还是看状态设计吧。 大概思路就是先把必须与相邻数凑对的取出来，从第一个开始向后配对（因为边界可配对的方案是唯一的，推出后面的方案都是唯一的）。可以在这里把无解判了。 接下来发现一定是 3 个相同数字一起行动，所以可以把每个数字的个数除以 3，结合后面约为 $O(n^2)$ 的做法，可以优化 $\frac{1}{9}$ 的常数。这里通过观察数据范围这个奇怪的 $n\leq 30000$ 和 1 秒时限也可以看出来，肯定是要优化常数的。 然后发现会影响后面的数的选择方案的有当前数作为第一个数，第二个数两种情况，所以状态要把这两维都设进去，否则无法转移。 然后转移就出来了。后缀和优化显然。然后就做完了。 有一点，关于时间复杂度的证明，我讲的时候好像一笔带过没有仔细解释。 因为时间复杂度分析出来是 $O(\sum_{i=1}^n a_i\cdot a_{i+1})$，所以无法直接用均值不等式。 （有 $\sum_{i=1}^na_i=n$） 稍微转换一下就行了：$\sum_{i=1}^n a_i\cdot a_{i+1}\leq\sum_{i=1}^n a_i\cdot n\leq n^2$。 这道计数 dp 还挺白给的。我赛上花的时间过于多了。 ## 2024.10.6 模拟赛 T2 神秘贪心。 不知道为什么最小值是第一问。 最大值很简单，每次取尽量大的区间就可以了，这样操作数一定最少，且代价一定最高。用笛卡尔树实现可以做到 $O(n)$，可以获得 40 分的坏成绩。 最小值的做法就比较抽象了。 赛上一直想怎样用笛卡尔树做。事实证明是作茧自缚了。思维被局限住了呢。还是要多变通。 首先对于区间 -1 的修改操作可以转化成差分，区修 $[l,r]$ 则 `c[l]--,c[r+1]++`。赛上甚至这一步都没有想到。为什么呢。 假设序列： $$ 1,1,4,5,1,4,1,9,1,9,8,1 $$ 差分后： $$ 1,0,3,1,-4,3,-3,8,-8,8,-1,-7,-1 $$ 本质上我们是每次将前面的 1 填到后面去。 用正数填负数。 根据四边形不等式： $$ \because a\leq b\leq c\leq d \\ \therefore (c-a)^2+(d-b)^2\leq (d-a)^2+(b-c)^2 $$ 证明很简单，就不写了（括号拆了之后移项算一算）。 所以这里也与上面最大值的计算方式对应了：最大值要尽量包含，也就是每次选最大的区间操作；而最小值则尽量不能出现包含情况。 最后构造最小值的方式是贪心。 从后向前枚举，把所有负数放进队列里，遇到正数就填队头，若有剩余继续填。 这样做可以尽量避免包含。感性理解，如果当前数可填的负数有多个，若不选择最远的一个，那么这个负数会比当前正数前的正数填，出现包含情况，一定不优。 然后就没了。[代码](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1543857)也很好写。 其实感觉这道题绝对难度并不高。但是就是不会。神秘贪心不会就是不会。 但是能怎么办呢，贪心题最抽象了。可以很简单，但是贪心题一神秘我就不会了。 或许以后得多练练贪心，多练思维。 ## 2024.10.6 模拟赛 T3 又是计数 dp。不会。 容斥我好像就没怎么写过。不太会。最近作业表里加了一些容斥的题目，得做做了。 这道题还有大模拟的属性。更不会了。 至今还没补。 因为最底层最多也只有 $2^{2k+1}$ 个合法矩阵，向上 4 个矩阵合并成一个矩阵，所以总数不会很多。大约 $4^k$ 个（感性理解等比数列？）。所以这个东西可以设到状态里。 但是直接 dp 显然会重。5 种分割方式有些地方非常相似，所以需要去重。 去重无非重新设计状态，使得计算的时候直接不重，要么减去重复的部分。在这里并不好重设状态，且分割方式较少，所以容斥。 看起来是两两枚举，实际上最后只有 11 种。对应的方案数乘一下容斥系数就好了。 ~~大模拟。不想写。不写了。~~ 这道题属于无论怎么样我赛上都做不出来的那一类型。 总结是 dp 和 码力的结合体，而且容斥我也不太会。得练。 ## 2024.10.6 模拟赛 T4 杜教锐评为答辩题。 ~~既然是答辩还考什么。~~ 仙人掌还没学过，圆方树也没学过。这题拿到基本就有思路了，但是极其难写。 除了倒序开题的赌徒应该也没人写了。 # 2024.10.8 模拟赛 这次考的极其糟糕。 主要在于 T1 写挂了，没有对拍导致的。没有注意细节。 然后挂的只剩下 30 分，只能垫底了。 除此以外，T2 想歪了，使用了类似归并排序，但是因为归并排序在这道题上用不了，所以想了一个四不像做法，还以为是对的。 写到后面时间所剩无几才发现假了。最后花了一点时间打了 T4 的 15 分暴力走人，T2 和 T3 都是一分没有，暴力也没有时间打了。 这场和 10.6 那一场比较相似。区别在于这场 T1 挂分了。 所以首先一个问题：无论如何，T1 是丢不起的，**必须打对拍**。 第二，两场比赛共同的问题，与 T2 死磕导致最后赌输，暴力分都拿不满。 这属于比赛策略的问题。赛场上要灵活变通，不能死脑筋。可以规定一个方案：一道题想了 20 分钟还是几乎毫无思路就该跳了，可以换换脑子，或者说先把某些暴力分写了。比如现在看来至少 T4 是肯定过不了的，可以考虑先写暴力分，不要出现最后西瓜和芝麻都没了的状况。 然后是心态的问题。不说 T2 做不出来了，最近的考试难度似乎已经让 T2 做不出来成为了普遍现象，有时 T1 不会，T2 不会，心态很容易崩掉。要保持冷静，不要孤注一掷地认为“某某题做不出来这场就完蛋了”，虽然很多时候确实有道理，但是在该放的时候要放，还是上面说的，至少要把暴力分打满。 最后，简单总结一下： + 细节。对拍。 + 比赛策略，时间分配。 + 心态。 以及，近期集训开始，一周有很多模拟赛，也暴露出很多知识漏洞，比赛的一些问题。 补题时间很够，但是发现有的时候 T3 和 T4 会出现补不动的情况。感觉还是理解不够到位，可能当时懂了，后面又忘了。如果没补，以后再看，再复习的时候又记不起来了。 所以最好是要写题解。时间不够也要写简要题解。一定要理解到位。 再一个，考试总结也要写。并不是只有考了倒三才说明这场考试打得不好。每次无论是优点还是问题都要及时总结。 ## 2024.10.8 模拟赛 T2 [这道 T2 ](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=i) 考了一个构造，比较抽象。CSP-S 真的会出这种题吗？不会被骂吗？ --- 这道题还是比较有意思。 首先可以做一步简单的转换，因为这个切牌方式不是特别好处理，可以转换为：对于 $k$ 个小区间，每个区间都翻转一遍，最后再对 $1\sim n$ 翻转。这样更方便实现，也更方便设计排序算法。（赛上这一步都想不到是不是可以原地退役了。） 接下来考虑要对一个排列排序，可以想到以某种排序作为模板，用这道题目要求的方式进行排序。 一般的排序的时间复杂度是 $\log$ 的，再观察题目要求的数量：120 次，能大概感受到是一个 $\log^2$ 的花费。 所以可以考虑基于分治的排序算法。 **归并排序**和**快速排序**。 根据本题的切牌方式，归并排序的特点是先将大区间分成两个子问题，递归后得到已经排好序的两个区间再进行合并。最重要的一步**合并操作**在本题的方式下很难实现，且花费不优秀，所以不考虑归并排序。 考虑快速排序。 快速排序的做法是选择一个数作为标准，将小于等于这个数和大于这个数的分成两个区间，再对其分别分治，然后可以**直接合并**，对于这道题目的切牌方式就十分友好了。 考虑把小于等于基准的数标为 $0$，大于的标为 $1$，可得到这样的序列： $$ 01011000110010110 $$ 我们要通过区间翻转的方式把所有的 $1$ 移到右边。 首先，连续的 $1$ 和 $0$ 可以看成 1 个点。所以序列的形态一定是 $0$ 和 $1$ 交错的，上面序列变换后如下： $$ 01010101010 $$ 所以可以考虑把 $1$ 移到一块，使其合并，减少 $1$ 的数量，最后形成一个 $01$ 的状态就是完成了操作。 考虑每 3 个数字，翻转后 2 个： $$ 00111000110 $$ 然后合并： $$ 01010 $$ 相邻的 3 个 $1$ 会合并在一起。 用这种方式类推下去，可以算出这里的操作次数是 $\log_3(r-l+1)+O(1)$ （加上一些常数）。 所以每次的标准选中位数就可以了，分治下去就是 $\log_2$ 的。 时间复杂度为 $O(n\cdot \log_2n\cdot \log_3n)$。 根据主定理：$T(n)=2\times T(\frac{n}{2})+n\cdot \log_3n$ 得到。 但是为什么是这个结果我不知道。主不在乎。 所以最后操作总次数为 $\log_2n\cdot \log_3n$，可能带一些常数。 有一个细节。因为在实现时并没有真正实现整个序列翻转这一步，所以根据最后总次数的奇偶性，可能最后是倒序的（同时输出时也要翻转输出）。再翻转一下就好了。 代码细节比较多。 [code](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1548214). ## 2024.10.8 模拟赛 T3 [好难](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=j)。真的不会。 期望 dp，还是带决策的期望 dp。 真的不会。 dyh 老师讲了之后应该懂了。但是好难。 为什么 MikeZ 会认为我们能做出来 $n^2$？？？ [大佬lm的题解 orzorzorz](https://www.luogu.com/article/1aqxhqaq) 这题就不写题解了。后面还有 T4 这个大工程。如果记不起来了看上面大佬的题解就好了。 这道题目也给了我一些关于性质的启发。 ~~因为没有保底机制，~~ 如果进行到第 $i$ 轮了则说明后面的期望一定会更大，否则就会直接停止。所以得出的结论是每一轮区分好牌和垃圾牌的阈值其实与抽到了什么牌无关，$C$ 确定的时候这个阈值也就确定了。 当然还有关于单调性的分析，最后 $O(n^2)$ 优化成了 $O(n)$。 还是很厉害的一道题。 ~~加强了我对抽！卡！的理解。~~ ## 2024.10.8 模拟赛 T4 还不会。会了回来补。 # 2024.10.10 模拟赛 这场考试不理想。 首先是 T1，继上一场 T1 挂了之后，决心一定要对拍。然后这一次对拍了还是挂了。 原因不是对拍的锅，是因为题面没有讲清楚（是否必须选择点对），但是通过样例 2 可以看出题意，但是最开始我样例 2 直接过了。后来想到了这个问题，临时加了一个特判，但是没有再测第 2 个样例，所以死掉了。 总结，题面确实有问题，但是更多的是我不够严谨。一定记得以后每改动了代码都要把所有样例测一遍，避免这种弱智失分。 其次，这个其实不好说。这场比赛 2 个小时把前两题都做了，然后开始想 T3 和 T4。但是，因为上一场的教训，我对 T1 极其不放心，而 T2 在我看来中间 check 的部分细节很多，很怕写挂，所以后面两题看了 40 分钟之后又跳回去写对拍了。 结果是对拍毫无作用，分数没有提升，T1 也因为是边界情况所以拍不出来，花了一个小时做了一些无用功。最后还剩半个小时时对拍妥当了，时间只够写最低档的暴力了。 最后只有大众分，甚至于因为 T1 的挂分，比大众分还少 10 分。 而之前考虑 T4 的区间 dp，其实再想想或许能写出来。但是由于跳回去对拍了，也只能作罢。 不好说的原因大概是，这次是因为没有拍出来错，所以觉得不值得。但是如果有错因此被拍出来了，那又是一件好事。 所以就不对这个事情感到后悔了，这样做其实是妥当的。 这里有一个事情要注意： 对于一场比赛一定要有**难度评估**。这是很重要的。 举例： + T2 想了很久，感觉正解边都没有摸到。 如果出现这种情况，大部分时候是这场难度较高，区分度就在 T2（不排除想歪了）。所以根据这个要及时调整比赛策略。比如可以先将 T2 放一放，把后面该拿的暴力分拿了，有个保底，再考虑 T2 是冲正解还是转而考虑暴力。并且注意，在这种情况下一定要及时止损，如果觉得正解出不来了，不要放弃暴力的分数。 + T1 和 T2 比较顺就过了，说明别人也有解出这两题的能力。所以这两题就不能丢分，丢分就意味着输了。这个时候就必须要考虑对拍了。 但是以今天这场为例，对拍花费了太久时间，导致后面的暴力打不出区分度，没输，但是也没赢。所以在保证基础分有的时候，对拍的速度要提上去，为后面争取更多的时间，尽量打出区分度。 所以，根据难度，调整相应的比赛策略，最后才可能赢。 这一点很重要。 简单总结： + 对拍不够快。 + 注意细节。 + 时间规划。 + **比赛策略。** ## 2024.10.10 模拟赛 T1 [比较简单的树形 dp](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=l)。解法不提了，主要提一下这种细节很多的题目，班上加上我有 4 个人挂分，甚至有两位挂到了 50，可以说是很严重的失误了。 对于边界情况一定要仔细考虑，包括计算答案，转移等等。 **T1 不能挂分。** ## 2024.10.10 模拟赛 T2 [这道题目](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=m)也挺一眼的。套路。 这个二分的套路和 10.5 的 T2 差不多，主要是要做到没有冗余的 check 和算答案。否则时间复杂度可能会假掉。 只有一点想提一下：使用 dfs 还是要慎重。要注意递归层数很多的情况。这道题目在使用笛卡尔树的时候，为每个点划分其管辖区域的时候使用了 dfs，但是这道题目有 $a_i=i$ 的数据，导致递归层数非常多，在没有开 O2 的情况下就爆栈。后来及时发现改成了 bfs。这种细节问题要注意。 （但是不知道最后评测机上这种写法会不会出问题？在本机上开了 O2 就没事？） 还有，这道题细节也很多。要注意。 这次没写挂，也是对拍了。以后遇到这种题最好还是得对拍。丢不起。 ## 2024.10.10 模拟赛 T3 dyh 老师说[这也是一眼题](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=n)，不过对于我们班同学来说只有 Frank 会觉得一眼。~~（原因能说吗？不能。）~~ 未完待续。 ## 2024.10.10 模拟赛 T4 [抽象题](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=o)。但这道题还是挺有意思的。 首先因为石头剪刀布互相克制，考虑分别转成 2,1,0，一个点为 $a_i$，则可以赢 $(a_i+1)\mod 3$，这一步操作方便实现。 关于部分分，可以考虑区间 dp 一类的解法，总之最多也只能做到 $O(n^2)$（maybe?）。 但是数据范围 $T\leq 10,n\leq 3\times 10^5$，显然需要一个接近 $O(n)$ 的做法，$log$ 都不够。 所以这道题其实不是 dp。 考虑常见的计数 dp，即每一种方案都要计入且数量较大。通常伴随着取模操作。对于那种题，并没有乱搞做法，乱搞一定算不出正确的答案。 但是对于这道题不一样。它并没有要求算出每个人获胜的方案数，只要求算出可能赢的人的个数，答案范围在 $n$ 以内，所以可以不考虑 dp，直接考虑枚举每一个人，直接 check 其是否有可能获胜。 --- 考虑当前 $a_i=0$。 显而易见的，如果最后 $i$ 要获胜，它一定会胜一些 1 来获得胜利。所以如果可以通过操作，使 $i$ 两边的数只剩下 1，就可以获胜了。 两边可以分开考虑。 假设一段里有 2，可以用 1 去消除；如果有 0，可以用 2 去消除；所以对于这个 0 来说，只要它的两边都有 1，就可以保证两边最后都消成 1，就可以保证获胜了。 看着很对，其实是错的。 考虑这种情况： $$ 210 $$ 如果要消去 2，则用 1 消除，但消除后 0 就无法被 2 消除，如果希望消除 0，则必须用 0 先消除 1，再用 2 消除 0，但是最后剩下的就是 2 而非 1 了。所以这种情况下无法使得最后只剩下 1。 但是只要有 1，就一定可以消除所有的 2（若有 0 阻隔，用 2 把 0 消除就行了）。 所以可以得出结论，当我们想要保证最后留下的是一些 1 的时候，0 并不一定能全部消除，可能会有剩余。又由于 0 可以消除 1，所以最后序列会变成若干个 0（可能只有 1 个）。 在这种情况下，第 $i$ 个人就不一定能获胜了。 但是注意：**如果可以通过操作，使 $i$ 两边的数只剩下 1，就可以获胜了。** 这里的只剩下 1 并没有规定 1 的个数，只要是 1，就可以被 0 消除。所以上面的判断方法可以放到这里，具体来说就是： check 一个位置 $i$ （假设 $a_i=0$）是否有可能获胜时，只需要分别 check 区间 $[1,i-1]$ 和 $[i+1,n]$ 是否可以消成若干个 1 即可。 那么由于在这里我们并不限制 1 的个数，所以判断是否合法，需要对于区间里的每一个 1 判断。 设当前 check 的区间为 $[l,r]$，当前位置为 $x$，满足 $l\leq x\leq r,a_x=1$： + 区间 $[l,x-1]$ 中有 2 （对于 1，相对于 0 的条件的数值循环一位），或区间 $[l,x-1]$ 中只有 1。 + 区间 $[x+1,r]$ 中有 2，或区间 $[x+1,r]$ 中只有 1。 只要满足条件，说明区间 $[l,r]$ 可以消成全 1。而若 $[1,i-1]$ 和 $[i+1,n]$ 都满足，则 $i$ 位置可以获胜。 对于 $a_i=1$ 或 $a_i=2$ 是类似的，条件数值循环 1 位即可。 每次枚举一个位置 $i$，check 是否可以获胜，check 内部需要枚举所有 $a_x=(a_i+1)\mod 3$ 的位置，只要有一个 $x$ 满足条件即可。这里使用前缀和判断。所以 check 复杂度 $O(n)$。到这里就得到了一个 $O(n^2)$ 的做法。 根据前文所述，还需要优化。 --- check 一个区间 $[l,r]$ 是否可以消成若干个 1，对于一个位置 $x$（假设 $a_x=1$），判断区间 $[l,x-1]$ 是否合法有 2 种条件，满足其一即可。区间 $[x+1,r]$ 同理。 所以对于一个位置 $x$，一共有 4 种可能的情况是可行的： 1. $[l,x-1]$ 和 $[x+1,r]$ 都包含 2。 2. $[l,x-1]$ 包含 2，$[x+1,r]$ 全 1。 3. $[l,x-1]$ 全 1，$[x+1,r]$ 包含 2。 4. $[l,x-1]$ 和 $[x+1,r]$ 都全 1。 首先对于最简单的情况 4，只需要一个使用前缀和的特判即可，时间复杂度 $O(1)$。 对于情况 1，可以发现只要找出一组 $(x,y,z)$，满足 $x<y<z,a_x=a_z=2,a_y=1$ 即可。又由于每次都是枚举 $i$ 分别 check 区间 $[1,i-1]$ 和 $[i+1,n]$，所以这其实是一个前后缀的问题。只需要 $O(n)$ 分别扫前缀和后缀，分别求 212 第一次出现的位置（在前缀中为 $z$ 最小，后缀中为 $x$ 最大）。对于 $i$ check 的条件即为： + 若当前检验前缀，则须满足 $z_{min}<i$。 + 若当前检验后缀，则须满足 $x_{max}>i$。 若满足，则满足情况 1，就可以说明当前 check 的区间满足条件。 对于情况 2 和情况 3，先看两个显然的性质： + 若有 $i<j$，则有 $presum_{i,2}\leq presum_{j,2}$（单调性）。 + 若有 $i<j$，且区间 $[1,i]$ 不满足全 1，则区间 $[1,j]$ 也不满足。 真的很显然。 对于后缀同理。可以发现这两个条件的单调性刚好是反过来的。 具体而言，满足全 1 在固定一个端点时区间长度越小越容易满足；满足有 2 在固定一个端点时区间长度越大越容易满足。 对于情况 2 和 3，左右两边分别满足一个条件，则一个区间尽量小，另一个尽量大。 所以最容易满足情况 3 的就是区间中的第一个 1，最容易满足情况 2 的就是区间中的最后一个 1。若这两个位置都不满足，中间的位置也不可能满足了。 又由于所有区间都是原序列的前后缀，所以这两种 1 的位置可以预处理出来。 然后用前后缀和 $O(1)$ check 就行了。 --- 通过分类讨论，check 的时间复杂度优化成了 $O(1)$，所以总时间复杂度 $O(n)$。 总之，思路还是很巧妙的。代码细节也比较多，有很多需要预处理的东西。 [code](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1550262). # 2024.10.12 模拟赛 考的很糟糕。 2 个原因： + T1 不会。 + T3 暴力能挂 5 分？？？！！！ 冷静一点仔细分析。 首先，T1 这次没有做出来是非常大的失误。这一场是最近的 5 场模拟赛以来第 2 次一半以上的人不会 T1，但是区别是我认为这次 T1 比上一次简单很多。不应该。 至于赛时为什么没有做出来，我认为是抽风了。 最开始一直不会，想了很多做法都算不对。有点急，然后就去体检了。 这里有一个地方做的还算可以：回来之后仔细考虑，**评估了这场的难度**，然后把 T1 放了，先去写了 T3 和 T4 的暴力。因为这个行为，最后没有出现暴力分都没拿到的情况。 但是 T3 暴力为什么会挂 5 分至今不得而知。 然后考虑了一种错解，是按**数位**做的。代码快写完的时候发现假了。 这里是第一个问题：**没有想清楚正确性就开写**，这个假做法又长细节又多，浪费了很多时间。 为什么会犯这种低级错误，是因为确实急了，担心 T1 不会做这场就废了。没有仔细想好。心态问题。 发现假了以后就更急了。 接下来想到了正解的 90%。想到了数位 dp，想到了状压每一个数是否顶满限制，也想到了时间复杂度是 $O(2^nnm)$。唯独把前面错解的**按数位来 dp** 给忘了。 我真的服了啊。不按数位 dp 是什么数位 dp 啊，为什么想到了数位 dp 还是不会啊。为什么前面按数位 dp 这里非要按数字 dp 啊。 非要按数字 dp 的结果就是完全想不到到底怎样才能把信息表示全。不然算不了。 然后心态崩完了。T2 也没仔细想，稍稍想了一会还是只写了 5 分暴力跳回去继续看 T1。 最后因为也有一些人和我一样不会 T1，依赖有几个人没打 T3 暴力所以没进倒三。 为什么会这样呢。为什么有的时候就是会卡住。 明明做法都呼之欲出了还是不到。心态还会崩掉。暴力还能打爆。 问题很多。 + 心态心态心态。老生常谈的问题，但是很多时候还是很难保持冷静。这个可能只能慢慢来。 + 何老板说得对。考试的时候一定要注意，读题要在草稿纸上记下一些关键信息，或者有可能被忽略，后面忘掉的信息。想解法的时候要有记录，有一些细节想的时候要写好，不然实现的时候可能会忘掉。一些想到的 trick，算法，思路要写下来写下来写下来！不要抽风了把想到的东西忘掉！ + 开始写代码前要考虑仔细！不要拿到就开始写，想清楚！ 以后不能再有这种情况。 ## 2024.10.12 模拟赛 T2 很神奇。还是一道偏思维的题目。我不会的那种。 首先，这道题的操作看着很眼熟。像一位故人：哈夫曼树。 但是不太一样，这里的权值计算是：$k-x-y$。 未完待续。 ## 2024.10.12 模拟赛 T3 感觉没有完全懂啊。后面的证明 dyh 老师讲的好草率啊。 大概是说，先考虑为树的情况，可知 $n

为偶数时 n 个点一定都可以变成奇度点。然后直接从叶子节点向上删边就可以了。相当于每一个点都有一条连向父亲的边可以更改奇偶性。

对于一般图，建出一颗生成树，不在生成树上的边都保留，生成树上再按照上述方式做就可以了。 保证字典序最大，就以边的编号为权值做最大生成树。这样可以保证删去的边的编号尽量大，达到字典序最大的效果。 不过因为对这个解法尚有一些疑问，所以简单写了一下。以后可以再思考思考，或许能想明白呢。 ## 2024.10.12 模拟赛 T4 很新的套路。我不会。 dfs 序套 bfs 序。 # Week 1 小结 一周（还要多几天）共打了 5 场模拟赛。加上之前的一起总结的话，一共有 8 场。 总的来说，8 场里有 1 场是极其糟糕（2024.10.8），原因是 T1 挂分。 其他场次有 2 场发挥还算满意（2024.9.11 和 2024.10.6），这两场都是做出了一道只有很少人过的题，并且后面的暴力都打得不错，排名也因此比较好看。 剩下的场次只能说中规中矩，有的时候暴力打得高一点往前靠，有的时候暴力打得不好或者正解挂分往后靠。 但是发挥还算稳定，除了 10.8 那一场没有出现很重大的失误。 还是记录一些出现过的问题： + **注意细节，不要挂分**。这一点在 10.12 模拟赛的总结中有详细说明，关于如何避免细节失分，以及记录思路。 + 比赛**状态**：比如千万不能犯困，这与前一天的休息有关。要休息好。 + 知识漏洞。目前已发现的：搜索（已经补过，当然还有待加深），计数 dp（包括容斥等技巧）。 + 不擅长的部分：dp（老熟人），数学（老熟人，不过近期模拟赛没怎么出现很数学的题目），思维（硬伤）。 + 还有一些套路。做题要及时总结。 + 之前有补题不到位的情况。最近集训期间不会有了。时间充足+会写总结。 + 对简单题不要先入为主。要变通。格局要打开。 + **考虑清楚**。不要把正解想假，也不要没想清楚就一顿狂写错解。代价是惨痛的。 + 暴力要打满。不要放弃任何能打的暴力分。这个关系到**比赛策略**的问题，根据 T1 或 T2 的难度估计这场比赛的难度，从而使用正确的或说最合适的比赛策略。这一点在 10.10 模拟赛的总结中有详细说明。 + 还是注意细节。这里着重强调**丢不起的题要对拍**。 + **心态。不能崩。** 要保持冷静，做出正确的决策。 + 打暴力和对拍的速度不够快。 没有犯过低级错误。当然这是基本的。 S 组的考试宗旨还是一个求稳，一定要一等的求稳。因为它决定了很多东西，包括今年后面很多活动的入场券。保持稳定我在绝大部分情况下是做到了的。以后要继续保证这一点。 集训期间时间很多，通过写考试总结和题解，也算是把补题这个事情做的更好了一些。希望通过这个方式能够对我有一定的帮助。至少总结提到的问题要注意起来，不要在同一个问题上栽倒多次。 所以继续努力，好好改进提到的问题，毕竟短期内不可能要求实力突飞猛进，还是稳扎稳打，将现有的实力尽数发挥出来，最后收获一个好的成绩。 # 2024.10.15 模拟赛 今天这场比较一般。 主要问题在于对难度的评估。还是先按顺序讲一讲。 先通读题面。 首先 T1 就弱智了。真的不明白，明明就是每一位取并，非要拆成 $\log$ 位算。最后时间复杂度变成了 $O(n\log w)$。。。脑子不太聪明。 然后花了 40 分钟左右过的。但是这个时间也太久了。不应该。后面对拍了，也没有查出错。总共花了 1 个小时左右。太慢了。 然后开 T2。但是不会。加之今天不知为何很困。真的很困。接下来的半小时好像没做什么事情，T2 也没有想出什么名堂。后来发现当时想的建拓扑图的方式可以判有没有解，但是结论依旧猜不到就是了。 跟 T2 磕了很久啊。不应该啊。 后来觉得 T2 不行了，代码也没写，这时净得分还是只有 100，于是跳到后面去写 T4 的 20 分暴力了。还因为一些弱智的问题调了一段时间。 然后觉得 T2 真不行了。开始写暴力。觉得 dfs 不好处理，破天荒地写暴搜用了 bfs。不过这道题找最小值好像 bfs 确实好一点。 写完调了一下发现前两个样例跑的飞快。想尝试一下测 $n,m\leq 50$ 的点。 然后差点把自己玩死了。 开始测了之后发现几秒没跑出来，感觉不行，这时候移动鼠标想把窗口关了。然后发现鼠标拖不动，卡卡顿顿地缓慢移动。也点不动。整个电脑卡死了。过了一会鼠标好了，流畅了，但还是点不动。这时候我慌了，死机了的话代码没了怎么办？？？ 由于刚刚点了 windows 图标，我怕乱点点到关机键，索性不动了。然后果然页面开始变，我之前点的东西生效了幸好没关机。然后即看着它一会蓝屏一会黑屏，抽搐。 5 分钟之后好了，回到了桌面，所有窗口都被关了。代码还在。万幸万幸。 ~~但是极域好像没了。~~ 长教训了。以后再也不会用 bfs 暴搜测大数据了。不然卡死了就完了。我猜测是队列扩爆了，然后空间爆了。 然后已经 11:30 了。我终于想起了被我遗忘的 T3。 为什么呢。看到计数就本能认为比较难，加之其 T3 的位置。所以最开始就认为很难。通读题面的时候没有细想。 然后几分钟就会 $O(n^2)$ 了。马上写了，还稍微调了一下，大样例直接过了。哈？？？ 然后发现优化很简单。树状数组就行了。这时候还剩 5 分钟哈哈哈哈哈哈哈哈哈哈哈哈！！！然后没写完。然后考后加了一个句子就过了。然后痛失 35 分。 痛，太痛了！！！ 总结一下问题： + 想歪了。不过其实问题不大，还是能过。简单题的耗时不能太长啊。 + **不 要 用 b f s 暴 搜 测 过 不 了 的 样 例 ！ ！ ！** + 严重的问题，虽然通读了题面，还是丢了不该丢的分。 + 一个是不要错误估计了题目的难度。题目不按难度放在正式 S 的赛场上出现的概率真的不低。放平心态去看每一个题，不要先入为主，不要先入为主，**不要先入为主！！！** + 再一个，比赛策略得更新了。以后这样，通读题面之后，先把每道题各自思考 5 分钟左右。然后先做 T1，如果在这一场 T1 比较简单的情况下，过了之后请**将 T2,T3,T4 都各自思考至少 15 分钟左右！** 如果遇到这种题目不按难度放的，可以分辨出来。如果不是这样，这个思考时间可以考虑到暴力该怎么打。**不亏的！** 然后注意这期间想到的东西都请**记录下来！** 因为后面可能会先去做别的题，有可能想到的一些点就忘了。还有一些细节问题，之前的总结里也说过了。要注意啊！ 差不多就是这样。提到的问题要改进。 ## 2024.10.15 模拟赛 T2 结论题。 首先注意到如果出现这种情况： $$ 10\\ 01 $$ 肯定无解。考虑第一行的 1 和 0 的操作方式一定不同。假定 1 用行操作，则 0 用列操作，对应的第二行的 1 用行操作，第二行的 0 用列操作，然后就回到了原点，再来一次等于再来 n 次。 更加广义的，这种关系只要成环了就是无解的。环每一次是行列交错加上 01 交错。 想到建图。 对于一个点，若为黑点，则其所在的行与列连一条黑边。若为白点反之。 判断是否有环即可。 要注意，环不仅要求行列交错，还要求 01 交错。但是这图显然是一个二分图，所以不需要判断，因为奇环不合法，[二分图里没有奇环](https://www.luogu.com.cn/problem/T523877)。 判无解这一步是 $O(n^2)$ 的。最多 $n^2$ 条边，判无解跑一遍图即可。 好了接下来就抽象起来了。结论不会啊。 首先，因为每一个点至少要被覆盖一次，所以每一行都要被覆盖一次或每一列都要被覆盖一次。 行覆盖完全时列不需要覆盖完全，反之同理。 假设当前行需要全部覆盖（列同理）： 假设某一列不覆盖。则剩下不需要覆盖的列一定和这一列完全相同。很显然吧，不需要覆盖说明行覆盖出来就长这列的样子。所以一样的都不用覆盖。 所以有个结论：答案最大值为 $n+m-\max \{ 相同的行的数量\ or\ 相同的列的数量\}$。 当然要先把无解判了。可以证明使用答案最小的做法做一定有解。 怎么证？不会！ 这里是让一个学生讲的。他讲的我没懂。然后 dyh 老师让我们自己思考。 感性理解一下吧。如果会了再写。 ## 2024.10.15 模拟赛 T3 水。 ## 2024.10.15 模拟赛 T4 > 好题啊，_____________________________。 思维题。 确实是很有趣啊。但是好难。 # 2024.10.17 T2 马拉松 > 不难想到。不难发现。不难理解。 这真的是 T2 吗？ ~~哦原来是因为是学校联考所以各学校为了彰显实力出的爆难。~~ ## A 早上的时间用于造模拟赛数据和睡觉。有思考 [A](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3046&tid=A)，但是毫无结果。然后下午就去打了个暴力，发现数据甚至有问题，$n^2$ 暴力只有可怜的 15 分。 下午还是很困。这一天吃了十多颗咖啡糖好像并没有让我更加清醒。因为直觉后面两道更抽象，我宁愿继续做 A。唉，这在实际考试中是绝对不能出现的啊。这次算任性了一回吗？下次不能了。 然后在困顿中对此题仍然思考无果。主要是太困了。然后 16:30 好像想到了该怎么用根号分治做。马上去了一趟厕所让自己清醒了一下，然后极限写代码，16:52 提交发现 T 了。然后发现是小于 $\sqrt n$ 的时间复杂度因为脑子不清醒算错了。那个东西是 $n^2$ 的，而且还因为大于 $\sqrt n$ 的部分写错了一个细节，结果只有 5 分。 然后就去吃饭了。不过对于小于的部分还是不知道怎么 $n\sqrt n$ 做。结果是去重是吧。 总的来说，这题虽然是超纲了，但是也不该想这么久啊。有一个 $\sum cnt_i =n$ 的条件就应该反应过来啊。唉。 --- 因为有 $\sum cnt_i =n$，所以可以根号分治。设阈值为 $m$，分别考虑： 对于 $cnt_x\leq m$ 的，想了很久真的没有想到怎样算这个东西对其他所有的贡献。 考虑当前固定了一个 $x$，怎样计算 $x$ 的贡献（为了不算重，我们假定值为 $x$ 的充当四元组 $(i,j,k,l)$ 中的 $(j,l)$）。 由于 $cnt_x\leq m$，所以可以枚举二元组 $(j,l)$ 满足 $a_j=a_l=x$。 此时需要计算二元组 $(i,k)$ 的数量，满足 $i<j<k<l,a_i=a_k$。相当于 $j$ 被两个相同的元素圈了起来。 但是直接计算是不好计算的，不妨换个角度考虑： 此时 $(j,l)$ 可以等价于 $(i,k)$。对于每一个 $j<p<l$ 的 $p$，都是被 $j$ 和 $l$ 圈了起来。所以不难想到在先前枚举了 $(i,k)$ 时就修改 $j$ 位置的方案数，在枚举到 $(j,l)$ 时，把总答案加上 $j$ 处的方案数。 所以就不用固定 $x$，而是直接从前向后枚举一个 $l$，然后再枚举所有 $j<l,a_j=a_l$ 的 $j$，计算答案并且区间修改 $[j,l]$。由于是单点查询，所以树状数组即可。 但是时间复杂度有问题。前面固定 $x$ 可以枚举二元组的根本是 $cnt_i\leq m$，而如此枚举则无法保证时间复杂度。 所以最后正解是：既然算不完，那就不算完。在这里我们只需要考虑满足 $cnt_x\leq m$ 和 $cnt_y\leq m$ 的 $(x,y)$ 的贡献即可。 相当于枚举到一个 $l$，若 $cnt_l>m$，既不区修也不更新答案，直接跳过即可。 容易分析出这一部分卡满了时间复杂度是 $O(\frac{n}{m}m^2\log n)=O(nm\log n)$。 还有一个小细节：区间修改时，区间中可能存在 $a_p=a_l$，这时候会算重。最后答案要对于每个值减去一个组合数 $C_{cnt_i}^4$。 --- 考虑 $cnt_x>m$。由于这样的数不会超过 $\frac{n}{m}$ 个，所以对于每一种值只需要设计一个时间复杂度 $O(n)$ 或者 $O(n\log n)$ 的算法就可以了。 那其实 $O(n)$ 也不难想了。 先考虑 $a_i=a_k=x$。枚举一个 $j(a_j\neq x)$，对于所有 $l(j<l,a_j=a_l)$： $$\begin{aligned} ans&=\sum_{l=j+1}^npresum_{x,j-1}\cdot (presum_{x,-1}-presum_{x,j})[a_l=a_j]\\ &=\sum_{l=j+1}^npresum_{x,j-1}\cdot presum_{x,l-1}[a_l=a_j]-presum_{x,j-1}\cdot presum_{x,j}\cdot (cnt_{a_j}-presum_{a_j,j}) \end{aligned}$$ 这个式子很好维护。结合代码理解一下。 ```cpp for(int i=1;i<=n;i++){ sum[a[i]]++,s2[i]=sum[x],s[a[i]]+=sum[x]; //sum数组为前缀和 //s2_i表示第i个数前有多少个x //s_i表示所有值为i的位置的前面有多少个x } ll prex=0; for(int i=1;i<=n;i++){ if(a[i]==x) prex++;//对x做前缀和，式子两个部分的计算都与其有关 else{ sum[a[i]]--;//此数组在这里的作用是后缀和 s[a[i]]-=s2[i];//s的贡献里要删去当前这一位，加上之前删去的，也是一个后缀和 //所以s[a[i]]的值就是式子第一部分的值 ll sum2=(s[a[i]]-sum[a[i]]*prex%mod+mod)%mod; ans=(ans+sum2*prex%mod)%mod; //ans是总答案 } } ``` 然后注意到前面算 $cnt_x\leq m$ 的部分时只算了都小于的部分，所以这里不能只算 $x(cnt_x>m)$ 在 $(i,k)$ 的贡献，还要再算一遍其在 $(j,l)$ 贡献。然后满足 $cnt_x>m,cnt_y>m$ 的一对 $(x,y)$ 会算重，所以这一部分还要额外计算一下，用总答案减去。计算的方式和上述方法一样，略作修改即可。 这一部分的时间复杂度是 $O(\frac{n}{m}\cdot n)=O(\frac{n^2}{m})$。 --- 最后平衡规划时间复杂度。两部分结合起来时间复杂度是 $O(nm\log n+\frac{n^2}{m})$。 最平衡则要求 $nm\log n=\frac{n^2}{m}$，解得 $m=\sqrt{\frac{n}{\log n}}$，总时间复杂度为 $O(n\sqrt{n\log n})$。 ## B 神秘题。 不会。 什么差分约束。 upd on 2024.10.24: 完了，前几天没写现在已经忘了怎么做了。 算了本来就不会。 ## C 神秘题。 不会。 > 关键词：逆序对奇偶性。 # 2024.10.18 模拟赛 > 贾老师，你看这天气多好啊![/kel](https://cdn.luogu.com.cn/upload/pic/62226.png)。 这场打得不好啊。 T1 还是想了好一会，猜了结论是每个点连边的最小值的最大值，在草稿本上证了许久，感觉没问题，写了之后稍微调了一下就过了，花了一个多小时吧。 然后 T2 就开始弱智了。感觉这个题很像倍增标记然后下放，然后贪心删最大的。但是一直就是想不通这样做在删了一个点后该怎么改变信息。啥都想了，就是没怀疑过这个做法的正确性。唉。贪心是错的。 然后正解在脑海中一闪而过：只会删 lca。但是不以为意了。唉。 可能是因为上一场不按难度放的抽象模拟赛。我就 T2 和 T3 换着看。T3 也算是想到了大部分吧，虽然还是比较好想的，但是没有想到这个转换。唉。 T4 暴力都不太想打。不好打。 总的来说，实力问题啊。不能在一条路里走到死，适时换换解法。 ## 2024.10.18 模拟赛 T1 为什么大家都想到了最小生成树？为什么我乱搞呢。 但是我是线性的！ 有一个性质，每个点的代价一定是其所连边的最小值。这样异色去染一定没问题。 不证了。水。 ## 2024.10.18 模拟赛 T2 弱智了。贪心魔怔了。唉。 明明想到正解了。 唉呀没什么好说的，要删一定是删 lca 这一点很好想。然后可以想到把 lca 按深度排序删。因为上面的可能被别的 lca 覆盖，下面的没有别的覆盖就必须自己解决。 ## 2024.10.18 模拟赛 T3 水。但是转换有一点点巧妙。 要掌握这个套路。 首先要选一些区间使得其并集为要求区间。不妨转化成把满足 $l_i\ge l,r_i\le r$ 的所有区间都选了，再判断是否满足。 ## 2024.10.18 模拟赛 T4 抽象思维题。 # 2024.10.19 模拟赛 最刺激的一集。 11:57 净得分为 0，11:58 净得分为 100。 T1 一上来就想树形 dp（敌辟！）。但是发现并不能直接做，会有很多问题。树上背包我一直都觉得是 $O(nk^2)$ 的，这道题又肯定不会和树上背包分开，这时间复杂度已经卡的很满了，所以根本没有想到还能在外面加一层二分去判定。唉。一个是实力不够，想不到啊。还有一个，树上背包时间复杂度是 $O(nk)$ 的。唉。 T1 搞了 50 分钟还是不会。就开始 T1 和 T2 换着看了。还是不愿意放弃 T1，不然要是那个时候把暴力写了的话，后面分数会好很多吧。 然后有一点还行，在 PDF 上勾画了很多重点，并且在 T2 的空白处写了很多思维过程。想着想着 10 点多，两个换着想，感觉 T2 好像会了。然后就开写。 还写了 spj。然后调到 11:30。 这个时候真的慌死了，一分还没有。然后盯着我的 T2 错误百出的代码纠结，调调调。 11:40 的时候还有问题。不行不行，然后跳回去 T1 打了 10 分的链暴力。但是因为太慌了，还出了问题，调了一会，最后也没得到这 10 分。 后来对于 T2 不甘心，11:50 又继续调。真的慌死了。然后 11:58 调过了。激动的要跳起来了。 最后 0+100+0+0 结束。虽然过了一个题，但是擦边没倒三。大家暴力分都拿的好多。唉。 这种行为，要是没调出来就万劫不复了。 以后不能再死磕了，我觉得还是要提前把暴力打了，规划好做每题需要多少时间！ 题解后面补。 ## 2024.10.19 模拟赛 T1 看到求直径，第一眼思路两个： + 两遍 dfs 求直径，在这道题上可以理解为贪心乱搞。 + 树形 dp。 略加分析可知贪心肯定不行。边权未定怎么贪心。当然了，数据范围 $k\le30$ 看着也不像贪心嘛。 但是如果考虑树形 dp 会发现也不能直接做。总之是转移会有一大堆问题。 如果非要做，时间复杂度又是接受不了的（主要在于两条叶子链合并成为直径的地方）。 这种问题，直接求解不好做，那就转判定。二分答案。 想到这一步了其实就很好做了。 问题在于时间复杂度的分析，关于树形 dp 为什么是 $O(nk)$ 的。 时间来不及了，我直接[放链接](https://www.luogu.com/article/w6wffyk1)，在目录“10.19”处。 orz。 树上背包的时间复杂度要记住。要记住。 ## 2024.10.19 模拟赛 T2 [这道题](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=%E2%92%B8)真的极限。 看一看考场上在 PDF 里写的草稿： ![](https://cdn.luogu.com.cn/upload/image_hosting/30e21e1g.png) 但是写了一堆废话。主要是想记录一下。下接正解。 --- 每一行和每一列至多存在一个点。不难想到把每个点的行和列连边。图会形成若干个连通块。 新图中一条边代表原图中一个点。新图中拥有公共点的边是冲突的。每个连通块至少要选一条边。 所以问题变成了在这个新图中选 $k$ 条边，满足边之间没有公共点，每个连通块至少要选一条边。 显然，$k$ 的最小值就是连通块的个数；由于新图是二分图，$k$ 的最大值就是最大匹配数。 所以这里要先跑一个二分图匹配。对于一个一般的 $k$ 如何去构造，大胆猜结论：每个连通块至少选一个点之后剩下的随便选就行。是对的。 所以这里也是随便搞搞就行。 比较难调的是后面的构造方案。我调了很久。 考虑当前已经选出了若干个点，剩下没有被选的点肯定是在其所在的连通块里消掉。我们可以认为这些点都跑到了被选的点的位置。 又由于复杂度要求并不高，所以直接考虑每一个点，如果它 4 个方向任意有一个相邻点被选，就可以直接去到这个点的位置。此时就给这个点也打上标记“被选”，意为其可以到达一个被选点。然后重复 $n$ 轮即可。遇到已经被标记的要跳过。 这个操作有点类似最短路的松弛操作。诶好像就是。 所以用 spfa 实现或许跑得更快？ 最后输出方案时，可以发现我们刚刚构造的东西，最先被松弛的点的操作一定在最后。又因为规则是吃掉，所以编号会改变。可以使用并查集优化，但是因为 $n^2$ 可以过，所以不优化直接暴力跳也行。 [真难调](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1557377)。 ## 2024.10.19 模拟赛 T3 不会。 ## 2024.10.19 模拟赛 T4 不会。 # Week 2 小结 没有什么特别的。 这周只打了 3 场模拟赛，都一般吧。没有特别差的发挥，但是确实不够好。 上周提到的许多问题已经有改进了。 但是感觉长期的考试和做题，精神状态和身体状态都不太好。总是会很困，很晕。可能还是要适当的调整休息，一直待在机房里，眼睛也不太受得了。 没有什么多说的了。今天晚上早点休息。 还有五天就是正式赛了。明天可能再来补一下一些注意事项！ 要积极调整状态，好好准备了！ 接下来最后的两场模拟赛要尽力，如果是所谓“信心赛”（实则难度和正赛最接近），那就要像打正赛一样。 唉，继续加油吧。 # 2024.10.22 模拟赛 信心赛考了倒三。主要是挂了 65 分。 先复盘梳理一下这场比赛的整个过程： 首先看到 T1 很激动，一眼秒了。但是还是先慢慢地读完了所有题面，然后考虑了一会才写了。8:20 过了大样例就放一边了。因为觉得这道题看着也不像能写挂的样子，想的是后面要是做不动了再看要不要对拍吧。 接着开 T2。还是比较谨慎，没有因为 T1 简单就妄下定论。想了一会先傻傻的想了一个带线段树的贪心，感觉正确性没什么问题。又想了一会发现扫一扫就可以了。 仔细考虑了正确性，觉得没问题才开始写的。 但是可能是思维的差异吧，我想的方法比较复杂。然后写了挺多代码，主要是还是有点细节。然后又有很多 bug。本来应该很快过掉的题甚至 9:40 左右才过了大样例。 **然后我觉得 T3 很可做，所有就没有打这题的对拍。** 然后就是想 T3，写了 60 分的做法（实际得分 80）。这时候感觉正解已经不难。还有一个多小时，先把 T4 的 30 分暴力拿了（实际没拿到）。 然后 T4 的 60 分要写树套树。认知清楚考场上写不出来，T3 的正解又会了，就想去写 T3。**期间考虑过 T2 的对拍，但还是侥幸心理想冲 T3 正解。** 哈哈，最后 T3 正解还差一点没调过，T2 挂了 55，T4 挂了 10 分。 --- 我只能说，今天整个策略真的没什么问题。状态真的挺好的。如果 T2 没挂，就算 T3 正解最后没调出来也打得不错。就算没调出来至少我会啊。 但是 T2 挂了。说明**不打对拍真的真的真的不行！！！** 最后发现是考场上有一个点没想清楚加了一个错的句子，直接丢了 55 分。 以后必须打对拍。想起我已经退役的同学去年 J 组因为打了对拍救了好多分。有一些没打对拍的丢了好多分。我去年比较幸运，J 没打对拍也没挂分（T4 不算！！！因为没时间打对拍了！！！）。 但是谁能保证自己不写挂呢。 说实话既然是求稳上一等，今天就不该冲 T3 正解了。最后 50 分钟给我 T2 打个对拍，改错就只需要删一个句子，还不够？唉。 **所以正赛 T1 和 T2 必须要对拍！** ## 2024.10.22 模拟赛 T2 其实是一个[很简单的贪心](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=%E2%92%BC)。 但是一定要注意细节问题啊！！！ **不 要 挂 分 ！ ！ ！** ## 2024.10.22 模拟赛 T3 小清新计数容斥 d↗p↓。 没想到赛上能想出来一个**计数容斥 d↗p↓**。不过仔细想想，[题目](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=%E2%92%BD)数据范围给了很多提示，加之本身也不是很难，所以做出来也是挺正常的。 不过以我对平衡规划的理解，没有数据范围的提示，这道题就肯定做不出来了。60 分能不能拿到手都难说。 --- 对于这种环上的问题，相邻之间有限制。一般的 dp 做法需要记录当前位置和第 1 个位置的信息，转移到第 $n$ 位时才能正确统计答案。 但是由于 $1\le c_{i,j}\le 2\times 10^5$，这里肯定记录不了第 1 位的信息。 但是不慌，先考虑暴力。 先枚举第 1 位选了哪个数，再 dp。设 $dp_{i,j}$ 表示第 $i$ 位选了权值为 $j$ 的数。 转移很简单：$dp_{i,j}=\sum_{k\in A_{i-1},k\ne i}dp_{i-1,k}$。 优化的话记录一个和，用和减去相同的就可以了。 然后这样时间复杂度约是 $O(n^2)$。但是不难发现实际达不到这么多。 由于是一个环，所以哪一个做第 1 位是可以指定的。想要时间复杂度最低，用 $|A_i|$ 最小的不就行了。 可以在前面基础上过 $n\ge100$ 这一档数据。因为均分后最小值最大为 2000，算算发现可过。 --- $n\le 100$ 的没有这个性质了。但是 $n$ 很小。 发现时间复杂度 $O(nm)$ 完全可过（$m=\sum |A_i|$）。 不妨考虑直接 dp，算重的部分即是 $a_1=a_n$ 的方案数。去重的话，不妨直接钦定 $a_1=a_n$，算 $a_2\sim a_{n-1}$ 的方案数。根据设的状态，可以使 $a_{n-1}\ne a_{n}$，但是不能保证 $a_{1}\ne a_{2}$。所以对于这个方案数还要去重，就是考虑 $a_1=a_2=a_n$ 的情况。以此类推，这就是一个容斥。 所以枚举一个 $i(2\le i\le n-1)$，每次算 $i\sim n-1$ 的方案数，然后根据 $i$ 的奇偶性对答案偶减奇加即可。 需要注意相同的数也要算出其方案数和算出来的 dp 值乘一下。 我加了一个小优化，如果当前钦定的位置中已经没有相同的数了就直接 `break`。好像要快一点。不过 nkoj 的数据不知道是太水还是这道题数据就这个性质，直接全部都用这个 $n\le 100$ 的做法做就能过。加了拼盘还会 TLE。 [code](http://oi.nks.edu.cn:19360/zh/Submission/Details?cid=2938&id=1560717) ## 2024.10.22 模拟赛 T4 还是[有点意思](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=2938&tid=%E2%92%BE)。 前面的部分比较一眼。把式子里与 $i$ 有关的部分去掉，其实就是一个直线解析式，李超树即可。但是由于限定区间，所以要树套树。但是因为 $n\le 10^6$，所以 $\log^2$ 过不了（而且还是线段树大常 $\log$）。 有同学说 60 分的 $n\le 10^5$ 不用树套树，可以线段树分治，好写一些。~~线段树分治是什么？不记得了。~~ 但是我们发现有一个性质根本没有用起来：第 $i$ 天可选择的区间是 $[\max(b_i-k+1,0),b_i]$，而 $k$ 是个定值。 区间长度不会超过 $k$。 所以可以把整个序列分为 $k$ 个一段，每一天选择的区间是一段后缀加一段前缀。然后这个东西用**可持久化李超线段树**维护一下搞搞就行了。 时间复杂度 $O(n\log n)$。 还没有补。主要是现在补这道题好像意义不大吧。CSP-S 能考可持久化？能考李超？ 可持久化李超线段树这东西也没有写过呢。就算考场上想出来了也不会去写吧。不过这个 trick 还是挺厉害的。 # 2024.10.23 模拟赛 后面补的。 无甚好说的。 T2 分块常数太大（线段树），被卡爆了。主要是一眼的根号还要带 $\log$ 的解法出了之后没有细想就写了。 唉。 最后一场了，说什么也没有意义了对吧。 # 2024.10.24~10.25 也没干啥吧。 10.22 写了一天大模拟。代码力还是十分的弱。 后面这两天做了什么我也忘了。反正就是复习，看往年真题，~~看骗分导论~~。 去 bz 试了个机，好慢啊。比 nk 的还慢。 希望键盘好用一点。 # 2024.10.26 CSP ### upd at 2024.11.4 15:29： 单独开了一个[游记](https://www.luogu.com.cn/article/yc5mxmcf)。 感觉今年比去年成熟多了。没有再写一堆废话。（不过现在看来，那些幼稚的文字还能让人回忆起往事……） 今年的主战场也从 J 变成了 S。 话是这么说，你别说，我去年对 S 的期望也是一等来着。 今年 J 打的就很草率了。随便吧。 马上 16 点查分了，祝我好运。 --- ### upd at 2024.11.4 16:00： 成绩单未上传，请稍后查看！ 延后至 17:30。 ### upd at 2024.11.5 16:29： 剩下的内容都在[游记](https://www.luogu.com.cn/article/yc5mxmcf)里。 # 补充 还没有完成的： + 2024.10.8 模拟赛 T4（不会啊） + 2024.10.10 模拟赛 T3 + 2024.10.12 模拟赛 T2 + 2024.10.12 模拟赛 T4（不会啊） + 2024.10.15 模拟赛 T4 + 2024.10.17 T2 马拉松 B + 2024.10.17 T2 马拉松 C + 2024.10.18 模拟赛题解 + 2024.10.19 模拟赛题解 有缘再补吧~ # 最后的最后 这段学习算是完结了，告一段落啦！ 有很多收获，也有很多遗憾呢。 但是没有关系，我还在继续前行！ > 旅行者，当你重新踏上旅途之后，一定要记得旅途本身的意义。提瓦特的飞鸟、诗歌和城邦，女皇、愚人和怪物，都是你旅途的一部分。终点并不意味着一切，在抵达终点之前，用你的眼睛多多观察这个世界吧。