集训第一周总结

感觉出现了很多的问题，现在来总结一下。

先对这五天的来分别概述一下情况。

\(2024.10.5\) 在 \(T2\) 卡了题，后面的也不会。\(T2\) 是加强版的第 \(K\) 大子集问题，感觉对这种求第 \(K\) 大的东西不是很擅长，想了半天也没整清楚怎么样才可以高效地、不重不漏地按大小顺序遍历到所有方案。\(T3\) 虽然知道肯定要结合一点贪心，但是根本不会处理交换，听了讲评才发现交换条件可以通过对价格排序，然后分两种情况来考虑。\(T4\) 没有挖掘到性质，导致根本找不到切入点，脑子又抽了，本来可以 \(O(n^2)\) 的打了个 \(O(n^2 \log n)\) 的东西（还好和 \(O(n^2)\) 一个分）。最后正解用线段树维护一下就行了。

\(2024.10.6\) \(T1\) 想了一个小时，写了一个小时（总共写了三遍，前两遍不知道为什么写错了），发现时间复杂度最坏是 \(O(n^2)\) 的，而且还用了指针，常数大到爆，感觉过不了，但是应该能拿很多分（最终结果 \(98pts\)）。这两个小时中途还看了一下第二题，没什么思路，写完 \(T1\) 就想着把 \(T2\) 的最大代价写了，结果方法错了，样例都过不了（其实那个方法也不是不行，好像是最后没取模），本来想过差分的，但是没看出交叉 \(\leq\) 包含的性质（这么显然都看不出来），所以还是没做出来，事实证明最小代价的正解就是差分。\(T3\) 感觉是 \(DP\)，但是觉得去重没想出来，而且感觉上还很难写，就没做，最终做法是将不同的划分方法用十种情况表示，算出不去重的方案，再考虑使用容斥去重（把轮廓线重叠在一起），这样就可以正确统计方案。\(T4\) 仙人掌看着就不好写，直接放弃，正解是把仙人掌变成圆方树，然后树边和环边分别考虑就行。

\(2024.10.8\) \(T1\) 做过类似的题，直接秒了。\(T2\) 已经想到快速排序了，但是实在不会处理块内如何划分，最后就是把 \(\leq mid\) 的和 \(> mid\) 的分别设为 \(0,1\)，然后以一个 \(0/1\) 连通块为间隔进行操作就可以每块以 \(O(\log_3 n)\) 的次数完成划分，最后层内可以打包统一处理，这样次数是 \(O(\log_2 n \log_3 n)\) 的。\(T3\) 只会状压，正解是价值从大到小排序，然后一定存在一个阈值，满足阈值之前的抽到就结束，阈值之后的扔掉继续抽。直接枚举阈值 \(DP\)，并结合上一些决策单调性，可以做到每次查询 \(O(n)\)。\(T4\) 根本没想到可以对每层的联通情况进行差分。

\(2024.10.10\) 前两题太水了，\(1 \operatorname{h} 20 \min\) 就做完了。\(T3\) 忘记了错排问题是怎么做的了，只会状压（怎么又是只会状压），最终可以转化到一个图上使用容斥，对于 \(a_i\) 和 \(b_i\) 连边，对于每条边要么不选，要么选一个端点。\(T4\) 没想到可以直接判定一个人是否能赢，就只写了搜索。

\(2024.10.12\) \(T1\) 感觉有点思维定式了，看到数据范围比较小就想容斥，最后做了两个小时也没做出来，其实这种数位与数位之间没什么关系的可以数位 \(DP\)，而且之前还做过这种题，只能说知识点掌握得还不够好。\(T2\) 没分析出什么东西，只写了搜索，正解是考虑每个数对最终答案的贡献/系数，肯定是比较大的系数为正，后面的系数为负，然后其实 \(K\) 的系数只和正负系数的个数有关（考虑把合并的情况看成一颗二叉树），和 \(K\) 本身无关，最后求答案可以三分或者考虑一些斜率相关的东西。\(T3\) 没想出来树怎么构造，感觉构造能力还是不行。正解先考虑树，对于 \(n\) 分奇偶性，然后对于图只需要找后面那些边的生成树，前面的全选即可，还是比较巧妙。\(T4\) 领域查询没见过相关的技巧，就打了 \(20pts\)（本来应该可以 \(40pts\) 的，但是没时间了），正解是考虑结合一下 \(DFS\) 序和 \(BFS\) 序，把 \(DFS\) 上的自己变成自己的所有 \(\leq K\) 级的儿子，这样就好做很多。

整体上能总结出以下一些优点：

• 时间分配较之前还是合理了一些，不会整场比赛死磕一道题
• 一般代码不会写挂
• 没有挂一分（这个是真的）

（好像优点就这么多）

当然还是缺点居多：

• 思维还是最大的痛点，不够开阔，总是只能做出自己见过的东西，没见过的几乎想不出来（貌似来到这边后离线比赛就只做出来过一次构造题，而且还是三四月份的时候）。感觉做思维题还是要大胆一点，总是局限在某几种思路，最好是每种可能的方向都试一下，有时候实在不行还可以打表，说不定能发现一些规律，找到特殊的构造方法
• 知识点掌握得不够牢固，一个东西学的时间久了容易忘。还是要温习一下之前学过的东西，不能学一个知识就丢掉另外一个
• 挖掘性质几乎总是只能挖掘到最浅的东西，更深层次的老是看不出来。这个应该和思维直接挂钩，所以主要还是提升思维能力
• 套路见的不够多，一些比较经典的问题根本找不到切入点（不过现在学套路也来不及了）
• \(DP\) 能力还是很弱，总是只会搜索/暴力 \(DP\)，需要结合转化、需要挖掘性质的 \(DP\) 题一般都做不出来。所以 \(DP\) 还是要多练题，同时提升自己的思维才能取得突破

希望能够继续保持自己的优点，并改进自己的缺点，在 \(CSP\) 的时候全力发挥，不要为出现不该犯的错而留遗憾，不然这一个赛季就又玩儿完了。