集训阶段反思 · Week2

· · 个人记录

10.15

还是没拉开分差啊。

本来以为 T4 能做出来的，写了一棵很优雅的线段树，然后测了大样例发现假了。

算了，先按题目顺序看看吧。

T1

简单题。但是赛上的复杂度没有做到太优，是 O(Tn \log a) 的。容易发现原操作等价于把原序列划成若干段并求每一段的按位与进行讨论。考虑最后的答案是一段前缀，则最开始可以是 a_1，后面该答案每发生一次变化，位数都会至少减 1，所以最多有 \log a 个可能答案。可以 ST 表+神秘二分做到 O(Tn \log a \log n) （我最开始也是这么想的），但容易发现有一个能划分则划分的贪心，证明是如果区间按位与 [l,r] 与 [l,r+1] 都满足条件，那么把 a_{r+1} 划分给 [l,r] 的下一段一定不劣。最后只要判包含 n 的最后一段的区间按位与等不等于 ans 就行了。

但是我神秘了，还容易发现每一段的答案一定就是整个序列的按位与。如果整个序列的按位与是 a，每一段的答案是 b，则我们可以用每一段的答案进行按位与与出整个序列的按位与，也就是 b \& b \& \dots \&b = a，但是我们又知道 b \& b \& \dots \&b = b，所以 a=b。这样就去掉了枚举答案的 \log a，时间复杂度为 O(Tn)。

大家都过了，也没花我太久时间，还对了拍的，比较合理的 T1 吧。

T2

看一眼就知道不是我喜欢的题。（可能将来会是但现在一定不是啊！）又是这种思维题，想了一会发现没想出来就去看 T3 了。这题却结论也猜不到暴力也不会打，（神秘了，一直在想什么全排列啊什么的暴力，没想到搜索。）所以交了一个全输出 -1 的代码，不作评价。

说是思维题却有点像结论题呢，貌似就说成是结论题也不为过，既然赛时没想出来，那么赛后写总结时就证明一下结论做做思维训练吧。

首先呢，是这样子的。题目既然有无解的情况，先把无解的充要条件找出来吧。

容易发现（好像也不是特别容易，至少我赛时没想出来啊啊啊）当一幅图至少存在如下矩形之一时，该图无解。

R ... B      B ... R
.     .      .     .     
.     .      .     .
.     .      .     .
B ... R      R ... B

充分性手玩即可很好证明，这样每个操作的拓扑序会形成一个环，必要性呢？

其实赛上一眼觉得这东西是个图论，但是想的却是 2-SAT。真正的证明需要的是二分图。我们可以把这种形状放到二分图上，如果 (x,y) 的颜色为 c，那么就可以把左部点 x 向右部点 y 连一条颜色为 c 的双向边，然后会发现这种拓扑序出现环的情况就会在二分图上形成一个黑白交错的偶环。

且容易发现，对于一个大小为 6 的交错偶环，可以通过加一条边（我们连的是一个完全二分图）把它划分成两个大小为 4 的偶环，且这两个小偶环中一定会有一个是交错偶环，画图就会发现比较显然。对于一个大小为 i \left(i \geq 8\right) 的偶环，可以通过加边将其划分为一个大小为 4 的偶环和一个大小为 i-2 的偶环，和上文一样，这两个环也必定有一个是交错偶环，归纳证明即可得到如果存在任何大小 \geq 4 的交错偶环，则一定存在一个大小为 4 的交错偶环，必要性得证。

那么这玩意判无解就可以直接找环做了，但是好像比较麻烦，nb_jzy 提供了一种很好的做法，但是他不会证明，让我们一起来看看。（做法其实是 nikangle 的，我先入为主了。）

做法简述为：将每一列按 R 的个数从大到小排序，如果重排后的图每一行的结构都是 i 个 R 和 n-i 个 B，则原图有解，否则原图无解。

这东西的原因就没有那么显然了，我们来通过分析建立一个映射。

首先，我们有两个无解结构：

R B    B R
B R    R B

那么在列重排后，它一定不会被破坏，顶多左右两列交换位置，这个不需要证明了。那么就可以得到：原图上是否有解等价于新图上是否有解。

nikangle 说不用证明了。

简单分讨后可以发现做法的确是对的，因为我们知道每一列 R 的个数是不增的，交换同一行的一个 R 和一个 B 后再结合上述性质，容易推出矛盾，不再赘述。

T3

简单 DP，放 T3 多少有点抽象。放 T1 估计还差不多。本来以为我计数有提升了，没想到是这道题虚高了。

T4

有点抽象的大数据结构。

赛上想了个暴力，然后发现可以用线段树合并优化，但是好像假了。于是就只写了那个跳子树的暴力，分析出来期望复杂度比较低，没想到真的连大样例都能过。其实只要一个菊花图就能卡，但不知道为什么没有人卡我。大家好善良啊。

先写点部分分吧。单组询问是比较好做的，只要看有多少条边的两端都是打了标记的点就可以了，因为是棵树所以连并查集都不用。这样单组是 O(n) 的。如果我们设立一个阈值 B，那么 k \geq B 的询问最多只会有 \lfloor \frac{5 \times 10^5}{B} \rfloor 个，直接用这个 O(n) 的暴力即可做到 O(\lfloor \frac{5 \times 10^5}{B} \rfloor n)。

那么考虑处理 k \leq B 的询问。可以发现当点 u 和 f_u 同时被标记时，连通块个数就会减少 1，那么我们可以对每一段 [l_i,r_i] 中的每一个点 u 都去统计出选中区间是否包含 f_u，可以发现这是一个在 [l_i,r_i] 中询问有关 [l_j,r_j] 的信息的问题，可以离线树状数组在线主席树解决。这样的询问共 k^2 组，每次询问是 O(\log n) 的，所以可以做到单次题目所给询问 O(k^2 \log n)。当所有 k 都取到 B 时，总复杂度有 O(\frac{5 \times 10^5}{B} \times B^2 \log n) 即 O(5 \times 10^5 B \log n)。

然后显然可以根号分治，并通过均值不等式算出 B 的取值，不细讲了。

正解和这个根号分治没多大关系，就是把原来的暴力做法用倍增优化然后用奇妙东西维护。（细节我还不太清楚。）不过能想到跳子树但是想不到倍增，果然我还是套路见少了吗。

10.18

写点有价值的东西。今天稍微有点困。

T1

水题。猜猜结论再带证明即可做出来。但是 Kruskal 复杂度没有线性做法优。线性做法是每个点朝自己距离最近的点连边。

T2

贪心。赛上一直在想错误的贪心做法。每次都找被覆盖次数最多的点然后进行删除操作。明知道这个东西很难维护但是还是觉得没问题然后浪费了我一个半小时。

可改正的点有很多：

T2 必须得做出来，没什么其它好说的。

鉴定为游戏打多了，对自己下手还是不够狠，练题练少了。决定这个周末只打一小时泰拉瑞亚。

T3

赛上想到了全部选择和离线的转换，但是这个点的覆盖的转换有些过于神奇了。但是这又属于想到这个转换马上就会做法了的转换，感觉还是蛮巧妙的。

这个东西应该也可以算作套路吧？大概就是把线段对点的覆盖用点被哪些线段覆盖来判断。

T4

赛上连 O(n^2) 的做法都没想到。也属于思维题和大分讨。可以想到只要找到中间一排叶子结点就可以确定出树的形态。如果能确定一组对应点，那么和它们距离相等的点就是叶子结点。（该对应点不能是叶子结点。）

那么就可以处理一个 dis_{i,j} 然后哈希一下就能求出对应点，当然这样做是 O(n^2) 的。通过神奇的找环来确定对应点就可以做到 O(n)。还是不太会。

10.19

这又是啥啊。

T1

让直径最小容易想到二分答案，但是我觉得判定是否可行和直接做最优化 DP 好像没有区别，所以就一直在想怎么直接做 DP。事实上这两东西是有区别的，而判定是可做的，直接 DP 则不太可做。

又和上次 T2 犯了同样的错误啊，在一个错误的做法上死磕了太久，而且好像又是 1.5h。真的不能再这样了，如果方向错了怎么磕也磕不出来，所以还是找对方向最重要。

UPD：问了 nk_fzx_sd，再思考了一下，终于算是明白了为什么。直接 DP 要同时保证子节点子树内的直径与新合成的直径的最大值最小，这玩意应该没那么好维护。但是可行性判定就不那么难了，因为子节点子树内的双链直径不会参与新直径的合成，所以只要保证不合法的状态不会被选就可以了。

T2

感觉比 T1 好做。

网格图 + 放车 + 两两互不攻击容易想到二分图。发现可行的最大值就是其最大匹配，最小值就是其连通块个数，因为每个连通块都至少要有一个位置上最后有车。（不可能全部吃完。）

所以说在最小值的情况下任意加匹配边且不超过连通块最大匹配就可以摆放出 K_{Min} 到 K_{Max} 间的所有情况。然后赛上我写了一个拓扑排序输出方案。本来以为能拿 100pts（大样例都过了啊），却只拿了 92pts，原因是我把一个 N 写成 M 了啊啊啊啊啊，，，本来能 A 的。

思路确实蛮好想，但是调了我好一会。

T3

神秘状压 DP。

普通的 O(2^m \times m^3) 状压比较好想，枚举已经扔掉的牌，枚举当前要扔掉的牌，枚举上次扔掉的牌，再枚举中间的牌是否会产生贡献。可以发现贡献这段可以预处理，然后可以做到 O((2^m + n) \times m^3)。

然后有两种优化方式，第一种是把预处理直接变成两段，直接预处理某个状态时中间所有牌的答案，查询就可以做到 O(1)，比较神秘。第二种是直接拆贡献，也比较神秘。如果前两题没想那么久估计就能打 60pts，但是实际上只拿了 5pts 的最低部分分。（不是 10pts 吗？不会我复杂度算错了吧？）

把时间堆 T1 上确实不是一个明智的选择，如果放在 T3 上想想 60pts 的做法会好很多。

T4

数据结构题也写少了，赛上甚至没有观察到这不是 polylog 的。可以发现（但是特别难）一个点的 dfs 序不能直接计算的部分只和它的祖先有关，又因为每次修改的 l,r 对应的是一段散点，我们考虑分块去处理。可以发现，当先遍历某个祖先时，只存在两种情况。

1.该祖先前序遍历。

2.该祖先中序遍历，且当前点在其右子树内。

然后就可以分块处理了。但是具体怎么个分块法自己复盘了下还不是很懂，得多想想了。这些 T4 都好难啊。

总结的总结

越来越体会到 T2 的关键之处了。无论是模拟赛也好，T2 专练也好，T2 的确就是大多数时候的翻盘希望。

不过呢，貌似新的弱点又接踵而至了。

构造/思维

一般会放在 T3/T4 吧，但是确实也见过放在 T2 的构造，比较恶心。但是没办法啊，恶心也得做。这种题就是猜结论和手玩为主，还要尝试将题意形式化，将复杂操作变得更简单。

贪心

应该也可以归到思维里但是还是有点区别的，而且考察的也比较频繁。贪心也是靠手玩和猜结论来引导出正解的，但是有的也有固定的套路，比如说像第 K 大和将路径贡献在 LCA 处计算之类的。

DP

本来说的是计数 DP 的，但是貌似是所有 DP 我都不会啊。状态设计和转移都是难点，而且现在出现的 DP 都没有那么直接了，需要拐弯抹角地推出很多性质才能正确地设出状态并且做到优秀的复杂度。转移的话在纸上写下来会比在脑内想清楚很多。

新的套路也见识到不少，套路见多了总是好的。

离 CSP 第二轮不远了。说实话模拟赛还有很多东西没有考到诶。数论啊字符串啊更是见都没见过。不过说实话，这俩东西应该也不会单独出题的，当然还是要练，把贪心啊DP啊练好就更好了！

比赛策略落实得也比之前到位了，现在只要保证不在一个题的错误做法上死磕太久就可以了！

好好练题也要好好休息，希望可以在 CSP-S 第二轮中发挥出好成绩！

我们都有光明的未来。