Atcoder/Codeforces 做题记录 [2020.9~2020.11]

sanaka87 · 2020-11-10 15:59:40 · 个人记录

CSP 前的做题记录。

重心大概是这样：

先 AGC，再做 ARC，抽时间看 CF 题。

这些基本上是我没做出来的题目，也有一些我自己做出来但是很有记录价值的题目。

"*" 表示自己到现在还没做或者不会。

upd on 10.23：不行啊，总结一直咕咕咕，到时候全忘了...

upd on 11.4：没时间了，所以总结先咕了...

\color{red}\text{AGC}

AGC 041D

~~你退役吧。~~

咕咕咕

AGC 009E

神仙题...这个性质找的我心服口服。

先声明：m 个 1，n 个 0。

想到了枚举 1 的操作贡献...但是推到后面感觉究极复杂...还想到了 k 进制小数，但是有什么用吗？还是不会...

神秘的理解方式：转成 k 叉树！

这样就直观多了！每一次选择 k 个节点连成一个树！答案就是 1 的深度和！

其实这题转成树不是必要的...我们继续往下看：

首先找答案 x 存在的必要条件？

设 x 在 k 进制下是 x_1x_2x_3...。

必要条件 1：\sum x_i\leq m。

这其实是显然的，这个 k 进制都压缩成这样了！！！

但是如果满足了这个条件，如何“解压”？就是把一个 \frac 1{k^y} 变成 k 个 \frac 1{k^{y+1}}？

必要条件 2：\sum x_i\equiv m \pmod {k-1}。

像极了小学奥数，对吧？！！！

这两个必要条件充分吗？还没有考虑 0 ！！！

其实这是一样的，考虑把 0 换成 1 以后，拼成的就是 1-k。所以：

设 1-x 在 k 进制下是 y_1y_2y_3...。

必要条件 3：\sum y_i\leq n。
必要条件 4：\sum y_i\equiv n \pmod {k-1}。

其实 2,4 是等价的。这样充分了吗？充分了。总结一下：

$$\sum x_i\leq m,\sum y_i\leq n,\sum x_i\equiv m \pmod {k-1}$$

三者成立。

找到了条件，接下来就可以枚举 k 进制小数 dp 了！！！但是还有 1-x 怎么办？

这里还是很妙，把 1-x 的条件转化成 x 的条件！

根据进位，假设 x,1-x 是 l 位小数，那么有加起来是 k-1,k-1,k-1,...,k-1,k 的形式，所以：

\sum x_i \ +\sum y_i=l(k-1)+1

这样条件就转化成功了！

接下来就是一个简单的 dp + 前缀和优化。注意不能有后缀 0，所以要开 2 维！

时间复杂度 O(n^2)。

总结：

这个合并转树的思维确实要有...就是合并转化为建树的思想，在 AGC 022F 里用上了！！！因为合并以后就是一起的了，所以可以用树的节点替代！

接下来是一堆总结的套路：

转成判断，观察合法答案的性质！
观察，找能找出的必要条件，再看看是否充分！
转化限制，方便 dp ！
观察数位和的 trick：k-1,k-1,k-1,...,k-1,k !

AGC 025D

咕咕咕

这题都完全不会，没救了，连第一步都没想到 /px

upd：这是套路了，详见 CF 1270E。

总结：

AGC 006E

咕咕咕

这个构造实属强大，提前剧透就真的没意思了...

排除一堆无解以后变成了；

AGC 002E

咕咕咕

神仙博弈模型转化，这种题实在是不可多得。

AGC 018C

刚开始想了不到 5 分钟突然想到了模拟费用流，感觉太难写了就看题解，没想到真有人写...orz Soulist.

但是这个贪心做法真的很经典很妙啊！

使用套路，先强制所有人选金牌，然后考虑选择一些改成银牌和铜牌。

如果只有银牌，按差值调整一下即可。

如果有 2 种呢？考虑继续使用调整法！假设 x 选择银牌，y 选铜牌比 x 选择银牌，y 选铜牌更优，那么 b_x+c_y>b_y+c_x。按照这个排序调整后，发现选择变成了前面选一些银牌，后面选一些铜牌，不能相交。还有个数限制，那么枚举分割点，使用堆贪心即可。

时间复杂度 O(n\log n)。

总结：

把多种物品消去一种是一个好方法！

枚举分割点+堆的贪心套路不能忘啊！

调整法不要推错！调整法解决贪心是一个基本套路！调整以后是一些特殊情况了，解决它就完事了。

AGC 018F

什么神仙题啊，根本不会。

看起来毫无思路，但是我们可以从局部入手，先考虑一棵树怎么做。

注意到正负一的奇偶性相同，我们考虑 dp 出节点的奇偶性（如果两棵树一个点奇偶性不同就直接退出）。

然后怎么构造一棵树呢？我们可以缩小限制狭义构造，下面的构造说明每一个点权值只可能取到 -1,0,1。

如果当前节点是偶数直接选 0，否则可以发现一个性质：子树奇数个数为奇数。所以子树一定可以两两配对，配对后一个 +1 一个 -1 即可。这样根节点就可以做到绝对值为 1 了。这个配对就是一个很简单的类树形 dp。

接下来 2 棵树怎么做？这就很麻烦？神仙操作来了：把两棵树两两配对的关系拿过来建图，得到的一定是二分图！为什么？

证明：一个点显然在一个树里只会连一条边，所以得到的图每个点的度数为 2。如果出现了奇环：对于一个点两条边一定是来自不同的树，对这个边按照树染色，如果是奇环一个点就在一棵树连了两条边，这样就矛盾了。

所以直接二分图染色，黑就是 1 白就是 -1，直接输出即可。

总结：

还是广义转狭义，增加特殊性质，然后转变成了匹配问题...

多个匹配限制，建图！观察得到是二分图！

用栈来维护匹配！

无解条件有时候很有用...

要多多观察，善于挖掘性质！

AGC 026E

这都不会，滚粗了。分割子问题的水平太垃圾了。

显然要对 s 的第一个字母进行分类讨论：

如果第一个字母是 a：

那么显然如果选了这个字母，不妨设后面是 aaaa...ba，那么后面的这些 a 都应该不选。

这样就是关于后面 x 对的一个子问题了。

如果第一个字母是 b：

那么假如选择了这个 b，不妨设后面是 bbb...ba，那么这些 b 都应该选。但是这样就不是一个子问题了，如何分割？

注意到这样选出来后字符串大概变成了：bbbb...a??a??a??b?a??a。

可以证明，在这个选择 ? 的过程中最后会“闭合”，形成一个连续的 ab 串。而且这个串有一个性质：

都是 ba，没有 ab。

为什么？根据题意可以反证出来。假设有 ab，那么一定已经闭合了。

因此这又是一个子问题，可以 dp，时间复杂度 O(n^2)。

总结：

感觉字典序的贪心还是太菜了...

手玩，贪心，然后看看能不能分割子问题你！

善于观察子问题，设计 dp！

AGC 018D

咕咕咕

看了那篇关于匹配的文章就知道这题怎么想到了，不得不说这题 nb。

AGC 040C

咕咕咕

为什么正常做不了...指数做法都不知道对不对，震惊了。

AGC 011C

居然想了不到 5 分钟切掉了，尽管全世界都会 /px

手完这个走路过程，发现环很有意思，又发现奇环就全可以达到，偶环不行。

所以瞎分类一下就可以了。

总结：

提示自己：

这种手玩要看出什么黑白染色的东西！要注意奇偶讨论！！！

手玩！手玩！手玩！干瞪眼看不出来的！

AGC 011D

咕咕咕

想了 20 多分钟感觉很复杂，瞄了一眼题解发现好像很多人都会，然后继续想...接下来就想出来了...

AGC 011E

咕咕咕

神题...感觉自己根本不会。

AGC 006C

这题好妙啊，听说是套路？

显然有一个很简单的期望 dp ，设 f_i 表示 i 位置的期望，然后就有方程 f_i=f_{i+1}+f_{i-1}-f_i。

接下来怎么优化？矩阵...？

神奇操作来了，差分，发现 f 数组的差分数组在一次操作下就相当于交换了相邻两个数...直接对于置换快速幂即可。

时间复杂度 O(n\log k)。注意置换只满足结合律，不满足交换律，写的时候很容易错！最好重载一下...

总结：

序列操作，差分一下也许会有好玩的事情发生...这题也太不明显了。

置换的乘法！群论好好学一下！

AGC 013D

想了 30 分钟还在题解“折线”的提示下才切掉（虽然不说我也能想到，只不过可能会慢一点），我菜 /kk

这是一道去重的计数好题。

首先这个限制就相当于确定了前缀和 -1,1 的上下界。所以可以枚举上下界直接做，可惜这样就重复了，因为我们要的只是颜色序列。

如果我们枚举下边界，强制碰到下边界，好像就可以做了，可惜的是我们还需要记录上边界的历史最大值，时间复杂度 O(n^3)。~~我搞出来了亿个 O(n^3)...~~

注意到一个很好的条件：极差最大就是 n。那么可以想到如果出发点不固定，批处理转移呢？这样就会算冲重了，但至少复杂度降下来了，考虑怎么去重：

接下来有两种去重方式：

枚举极差长度，对于每一种除以 \text{len}，这样复杂度又暴毙了。
枚举边界，只计算碰到上边界的。发现这样恰好满了。

所以初始值对于每一个起点都设为 1，然后转移即可。

ps：我一开始搞麻烦了，记了上下边界...注意 01 10 也要判断边界的。

总结：

批处理 dp，放一起转移的 trick 不能忘记啊！

如何去重？这几种各有长处，但本质是枚举关键的特殊信息！这种枚举边界的思想很妙！

一条路想不出来，换一条路啊...尤其是这种枚举方式多样的 dp 题...

对了，关于前缀和，极差这些字眼要想到路径，这样那个去重方式就很直观了。

~~最近怎么自己想出来以后又感觉很妙啊，是不是已经凭借灵感做题了？~~

AGC 012C

真就只会二进制拆分...正解和我的出发点完全不同...感到恐惧。

那个 naive 的二进制拆分就不说了，级别是 \log_2^2 n 的。

注意二进制题可以套路倍增，考虑怎么构造才能做到 \times 2 和 +1。

接下来就很妙了，如果考虑**增量**构造，就是在原先的基础上做，第一个 $\text{aa}$ 就是 $1$ ，$\times 2 $直接 $\text{abab}$ ，也就是在两段之间插入新数即可。如果增量构造就相当于序列被分成了两段排列 $P,Q$，这样就可以做到 $\times 2 $ 了。因此可以做到长度 $2\log_2 n$，本质不同的数 $\log_2 n$。 ------------ 总结：二进制有关考虑**倍增**构造！如果一个操作不好实现，考虑特殊的形式能不能实现，再利用归纳看看初始的是否满足这个性质，**增量**构造。这样归纳就出来了。 ## AGC 012E NOI 前想了 20 分钟没想出来，现在打开题解我就发现自己当时降智了... 首先这个每次 /2 让我们想到了只会跳 $\log V$ 次，发现就是有 $\log V$ 层线段，问能不能第一层固定一个，剩下来每层各选一个，能不能全覆盖。然后我就不会了，怎么做怎么炸。然而这离正解其实还差了一扇门... 按照层顺序根本不能做，如果能按端点顺序选择线段就好了，那么怎么办？跳出题意的限制，转化思维，我们可以把问题改成直接在 $\log V$ 层里面选择啊！这样就不需要按照层顺序了...吗？考虑状压，设 $R_i$ 表示选择层的状态是 $i$，覆盖的最远右端点，$L_i$ 同理，是左端点。这样就可以按端点顺序了。最后怎么统计一个点的答案？直接枚举第一层会出事情...复杂度会变成 $O(nV)$？这里又有一个神奇的观察：第一层线段如果 $>\log_2 V$，就无解。正确性是显然的，因为第一层最大。所以暴力做就可以了，时间复杂度 $O(n\log V)$。 ------------ 总结：思维还是不够开阔啊...如果能及时跳出题意的限制，想到怎么样好做就可以了... 思维要开阔！敢想敢转化题意！挖掘题目的限制！ **一些关于无解的必要条件也是很有用的！也许可以成为优化复杂度的利器！**（后面 AGC 005E 就出现了...） ## AGC 001F 看到了完全不一样的题解，我惊了，~~感谢 yhx 救我一命！×5~~ 首先这个太抽象了，转化为逆排列，问题变成每次可以把相邻的两个差值 $\geq K$ 的数交换。（我连第一步都没想到？？？）可以发现，接下来就和 AGC 010E 几乎一致了。~~（其实是之前我是在看 yhx 博客的时候发现的）~~ 如果两个数之差小于 $K$ 那么永远无法换位，直接连一条边即可。怎么使拓扑序逆排列字典序最小？这就是经典的 HNOI 菜肴制作，使得反拓扑序字典序最大即可。最后是优化连边，直接**贪心**连最右边满足条件的即可，这个直接线段树维护出来，最后用堆跑拓扑排序，时间复杂度 $O(n\log n )$。 ------------ 总结：排列限制错综复杂，如果同时对应了下标和权值，不妨考虑逆排列？相邻交换，限制连边！贪心优化建图！不一定要无脑数据结构，可以找性质贪心。看 yhx 题解学到了一个字典拓扑原理： > 对于任意一张 DAG 和其拓扑序 $p$，则 $p$ 是字典序最大的，当且仅当 $p^{-1}$ 是字典序最大的。 > 对于任意一张 DAG 和其拓扑序 $p$，则 $p$ 是字典序最小的，当且仅当 $\text{rev}(p^{-1})$ 是字典序最大的。 > 对于任意一张 DAG 和其拓扑序 $p$，则 $\text{rev}(p)$ 是字典序最大的，当且仅当 $p^{-1}$ 是字典序最小的。 > 对于任意一张 DAG 和其拓扑序 $p$，则 $\text{rev}(p)$ 是字典序最小的，当且仅当 $\text{rev}(p^{-1})$ 是字典序最小的。证明待补。咕咕咕 ## AGC 016E 一直在最小生成树的路上越走越偏，感觉极其复杂，一开题解感觉标算的做法好厉害，再看到小粉兔的做法我就感觉自己是个 sb... 首先肯定是考虑一只鸡会不会死，然后我这都不会...我想了一通奇怪的东西，比如相邻的什么最小...然后走远了。我们想知道一个鸡能不能活，从图论的角度入手，就是一堆限制问能不能满足。接下来处理限制有两条路： #### 小粉兔做法：我的 2-SAT 没学到家啊 /px ，这都没想到... 活和不活是 2 元选择，考虑 2-SAT。先**按照时间拆点**，拆成 $n+m$ 个二元组表示这个时刻第 $i$ 只鸡有没有选择活下来。接下来找性质呗：对于当前的边 $(x,y)$： - 如果 $y$ 之前选择死掉，那么 $y$ 现在必死。 - 如果 $y$ 之前选择死掉，那么 $x$ 现在必死。 - 如果 $y$ 现在选择活下来，那么 $y$ 之前一定活下来。 - 如果 $y$ 现在选择活下来，那么 $x$ 之前一定活下来。 - 如果 $y$ 现在选择活下来，那么 $x$ 现在必死。这是关于 $y$ 的，$x$ 就不赘述了。接下来得到了一张缩点后的 DAG，点对满足条件就成了 DAG 上的可达性问题，使用 bitset 可以做到 $O(\frac{ (n+m)n}{\omega})$。 #### 题解做法：很妙啊，虽然复杂度不如上面的优秀。考虑 dp 处理限制，设 $f_{i,j}$ 表示：如果 $i$ 最后活下来，$j$ 有没有被杀掉拿去替死。如果转移呢？首先明确一个事实：留着一只鸡以后杀是为了在我们需要保留的鸡 $i$ 要被杀的时候拿去替死。发现性质：对于一条边 $(x,y)$ ，假设 $x$ 以后要拿来替死，那么 $y$ 一定要死。这个"**以后**"提示我们要**时光倒流**。倒着加入每一条边，考虑这样的转移： - 如果 $f_{i,x}$ 和 $f_{i,y}$ 都要替死，那么这条边会打破所有的策略，$i$ 一定会被删掉。 - 如果 $f_{i,x}$ 和 $f_{i,y}$ 有一个替死，那么另一个也要替死。因为那只鸡要保留为了以后拿着替死。 - 如果 $f_{i,x}$ 和 $f_{i,y}$ 都不用替死，那么无所谓。这样就满足了这个性质，而且仔细观察这是唯一的性质。得到了数组以后，如果 $i,j$ 都可以活着，它们一定能同时活着吗？显然不是，如果两个鸡替死集合有交就不行，所以判一下两个 $f$ 集合有没有交即可。为什么是对的？我的证明（口胡）：显然这个替死形成了一棵树的结构，如果有交集一定是一条链，两棵树出现分歧的地方就不能同时满足。可以用 bitset 做到 $O(nm+\frac{n^2}{\omega})$。 ------------ 总结：不要吊死在一棵树上...换思路... 限制选择可以建图，用 2-SAT 考虑是活是死！2-SAT 是处理二元选择的利器！限制可以暴力动态规划！观察性质，再满足这个性质！这个性质是替死限制树，那么就 dp 出这个即可... ## AGC 016F 一直在想状压 SG 函数，然后自闭了。这题好妙啊。首先，两个石子好像是互不影响的，这提示我们算出 SG 函数相同的方案。接下来怎么做呢？这个导出子图 dp 肯定要状压，但是怎么 dp 呢？如何更新？然后我就不会了。老样子，考虑**如何割子问题**。抓特殊的部分看看？如果我们知道了必败点，那么这个图是怎样的？ - 所有必胜点都一定要连向至少一个必败点。 - 所有必败点之间不互相连边。这两个限制。如果把这个一些必败点去掉呢？神奇的事情出现了：SG 函数为 $1$ 的变成了必败点！这是什么，分割子问题出现了！做完了？是的，做完了，每一次分割的时候满足 $1,2$ 在一起，就可以 dp 了。具体转移就不说了，时间复杂度 $O(3^nm)$。 ------------ 总结： - 通法：分割子问题，分割子问题！如何分割？抓特殊！抓已知！这题的已知是必败态！ - SG 函数 dp：SG 函数本身就是一个分层图的形式，对分层图的 **“层”** 进行分割！这种思想一定要有！博弈论 SG 函数可以通过扒必败态来分割子问题！ ## AGC 005E 这都不会，可能要退役了。深入思考不够啊...怎么就直接打开题解了？~~sb HorizonWind。~~ 先考虑无解，发现就是如果 A 树有边，在 B 树上距离大于等于 3，先手就可以到这条边去溜后手达到 $\infty$，前提是能到达。然后我就不会了。不妨设无解的点为关键点，假如先手到达不了关键点，怎么算最大距离呢？ #### 一个非常重要的事情：无解已经不可能了，因此先手不可能一次在 B 树走大于 2 步！假设后手在 Y，先手在 X，那么先手不可能跑到 Y 的后方！（就是子树外）！不然先手随便搞搞就被抓住了（最多走 2 步）。那么后手层层逼近下来，先手可以走到以 Y 为根最深的且先手能比后手先到的点，然后乖乖等死即可，这样就最大了。 ------------ 总结：要善于简化问题：在排除无解的过程中，注意性质！这个不能一次走 2 步的性质至关重要！好多题都是这样，通过一步一步的转化与排除，可以得到很多新的有妙用的性质！ ## AGC 006F 画了一个直线 $y=x$ 然后自闭了，事实上我第一步都没想到 /px，甚至第二步也及其神仙 ~~（但我之前不是秒过一道二分图的题吗，这次三分图怎么这么难？）~~。首先这条件太阴间了，**考虑建行列图**！！！这也太妙了，每个点当成一条边，这就变成了一个图论题啊！如果 $x\rightarrow y,y\rightarrow z$，那么 $z\rightarrow x$，求最后有多少条边？太妙了，真的太妙了。接下来是一个可以手玩出的结论：$3$ 染色，考虑每一个弱连通分量：如果 $3$ 染色失败，那么贡献是连通分量大小的平方。如果成功，而且用了 $3$ 种颜色，那么贡献是 $rb+bg+gr$。如果成功但是没有用满 $3$ 种颜色，那么贡献是边数。和 AGC 011C 的结论蛮像的，就是出现一个非 $3$ 倍数环，就可以利用这个东西无限扩张。 ------------ 总结：这种转行列图的转化一定要看出来啊... 充分手玩，玩出 $3$ 分图的那个性质！ ## AGC 017C 咕咕咕居然是 BJOI 删数的弱化版... ？？？这个转化我这辈子想得出来？？？ ## AGC 020F 咕咕咕神奇的实数离散化...被难度值劝退了，全场无人 AC... 写这个题的时候头昏眼花浑身难受，可能已经撑不下去了？ ## AGC 022F 咕咕咕网上的做法好像是奇怪的方法？这个 F 题难度值看着太吓唬人了，瞎 jb 想了一下感觉是一个虚实链剖分就看题解了，打开以后发现网上的做法很奇怪？又看了一眼 LH 的题解发现自己的第一步和他一样...仔细想了快 1 个小时就想出来了，后悔...早知道就不看了，太不够自信，这种题我应该是能想出来的啊... ~~网上的做法待补。~~ 首先按照 AGC 009E 的套路，把合并关系看成一棵树。 ## AGC 015E 搞了 1 个半小时假做法，自闭了。我的想法：考虑分割子问题，每次看速度最慢的，如果不染色说明速度比他快的且在他前面的染了色，如果染色速度比他慢的全部可以变成黑色，发现这样 dp 状态数爆炸，因为还有欠下黑色的操作...我自闭了。 ~~其实我都已经想到对速度排序了，可惜方向偏了，血亏。~~ 正解居然是直接下手。考虑一个点被染色以后的影响： - 在他前面比它快的：可以超过他然后获得黑色影响后面的。 - 在他后面比它慢的：会被他超过然后获得黑色影响前面的。但是还有一些点获得黑色以后可以影响其他点！比如速度快的超越前面的所有点...怎么处理？我们考虑搞出“**最强点**”，意思就是左边速度最大的，右边速度最小的，然后观察这些最强点可以得到一个结论：右边速度比左最强点小的都会被染色，左边速度比右最强点大的都会被染色。 #### 重要性质：速度在左右最强点之间的都会被染色！接下来自然地就会想到一个转化：按照速度从小到大排序，那么染色的是一个区间。 - 左边是速度最小的在它右边的点。 - 右边是速度最大的在它左边的点。所以问题就变成线段覆盖了，直接线段树优化 dp 即可，时间复杂度 $O(n\log n)$。但是这题线段满足亮亮不相交，直接前缀和也行。 ------------ 总结： #### 想清楚再写... 一条思路死了换一条啊啊啊啊要善于观察发现美妙的性质。可以多多转化，比如 yhx 就是画了一个坐标图...如果转化到了最后一步（区间覆盖）就要灵敏地想到 dp 啊！思路是多元化的，可以直接做也可以巧妙转化...这题直接看最小值（整体地）反而还出问题了，还不如直观感受一个点被染色后的影响（局部地）。~~所以还是要靠灵感啊...~~ 还有一个错误的思路可能会对正解有一定的启示... ## AGC 024E 想了 40 分钟还不会，我好菜。我是从小到大做的，搞了一堆奇怪的 dp 发现不行...去重我会但是不会找共性...想了各种方向又感觉不太可能... 这道神题充分说明了如果找不到共性怎么做？接下来我要扯一大堆了... ~~网上一堆傻逼题解去死吧，妈的智障。~~ #### 直接做会有什么问题？插入一个段需要满足这一段 $>$ 下一段，这个不好处理。还要记录一个点可以扩大多少，这没法做。 #### 简化问题先考虑去重，每一次我们可以考虑插入一个数到一个连续段的末尾，简化后的问题是： > 每一次可以插入一个数到末尾或者小于它的数后面。 ~~没有确定这一步就自闭了，这样转化就清晰多了。~~ 接下来怎么做？ #### 做法 $1$： ~~结合各家之长自己摸出来的做法~~ 思想：枚举特殊的分割子问题（可惜这真的不好看出）枚举插入末尾的有多少个，然后枚举划分，分割子问题，每一段又分别是子问题...然后不能小，所以设 $f_{i,j}$ 表示长度为 $i$，最大值为 $j$ 的方案数。但是插入顺序在不同子问题里可以不同，所以需要组合数转移（$\text{EGF}$）接下来是一个类似于多项式 exp 的过程，可惜这题模数不是质数，所以只能暴力背包了。时间复杂度 $O(n^2k)$。 #### 做法 $1$ 的另一个切入口来自官方题解。思想：转化成具象的树，打破位置连续的 dp 限制。插入变成连边，然后变成了树计数，枚举根节点分割子问题即可。时间复杂度也是一样的。 #### 做法 $2$： ~~其实我都想到了这个方向但是感觉不可能，这次是深度不够...~~ 来自毕克。咕咕咕 ------------ 总结：居然暴露出了这么多问题，看来我的水平真的还不够啊... - 简化问题：在思考和排除的过程中，多多注意挖掘出清晰明了的具体的模型和性质！ - 分割子问题：从末状态，初始状态下手分割，注重初始确定的部分（如这次末尾的 0）。（AGC 035D 也是一个分割子问题的好题） - 转图：将插入的大小偏序关系拉出来连边！这次是通过观察得出“堆”，接下来就便于分割子问题。 - 从小到大放：跳出题意的约束，从小到大，发现特殊性质（都能插入），再找出反悔的方式（一层一层做！）。 ## AGC 038F 咕咕咕毫无思路，一看题解最小割...发现自己最小割模型网课看过现在又忘了...复习一下。 [最小割总结来了!](https://www.luogu.com.cn/blog/Noziro/zui-xiao-ge-mu-xing-zong-jie) 神仙题...第一步都没想到 ~~（其实是没仔细想？）~~ 的我宛如智障... ## AGC 027F 神仙题，但我又 tm 第一步没想到，我最近怎么了... 无根树关系错综复杂，我直接弃疗了。题解很神仙：无根树做不了怎么办？转有根树啊！假设 $x$ 不操作，我们就可以以 $x$ 为根。接下来 $x$ 显然不会动，那么成功搞出了问题的落脚点！有点不动就可以快乐切入问题了。接下来就可以套路地观察限制了：注意到：只要 $x$ 到了 $y$，那么 $x,y$ 都不能动了，因为一个不是叶子，一个已经被操作过。又注意到：因为根已经固定，所以两棵树同构当且仅当 A 树上每个点的父亲与 B 树的相同。那么假设 $x$ 在 A 上的父亲是 $y$，在 B 上的是 $z$（根都固定了），我们需要把 $x$ 从 $y$ 搞到 $z$。限制是什么？ - $z$ 要先操作到正确位置。 - $y$ 要等 $x$ 操作完才能动。 - $x$ 不操作，$y$ 也不能操作。限制错综复杂，怎么办？连边！先把第三种情况的无解判掉，然后连边 $z\rightarrow x\rightarrow y$，拓扑排序判环即可。和树上的数好像啊... 最后一个问题：如果所有的数都动怎么办？怎么搞出有根树？暴力枚举第一次操作即可。时间复杂度 $O(Tn^3)$。为什么我总感觉可以优化啊...但我不会。 ------------ 总结： $n$ 很小是突破口！无根树不好做转有根树！不好做就转化！想方设法也要转化！转化后仔细观察性质，发现限制，然后限制错综复杂就连边！这种先后选择限制一定要注意拓扑排序啊！限制能多数学化就多数学化！ ## AGC 012F 神仙题？想了 10min 就弃了...说真的我好菜啊。然后题解啃了很久才啃出一点名堂来...看来又要扯了... 先对 $a$ 从小到大排个序。直接做又出事了，考虑如何计数那个 $b$ 数组。有一个很好的思想就是考虑什么样的 $b$ 数组是合法的。首先从后向前看，第 $b_i$ 数的取值范围是限定的：$[a_i,a_{2n-i}]$，这个还是可以看出来的。然后发现一个不显然的性质：不存在 $i<j$，使得 $b_i$ 介于 $b_j

和 b_{j+1} 之间 (不含端点)。也就是说这个中位数不能跳，要一步一步地走。

证明这是充要的？可以归纳法吧。

接下来问题就变成了求解这样的 b 数组个数。

b_i\in\{a_1,...,a_{2n-1}\}
b_i\in[a_i,a_{2n-i}]
不存在 i<j，使得 b_i\in (b_j,b_{j+1})。

还是很神仙...

观察这个限制 3 如何具象地表示：也就是说原先的 b_i 形成了一堆点，每次只能走到相邻的一段点之间或者走到相邻的 b_i上。问有多少种走法。

正着做搞了半天又假了，因为限制越来越多，无法快速用 dp 记录状态找共性。那怎么办？考虑倒着做。正好限制 2 也是倒着的。

倒着做再转化一下限制 3：如果一次从 i 跳到了 j，那么接下来区间 (i,j) 就不能再走了！

看起来限制更阴间了，事实上，如果当前 i 跳向了左边，那么左边这一段全部不能再走，右边还可以！如果当前 i 跳向了右边，那么右边这一段全部不能再走，左边还可以！那么如果向左可以走到 x 个点，我们可以维护处向左走到哪里，然后中间的全删掉...

每一轮如果数不一样还可能会加入一些新的左右可走的点...但是我们还需要知道多少个可以向左向右多少啊！

不知道就设啊！

分析到这一步，这道题其实已经做完了。转化后的限制变得清晰明了好维护了很多。设 f_{i,l,r} 表示后 i 个，当前可以向左走多少，向右走多少每次枚举向左还是向右，走多少还是不走。如果两边数变了还要更新 l,r。

f[n][0][0]=1;
for (int i=n-1;i;i--){
    int xl=(a[i]!=a[i+1]),xr=(a[N-i]!=a[N-i+1]);
    for (int l=0;l<=N;l++){
        for (int r=0;r<=N;r++){
            f[i][l+xl][r+xr]=(f[i][l+xl][r+xr]+f[i+1][l][r])%ljc; 
            for (int k=0;k<l+xl;k++) f[i][k][r+1+xr]=(f[i][k][r+1+xr]+f[i+1][l][r])%ljc; 
            for (int k=0;k<r+xr;k++) f[i][l+1+xl][k]=(f[i][l+1+xl][k]+f[i+1][l][r])%ljc; 
        }
    }
}

时间复杂度 O(n^4)。

总结：

仔细思考，不要想错！可以手玩样例！

本质不同方案计数，可以 4 种突破口，已经总结过了，这题就是要考虑好方案的性质是什么，什么样的方案是合法的，能不能搞出充要条件对它计数。

充分手玩，考虑清楚，实在不行也可以打表啊...

普通 dp 很难处理甚至处理不了限制越来越大的情况，遇到这种情况可以考虑换思路或者换角度！这次又是倒着考虑，从已知的 n 放大到初始局面！转化限制，抓住关键信息！

不知道什么可以设出来！不会求就设啊！缺什么也设啊！

~~说了这么多，下次遇到这题还是一样不会吧...~~

AGC 039C

为什么我连 C 都不会了...

搞不懂啊，为什么大家都会啊？这个循环节计数不是很难吗...

手玩一下发现是把最低位反转后扔到后面，问题等价于这样操作的最少次数和，然后我就不会了...

如果没有翻转操作，这样扔数的过程你想到了什么？次数如何快速求？循环节！操作次数就是循环节...那么有翻转，我们就可以把串倍长，再把后面的翻转，然后求它的循环节！

现在问题变成了对每一个循环节进行计数。直接计数不好做，考虑容斥，设 f_i 表示循环节为最小循环节为 i 的约数的方案数，最后莫比乌斯反演一下就好了。

接下来怎么求呢？因为这是翻转串，我们考虑如何计数：

不妨设循环节为 i，进行分类讨论：

如果 i|n，也就是循环节没有跨过中间，那么发现无解。

然后就变成了跨过中间的情况，考虑这个循环节被中间分成了两段：p 和 q，那么通过归纳可以得到这个串就是 pqpq...pqp 的形式，而且 q=\text{rev}(q) ！

所以我们枚举最高位就好了？但是还有位的限制...解决方案是拿最高的 \frac i2 位看是否符合条件，如果不符合减 1，根据数位的性质可以证明正确性。

最后反演一下即可，时间复杂度 O(n\log n)。

总结：

循环节没看出来，这真的要好好反思了...

头插入到末尾要看出最小操作次数是循环节！这种恢复的操作次数也许和循环节相关！

循环节计数和莫比乌斯反演经常联系起来！

枚举循环节，通过构造发现循环节的关键性质！

从最高位开始会方便很多！

AGC 034C

我 tm 又 A 不了 C，我是不是可以去死了？

想了不到 25 分钟会了一个做法，大概是这样的：

二分，然后考虑钦定一些科目超过对手，然后把 R 开满，剩下的没超过的把 L 拉到底。问题变成了如何选择 R？发现一个选择 X 一定比多个选择总和为 X 更优，证明可以用反证法。因此就会有 \lfloor\frac {\text{mid}}X\rfloor 个选满，剩下的一个选 1 个不满的即可。先全部强制减去对手的分数就可以避免很多讨论。

~~（哇，居然想出来了题解的大部分内容呢，太强了！）~~

然后我按照 L\times b+R\times(X-b) 排序，就是优先选择大的，最后选一个小的，小的再排序选择贡献最大的。结果交上去 tm WA 了...搞了半天还是 WA？对拍了一下还是搞不懂，改了排序方法还 tm WA...耻辱，这么多人 AC 的题，我却只能向题解屈服。

hack 数据：

事实上前面我的分析都 tm 是对的，问题是可能出现一种情况：

大的科目不选，留着替补，然后把大的让给别的科目？？？！！！因为可能大的 R 比较小，给后面的自己损失少而且可以赚到更多分...我为什么写前没有意识到这一点啊...

解决方法：你就暴力一点，直接枚举哪个做小的，剩下的直接选最大的不就行了...？时间复杂度 O(n\log n)。

总结：

感觉自己贪心确实不太好啊...

找关键性质！这题的性质就是选满的就一个...调整法，反证法，这些都很重要。

想清楚有没有可能出现错误情况再写，不要想当然！现场如果是猜结论，怀疑可能有错误情况，就可以写暴力对拍一下！

能枚举就枚举，不要投机取巧什么的...这题只有一个，直接枚举就好了，思维要跳跃！

~~来自错误的做法的总结：~~ AGC 018C 的“枚举分割+堆”的贪心不要忘记！这个非常有用！

~~感觉今天的灵感不太行啊...~~

AGC 037B

咕咕咕

差点身败名裂...感觉我思维不太活跃了啊...

2 周前看过不会，现在题目看成 \max 白花了 1h30min 后想了 20 分钟终于想出来了...然后我的代码还吊锤别人...思路还清晰一点（看来我不菜？）

~~居然想到了，灵感还不错！~~

~~而且我可以出一道 max 的题目了？爽！~~

AGC 020E

神题...

没有子集这玩意就是一个裸的区间 dp...有限制呢？

我们考虑暴力，把状态设为 01 串。转移要考虑 s 的一堆 \text{and}。

这就是正解，复杂度是对的。是 O(n^4+2^{\frac n8})。

主要原因在于那个 \text{and} 上，具体证明其实我也不大会...

证明

总结：

有时候看似指数的 dp 可能状态很小！比如 dp 套 dp 哪些...

如果实在想不出优化了，可以考虑信仰打表！！！

AGC 039E

NOI 前咕到现在的一个题目。

和 AGC 028D 很像的一道题，但是感觉这题难一点...？

疯狂疯狂分割子问题哦...

无从下手，先考虑树是什么样子的。

一定是：

这样是不合法的：

也就是对于一条黑色的边，它把圆分成了 2 块。两块之间的连边一定是不相交的。可以知道这是充要条件。

当然这是要连通的，所以两块之间至少要有一条边。

不妨枚举 1 和 i 相连，接下来就是一个子问题：

两块分别是 [2,i),(i,n-1]，分割点为 i，两块之间至少有一条边的方案数。

不妨设 f_{i,j,k} 表示上面这个东西：两块分别是 [i,k),( k,j]，分割点为 k 的方案数，接下来 dp 这个东西就好了。怎么做？

分割子问题。显然两块至少一条连边，不妨设这个是 a,b，然后因为这是一棵树，套路地（AGC 028D），我们枚举 a,b 的分界点 c,d （具体意义就是分成的这两块的端点）。接下来就变成了 3 个子问题了。

时间复杂度 O(n^7)。常数极小。

优化到 O(n^5)：咕咕咕

总结：

抓住性质，找到条件，使用枚举，善于观察和分割出子问题！

不要被数据范围吓到了，不一定是状压！！！

套路不能忘啊！

AGC 023D

咕咕咕

神仙思维题，感觉自己没想出来还没搞清楚，实在是辣鸡。

AGC 035E

咕咕咕

又是一道 NOI 咕到现在的神题...

AGC 031D

咕咕咕

完全不会群论.jpg，来个学习记录？

下面把置换讲成排列？

定义排列的乘法 (p\cdot q)_i=p_{q_i}

定义排列的逆 p^{-1}_{p_i}=i

有一个关键性质： (p\cdot q)^{-1}=q^{-1}\cdot p^{-1}，证明再见。

置换乘法满足结合律不满足交换律，就讲这么多吧。

回归本题：f(p,q)=q\cdot p^{-1}，找规律开始！

a_1=p,a_2=q

a_3=q\cdot p^{-1}

a_4=q\cdot p^{-1}q^{-1}

a_5=q\cdot p^{-1}q^{-1}(q\cdot p^{-1})^{-1}=q\cdot p^{-1}q^{-1}p\cdot q^{-1}

a_7=q\cdot p^{-1}q^{-1}p\cdot q\cdot p\cdot q^{-1}

找不到规律...但是把 a_7 改一下？

a_7=\color{red}{q\cdot p^{-1}q^{-1}p}\color{black}{\cdot p}\color{blue}{\cdot p^{-1}\cdot q\cdot p\cdot q^{-1}}

看出规律了吗？

a_m=\color{red}{q\cdot p^{-1}q^{-1}p}\color{black}{\cdot a_{m-6}}\color{blue}{\cdot p^{-1}\cdot q\cdot p\cdot q^{-1}}

我也不知道怎么看出来的...表示震惊。接下来快速幂即可！

注意置换快速幂的顺序不要写反...

AGC 039D

什么，我的初中数学还给 wjs 了？

算内心不好算，用一个东西转化成垂心，然后垂心用欧拉线，转化成重心。重心就好算了。

总结：

我能总结出什么...我已经不会 MO 了啊...

就是转化吧，计算几何里面重心最好算。

AGC 003E

咕咕咕

神题，完全不会...

感觉自己根本没有完全理解...所以咕咕咕了。

AGC 019E

现在什么都不会...我觉得我菜死了。

不妨设 a_i=0,b_i=0 为 00 类点， a_i=1,b_i=0 为 10 点，其他同理。

经过思考与多方向的切入 ~~（看题解）~~ ，我们先考虑这样一个问题：

假设我们已经确定了 a_i 和 b_i 发生了一次交换，如何求概率呢？

干瞪眼不行，这是限制，连边！！！！！！

我们得到了一个图，考虑每一个连通块，观察性质：

一个点度数最多为 2 ！！！所以每一个块要么是一条链，要么是一个环！！！

链要求 10\rightarrow 11\rightarrow 11\rightarrow ...\rightarrow 11\rightarrow 01。

环要求 11\rightarrow 11\rightarrow ...\rightarrow 11。

发现这个模型转化越想越对，越想越妙啊！！！！！！~~但是怎么想出来呢...~~

算概率：

一个环想怎么操作就怎么操作，概率为 1。
一条链只有一种合法方案，概率为 \frac 1{n!}。

因为操作顺序在连通块之间是随意的，那么套个 EGF，接下来想怎么做就怎么做了，用多项式快速幂可以做到 O(k\log k)。

总结：

连边妙啊！！！题意复杂还是限制复杂还是转化复杂，连边！连边！连边！！！这题是传递关系连边！

连边后，这题就简单了，所以脑洞要大！！！

AGC 044D

咕咕咕

自闭，以为自己会 O(L\log L)，然后发现编辑距离...有坑，然后假了，发现自己甚至不会 O(1) 判断一个前缀有多少个 a /cy

题解有神仙的二分...看不懂，爬。

其实我想到了相对位置，想到了可以通过判断子序列合并，结果只会 O(L^2)，忘记了启发式合并？？？我？？？

感觉启发式合并好 nb 啊，以前浙大集训遇到过这样的交互，现在又出现了，赶紧要学了。

总结：

咕咕咕

不会做不可怕，以为自己会做才可怕！

AGC 023C

居然切掉了，我也有今天 /cy

一开始觉得是一个 min-max 容斥的 \max 形式，然后只会 O(n^2) dp，状态都是 O(n^2) 的。然而事实上这题不是期望...所以 min-max 容斥还不能做...

本来想直接看题解，然后坚持了一下，逼着自己继续想，换了一个思路，切掉了/cy。果然人就是要逼自己打破思维定式一下...

考虑直接下手，求多少个操作序列是 i 次饱和。直接下手不好做感觉非常复杂，怎么办？

脑子里闪过一个词，容斥。我也不知道我是怎么想到的...

考虑求 f_i 表示至多 i 次饱和的方案数，注意这里就是至多，不是枚举方案数。答案就是：

\sum_{i=1}i(f_i-f_{i-1})

$$f_i=\binom{i-1}{n-i-1}\cdot i!\cdot(n-1-i)!$$ 时间复杂度 $O(n)$。 ------------ 总结：正难则反的容斥啊！！！恰好不会求就求至少或者至多！$=x$ 不好算算 $\leq x$ ！！！基本套路不要忘了！这种“结束”型的计数题可以这么考虑！ ## AGC 013E 我脑残吧...第一反应组合意义，但是感觉直接做更好？然后搞了一个 dp 发现矩阵和 $i$ 有关，就弃疗了，结果忘了一开始想的组合意义？？？多少次这样了？？？ #### 失败的 dp：设 $f_i$ 表示末尾为 $i$，然后转移是 $$f_i=\sum_{j=1}^if_j(i-j)^2$$ 拆掉后维护 $3$ 个值，可惜矩阵与 $i$ 有关。 #### 解法 $1

来自 yhx：

发现问题的关键在于我们不好维护 f_i\cdot i,f_i\cdot i^2？

考虑差分降次：

f_{i+1}-f_i=\sum_{j=1}^if_j(i+1-j)^2-\sum_{j=1}^{i-1}f_j(i-j)^2

=f_i-\sum_{j=1}^{i-1}f_j[(i+1-j)^2-(i-j)^2]

=f_i-\sum_{j=1}^{i-1}f_j[(2i-j+1)]

=2 \sum_{j=0}^{i-1} f_j \cdot \left( i - j \right) + \sum_{j=0}^i f_j

拆成这样有什么好处？注意到我们可以直接利用前缀和递推出 \sum_{j=0}^{i-1} f_j \cdot \left( i - j \right)！！！

接下来就可以直接矩阵乘法了。

解法 2

考虑组合意义，就是在每一个空里面放 2 个颜色不一样的球...直接矩阵乘法就没了。

时间复杂度都是 O(\omega^3\log n)...

总结：

别忘了第一反应（灵感）...不要不会就直接爬，再想一下也不是不行...

组合意义可以很好地降次，减轻 dp 的负担！

dp 利用差分降次！矩阵和 i 有关可以试试差分！

## AGC 033E 咕咕咕 ~~又没看清题目，爽！~~ ~~怎么回事，看对了就会了？感觉和 AGC005E 一样都很棒！~~ ## AGC 032E 咕咕咕调整法神题，这题疯狂调整，属实 nb。~~感谢 yhx 救我一命！× 6~~ ## AGC 030C 咕咕咕这题感觉神到做了和没做一样，还是什么都不会... # $\color{orangered}\text{ARC}

按照题目编号排列。

ARC 073E

~~我好像变强了呢。网课时候不会做，果然做 AGC 会提高智商...呸，提高套路？~~

为什么这么多人过啊，外国人真的贪心魔鬼吧...

首先一个一个袋子选显然死掉了。（为什么我当时没发现？？？）

那么先全体排序，看看怎么选最优？（AGC 028C 的套路）

我的思路：

发现可以贪心，小的能选就选，如果选到了集合不一样的再看大的，能选就选，不行就小的。这样上下界都固定了，应该最小。但我不太会证明？但是还会出现最大最小一个颜色，这个双指针即可。

然后 UB 了一下就过了？

为什么对呢？口胡一下，第一步能让 B_{\min} 尽可能大，第二步能让 A_{\max} 尽可能小。

总结：

套路！转化题意变成哪些合法哪些小！

手玩样例找突破口！

贪心，分类讨论，不要忘记特殊情况！仔细思考！

ARC 076F

神题，广义 Hall 定理属实 nb，本来还以为这个东西没用...

这东西感觉可以模拟匈牙利，但我不会。

我想到了前缀优化建图...但是过不去...因为这样就不是二分图了...

因为这个图很特殊，考虑用 Hall 定理。设人集合为左部点，那么最大匹配个数等于 n-\max(0,|S|-|T|)。

然后这个 |T| 很特殊，是线段交。这就是这题的妙处。

式子化简后是 \max(0,|S|-\min r-\max l-1-m)。先判掉交集为空，这个随便搞，贪心一下发现就直接减。

接下来考虑枚举 r，从大到小枚举，用扫描线维护 l 的答案。贪心一下就是一个区间加+全局最大值，线段树即可。时间复杂度 O(n\log n)。

总结：

Hall 定理可以求最大匹配，前提是图很特殊。

化简式子很重要！

切换枚举方式，转成数据结构题。感觉自己扫描线好像不太行啊...就类似于线段树优化 dp，维护一个区间的答案，然后动态更新...这个 \min,\max 的东西扫描线好像很在行啊...得注意一下了。

ARC 081F

咕咕咕

ARC 083E

去年做的，当时不会，感觉质量很高，拿过来补一下。

这是一道贪心和构造结合的好题！

发现这个权值很有性质，如果当前节点颜色确定了，这个子树的一种颜色就已知了。剩下来的颜色有很多种权值和，记录下来？这样就 O(n^3) 了，无法通过。

发现无解显然是子树权值和太大了，当前染什么颜色都会超出 x_i，反而如果小还可以调整上去，因为没有上界。

正解已经呼之欲出了。我们设 f_i 表示这个点染了一种颜色，其子树内反色的权值和的最小值。

那么发现对于一个点 u 的一个子节点 v，要么选择和 u 一样的颜色，对根贡献为 a_v，对 f_u 的贡献是f_v。否则就是 f_v，对 f_u 的贡献是 a_v。

所以我们发现我们如果设对根的贡献为费用，对答案贡献为价值，那么我们跑一个最小费用，强制选所有物品的背包不就好了吗？这道题做完了。时间复杂度 O(n^2)。

总结：

好好地挖掘性质啊！思维不能僵化...

贪心和构造结合的思想，一定要有啊...贪心，贪心！

这种二元记录反颜色的思想也很不错。

ARC 084D

以前做的有点记不得了，来补一下。

神仙题啊...注意到数位和以及整除搭不上边，考虑切换思路。

整除等价于模 k 余 0。然后考虑从 1 开始构造那个很大的数，怎么构造？

发现接下来可以跑同余最短路！于是就做出来了！！！

时间复杂度 O(k\log k)。

总结：

很多东西搭不上边或者性质很差就不要想！比如异或和数论，还有这个数位以及整除，考试已经被坑过一次了，接下来注意啊！

数位和的构造方式：+1 和 \times 10 ！

有个东西叫做同余最短路！妙啊！

ARC 085E

死磕 dp 然后去世，一看正解“最大权闭合子图”？

注意到性质：

一个点死了，那么他的倍数也死了。
一个点活着，那么他的约数都活着。

对第二条建图跑最大权闭合子图即可。

总结：

网络流忘了好多啊...

dp 不行不要死磕啊...最优化可以贪心可以 dp 也可以网络流啊！

这个性质其实已经观察出来了，如果对最大权闭合子图模型再熟悉一点就好了...

ARC 087E

我是博弈菜鸡 /kk

首先问题等价于求一棵 trie 树上的所有空子树的 SG 函数异或和，问题变成了求一个深度为 dep 的满二叉树的 SG 函数。

然后我就 nt 了，突然就搞错了问题...

列出方程：

\text{SG}(n)=\mathrm{mex}\left\{ 0, \text{SG}(n - 1), \text{SG}(n - 1) \oplus \text{SG}(n - 2), \text{SG}(n - 1) \oplus \text{SG}(n - 2) \oplus \text{SG}(n - 3), \cdots, \text{SG}(n - 1) \oplus \text{SG}(n - 2) \oplus \cdots \oplus \text{SG}(0) \right\}

这就是一层层扒链的过程。不要转化错啊！！！

打表发现就是 \text{lowbit}。证明需要格雷码，咕咕咕。

证明，格雷码。

总结：

都想到最后一步了，你在干什么...不要把模型转化错啊！

把前缀看成 Trie 树！使用 SG 函数分割问题！打表找规律！~~灵感妙啊！~~

ARC 091F

我是博弈菜鸡 /kk

把 SG 函数拿出去打表，发现：

\operatorname{SG}(n) = \begin{cases} 0 & 0 \le n < k \\ \frac{n}{k} & n \bmod k = 0 \\ \displaystyle \operatorname{SG} \!\left(n - \!\left\lfloor \frac{n}{k} \right\rfloor\! - 1 \right) & n \bmod k !\neq 0 \end{cases}

~~这个规律怎么找出来的啊，真的强？~~

如果暴力求，显然 k 大就会 TLE，怎么办？

发现如果一次减去好几次 \lfloor \frac{n}{k} \rfloor 直到 \lfloor \frac{n}{k} \rfloor 发生改变是不是就可以了？这个减多少次显然可以利用整除分块的那套理论算？

那么这样复杂度是多少？因为一次 \lfloor \frac{n}{k} \rfloor 至少减去 1 ，那么...会减去多少次？还是不会算...

有个神秘的东西叫做根号分治 !!!!!!

考虑上面直接暴力做的复杂度，如果 \sqrt n\geq k 那么复杂度是 O(\sqrt n)，否则，\lfloor \frac{n}{k} \rfloor \leq \sqrt n，一次 \lfloor \frac{n}{k} \rfloor 至少减一，复杂度也是 O(\sqrt n)，做完了。

总结：

博弈论 SG 函数能分析就分析，不然，找规律！！！

关于整除的根号性质要有所注意了！其实前面那个暴力部分你就应该要看出来...~~（然而事实上你直接写后面那个东西复杂度就对了，所以可以大胆一点不要证明）~~

ARC 093E

刚睡醒看了 10 分钟直接看题解了...

做题前能不能带个脑子来...这种基础套路题能不能想完所有套路再爬？思维定式怎么还是破不了？？？再给我 20 分钟冷静我还想不出来？？？

不要一直想奇怪的东西...不要思维定式...换思路...

首先求出一个最小生成树 T，设边权和为 y，那么 x<y 无解。

接下来要分类讨论了：

如果 x=y：

假设这棵树上已经有黑白两色了，我们就不用多心了，直接把这部分的贡献加上即可。

接下来不妨设全染白色，黑色乘个 2 就行。

我们考虑维护最小生成树的断边操作：删去一条再加入一条得到的树等价。

所以我们找出这些满足 T 上路径边权最小值 =w_i 的边 (a_i,b_i,w_i)，设有 p 条，然后就可以算答案了。

如果 x<y：

情况开始复杂了。因为这棵生成树还需要满足异色。

仍然套用上述做法，先强制把 T 所有树边都染掉。

有一个结论，就是这棵树黑色边只有一条。可以手玩证明。

接下来考虑每一条非树边：

如果加入这条边对使生成树答案小于 y，那么这个边必须染白。

否则如果等于 y，可以任意染，但一定要有一个是黑的。

剩下的那些边想怎么染就怎么染。这样这题就做完了。

时间复杂度 O((m+n)\log n)。

总结：

不要神游啊！不要死磕一个方法...

最小生成树有好多突破口，比如加入边权连通性不变...删除一条加入另一条...

这次选用的是后者，也有可能是前者的（比如 CF Abandoning 那题，又是这个...）

仔细思考，冷静计数！！！

ARC 093F

很早以前看过的题目，被提前剧透了是容斥，就没意思了...

先容斥，钦定打破集合 i ，满足其最小值是特殊人。从大到小，设 f_{i,j} 表示集合 i 已经打破，已经考虑插入了 j\sim m 的特殊人，转移即可，时间复杂度 O(nm2^{n})。

总结：

看到限制想容斥我就不说了，现在回想起来这题突然感觉有点意思。

为什么我当时可以想到从大到小？虽然灵感是迸发出来的，但是细思极恐，如果这种题第一反应是从小到大，然后搞了半天发现做不了，换掉了思路，怎么办？

这种限制条件是关于 \max,\min 的需要好好注意了啊...从大到小和从小到大，枚举最小值和枚举最大值可能会出现完全不一样的效果啊！！！

然后第二天考试，T1 dp 题，想到正解的大致思路后，我太紧张，nt 搞了从大到小，就暴毙了，各种边界搞死你，真 tm 服气。感觉好几次这样了，考试就突然考到了最近看的或者最近死过的东西，这是好事还是坏事呢？

ARC 096E

脑洞大开但是 sb 的一天，居然切了一道容斥+组合意义？？？不愧是我...

仔细一想发现这题有两个限制：

每一个集合只能出现 1 次。
每一个数至少出现 2 次。

这就没法 dp 了，那就容斥啊！打破第二个限制，然后问题变成有 i 个出现次数只能是 0 或 1，其他随便。接下来怎么计数？

搞了一堆奇奇怪怪的贝尔数然后发现错了...

我的做法：

枚举这 i 个有 j 选了 1 ，选了 1 的又可以随便带上没有限制的 n-i 个。

=\sum_{i=0}^n\binom{n}{i}(-1)^i2^{(2^{n-i})}\sum_{j=0}^{i}\binom{i}{j}\sum_{k=1}^jS_j^k(2^{n-i})^k

注意 j=0 要特判...

这样就 O(n^3) 了。接下来怎么优化？

交换和式：

=\sum_{i=0}^n\binom{n}{i}(-1)^i2^{(2^{n-i})}\sum_{k=1}^n(2^{n-i})^k\sum_{j=k}^{i}\binom{i}{j}S_j^k

对后面的式子使用组合意义，发现就是 i 个球选择 j 个分成 k 组，其实就是一些数可以不选。设 f_{i,k} 表示前 i 个分成 k 组就好了。时间复杂度 O(n^2)。

yhx 的做法：

...

\sum_{j=k}^{i}\binom{i}{j}S_j^k=S_{j+1}^{k+1}

你说证明？你没发现 f 的方程式和第二类斯特林数完全一致吗...而且考虑加一个垃圾桶组，就是 i 个球分 j+1 组了...不过有个小问题就是垃圾桶可以为空，和斯特林数定义不一致，直接加一个 0 号球就好了...

总结：

容斥！斯特林数！组合意义可以考虑一下优化和式的复杂度！！！

\sum_{j=k}^{i}\binom{i}{j}S_j^k=S_{j+1}^{k+1}

感觉这个恒等式非常不错，仿佛又多积累了一个东西。

这个式子和贝尔数的那个公式有异曲同工之妙（虽然就可以用来推）：

B_{n+1}=\sum_{i=0}^n\binom{n}{i}B_i

ARC 099F

听说是神仙字符串哈希，然后看着题不知道怎么字符串哈希，打开题解发现我...

为什么要被别人的话语束缚住啊...无语了，这不是普通哈希吗，和字符串有半毛钱关系...为什么不仔细想一下这题...

考虑如何判等？一个直观的想法就是对生成的序列判等。

一个序列判等...哈希！

考虑如何表示这个序列？我们使用 X 进制哈希，加一就是在当前的位置 +X^{y}，唯一就是将 y 进行加减。

这是一个类似多项式的操作，满足各种运算律，考虑前缀和，然后开一个 map 就没了。

总结：

u1s1 感觉自己哈希思想还是不够...

序列判等可以大力哈希！这种序列要想到多项式的各种操作！

ARC 101E

ZJOI 前做的题目。

这题妙啊！dp 不能做，换角度用容斥打破复杂度，然后把容斥系数融合在方程里面，就成功优化了复杂度。

具体转移的时候和 CTS 2019 氪金手游一样，把容斥系数扔到方程里，时间复杂度是 O(n^2)。

总结：

有限制就可以容斥，但也不要过分依赖容斥。

直接 dp 复杂度不对如果优化死也想不出来就可以换思路了。而在计数题里容斥是一个更好的选择。

ARC 101F

居然切掉了，感觉自己的脑子还是可以的？舒服了。

我的思路比大家都顺？写一下以免下次想不出来了。

首先我们发现一个机器人只可能在两个出口出去，而且这两个出口分别是左右最近的出口。把操作看成指针，设二元组 (L,R) 表示最大向左了 L，向右了 R 。那么设一个机器人的二元组为 (l_i,r_i)，一个机器人从左出当且仅当 L 先到 l_i。

用 AGC 019D 的套路，转为二维平面，问题变成了二维平面可以向上向右的一条路径，碰到一个矩形边界就在数组上打上标记（是左还是右）。这还是不太好做，思考大概 15 分钟后发现直接 dp 的话，不仅复杂度会炸而且还会算重，怎么办？

换思路继续转化。观察发现这很像 2-SAT 里的二元选择，于是考虑限制，建图。矩形太抽象了，直接换成点。发现如果第 i 个点选择了右边界，那么其左上角的所有点都选择了右边界，同理如果是选择了上边界，其右下角所有点都选择了左边界。这样我们可以建图，然后问题等价于一个拓扑图黑白染色满足一条链均为 BBB...WWW 的方案数，发现问题好像变成了拓扑序计数，更不可做了？

~~然后就不想想了，打开小粉兔的做题记录发现他自己做出来了，感到震惊，思考的动力马上来了。~~

再换思路，灵光一闪后发现我们可以暴力枚举上述的染色方案中所有链的 “BW” 分割点。？做完了？这其实就是单调栈后...矩形...没覆盖的点...？二维偏序序列计数...！

树状数组即可，注意细节很多，时间复杂度 O(n\log n)。

总结：

敢于换思路你一定能行！一定要打破那种安逸感，一定要想啊！

信息转二维平面，限制转图论，枚举关键信息，方案转路径...这些思想一个都不能忘！

有时候要把东西放大，转成广义的问题去做；但有时候不要忘记特殊性质，放大了还不一定能做了。（拓扑序）

小粉兔的题解里出现了新的思路：大力 dp 发现看起来错的是对的...下一次也可以试一下。

ARC 103F

没看到那个互不相等还想到网络流去了...

一道不错的构造题，但是感觉偏简单了，直接对于每条边算一下贡献，从叶子开始向上推进，用并查集合并即可。

总结：

仔细看题目啊！

树上问题，从根节点到子树推，也可以从叶子到根节点推。

ARC 104D

感觉还可以的 dp 题。前期和 dzw 神游了 10 分钟，然后花了 15 分钟想出来了。

枚举 x，然后分数规划，变成方程 \sum(i-x)c_i=0 的解数。

这不好做，考虑正负分开，枚举，然后合并（老套路了）。

这样状态数是 n^2k，利用前缀和优化，dp 复杂度可以做到 O(n^3k)。后面枚举也是 O(n^3k)，所以时间复杂度就是 O(n^3k)。

总结：

这种问题拆开算然后合并是套路了！以前总结里也有写，AGC 041D 也是...

然后前缀和优化不能忘啊...

~~不要神游，找突破口！~~

ARC 104F

感觉比 D 还水...主要是太套路了，然后赛后秒切了。

考虑最大值分治，然后利用贪心优化直接选最大就做好了。

时间复杂度懒得算，反正能过。

总结：

和最值相关就要想最值分治...

计数和贪心结合的思想说真的我也是第一次发现。就是要不重不漏就贪心枚举。

ARC 105F

这场是真的思维场...这题比较套路我不会，D、E 两个思维题都被我做出来了...就记录一下这题吧。

首先题目那个条件显然是二分图。接下来考虑如何计数。

这个连通图比较烦，考虑套路正难则反，枚举 1 的连通块，但是还需要 dp 出二分图总个数。这怎么 dp？

直接枚举左部点显然会算重...怎么办？

这是一个套路：二分图先算连通块。

为啥？因为连通二分图黑白染色只有 2 种方案。

考虑我们的第一反应：直接枚举左部点我们算重了多少次？

是染色方案次。

那我们直接 dp 出总染色方案，然后把算连通二分图个数改成算连通二分图总染色次数好不好啊？

发现做完了！最后算出来除以 2 就是答案！

总结：

正难则反不能忘...

二分图计数转染色方案！连通的二分图只有 2 种，而且总的很好算。

ps：那么我们怎么计算总的二分图个数？可以通过连通的算回去。

这个故事告诉我们，有时候连通还比总的好算，不能思维定式！

ARC 106E

怎么对中国选手这么友好啊...出板子题看谁手速快吗...为什么我看了 5 分钟才看出来...

发现这是一个二分图匹配问题。外层先套个二分，内层求个匹配，看是不是完备即可。

这是一个奇怪的连边，而且很有规律可言。因为 k 很小，考虑使用 Hall 定理，然后套一个 FWT 就好了。

总结：

很有规律可言的连边可以使用 Hall 定理判断匹配是否完备！

ARC 106F

怎么对中国选手这么友好啊...出板子题看谁手速快吗...ARC 真的越出越简单...

~~复习一下 prufer 序列也挺不错的~~

直接上生成函数：

=(n-2)!\prod_i\sum_{j=1}^{\infty}\frac {A_{d_i}^{j}x^{j-1}}{(j-1)!}\ [x^{n-2}]

不写 \text{EGF}：

=(n-2)!\prod_i\sum_{j=1}^{\infty}\frac {d_i!}{(j-1)!(d_i-j)!}x^{j-1}\ [x^{n-2}]

=(n-2)!\prod_i\sum_{j=1}^{\infty}\frac {(d_i-1)!d_i}{(j-1)!(d_i-j)!}x^{j-1}\ [x^{n-2}]

=(n-2)!\prod_i\sum_{j=1}^{\infty} d_i\binom{d_i-1}{j-1}x^{j-1}\ [x^{n-2}]

=(\prod_i d_i)(n-2)!\prod_i(x+1)^{d_i-1}\ [x^{n-2}]

=(\prod_i d_i)(n-2)!\cdot(x+1)^{\sum d_i-n}\ [x^{n-2}]

后面那个就是

=(\prod_i d_i)(n-2)!\cdot\binom{\sum d_i-n}{n-2}

时间复杂度 O(n)。

总结：

~~水水水~~

prufer 序列不能忘！组合排列搞清楚！生成函数很重要！

\color{orange}\text{Codeforces}

CF 506E

牛逼，这题现在想到了 dp 了，比当时强了？

首先 dp 状态数是 O(|S|^2) 的，好像还无法直接压缩自动机呢！

然后自动机不会优化，看题解发现可以考虑路径。

那么挖掘性质，发现 25 点和 24 点的 2 倍的和是固定的！

那么统计 24 点的个数然后单个算即可。但是这好像单个计算也只能做到 O(|S|^4\log|S|)。

然后转化完又可以转化优化自动机状态了！！！拉出一堆链拼起来状态数就只有 O(|S|) 了。

总结：

通过路径和性质来压缩自动机！

这种 dp 转路径的题已经遇到好几次了啊...敲响警钟！

独立思考引出了一个恶心的问题：组合意义？

组合意义很强，...浪费时间...然后可以生成函数...基础不扎实我爬。

CF 547D

不会，丢人。

nb 数学竞赛题。首先点→行列选择一个贡献→二分图。！！！

不能忘记网格图和行列点有关可以建一个二分图！

然后利用构造的二分图 2 染色使得每个点的两种边个数绝对值相差 \leq1。

这个就很仙：点奇偶性 → 欧拉回路，二分图欧拉回路是左 → 右 → 左...

欧拉回路可以抵消边。然后可以给奇点加辅助边，就可以了。

怎么现在脑子还不如当年 9 月？

总结：

行列二分图！

度数奇偶性，欧拉回路！

这种构造太妙了。

CF 578E

不会。

又是一个最优化+构造的脑洞大开题啊！

显然可以发现，如果前面有一段 \text{L...L} ，后面有一段 \text{R...R}，那么我们可以拼凑成 \text{L...LR...R}！！！

发现了什么？是 \text{LRLR}... 的最小划分！这个最小划分显然可以 O(n) 或者 O(n\log n) 求。

但是一个划分一定可以出答案吗？

构造！

但是 \text{LR,RL} 怎么办？做法假了？没有！拆掉！\text{LR,RL}\rightarrow\text{LRL,R}。做完了！！！

细节太多了，爆了一万发 OJ，丢人。

写了一遍，自闭了。

总结：

先找到一个下界再证明是一个解贪心题的好方法...

然后这个下界的答案还可以和构造一起配合!

如果有反例，不要悲伤不要心急，转化一下也许就不是反例了。

CF 575I

咕咕咕

CF 587E

咕咕咕

CF 587F

咕咕咕

CF 605E

我没有脑子 /ll，我连普及选手都打不过了 /dk

思维定式害死我，唉。

图的 dp 非常不好搞，先考虑策略。设 f_i 表示 i 走到 n 的期望。

性质：i 不可能走到 j 满足 f_i<f_j。

因为这个东西是期望，已经平均过了！！！这样还不如待着不动。这个性质看起来非常傻逼，但是非常有用。这样就可以排除很多让你神游的情况。

假设所有点的期望大小排序后是 i_1,i_2,...,i_n，那么 f_i 满足什么？根据上面那个性质：

f_{i_x}=\sum_{j=1}^x[\prod_{k=1}^{j-1}(1-p_{i_x,i_k})]p_{i_x,i_j}f_{i_j}

可以直接做了？我们还无法确定 i 数组啊！怎么办？

冷静一下就可以发现可以从终点开始反推出 i_x 数组。每次找最小的，用 dijkstra 那套理论可以发现，这就是是每次找最小的，然后确定下来它的位置。因为这是 dijkstra 所以这就是对的。

时间复杂度 O(n^2)。

总结：

期望已经平均过了，是可以相互迭代的啊！多发现性质，少神游。

从终点开始反推！

用 dijkstra 的贪心思想来确定需要的序列！这本质其实也是一个动态的最短路！（扩展 dijkstra？咕咕咕了）

CF 1137E

补档...

发掘性质，一次插入只有最前面的 0 有用?

而且最后一个操作很明显提示了是凸包。所以我们维护一个凸包然后单次查询就完事了...

具体的，前端插入一个 0 我们就删完，后端插入就通过全局标记处理，每一次查询的时候，如果凸包“上翘了”就弹出。时间复杂度 O(n) 。

总结：

那个凸包的形式不能忘了，好多数据结构题都是这个形式。接下来就是弹栈，具体问题具体分析即可。

CF 1137F

补档...拉一波当时的题解：

LCT 神题，和 \texttt{[SDOI2017]树点涂色} 是母子题。

首先最大的一定最后删除，所以我们以最大的点为根。

我们考虑每一个点一定是等子树所有点被删完以后再删除。

所以可以用剖分的方式来表示一段链按照深度在删除序列上连续。

这个可以用一个颜色来表示一条连续链的先后删除顺序。

想到这里就是 LCT 了。但是我还是感到奇怪，是怎么想到的...

其实发掘一下性质，对于一次 up 操作就是换根。怎么搞？

发现更有趣的是，之前的根到新根路径上所有点是一段连续删除段。而且是最后删的！

这不就是 makeroot 吗？？？神奇啊！！！

其他的删除序列就是这一条链强制最后，其他的能提在就提早，但是和原“颜色”（删除时间戳）有关，这不就是 access 吗...

那么怎么看排名呢？用树状数组记录每一种时间戳有多少个点。

这在 access 切换虚实链时可以直接维护。

时间复杂度 O(n\log^2n)。

总结：

事实上这都成一个套路了。对这些“全新的”字眼一定要敏感。

还有一道 JOI 的题目也是 LCT 维护抽象信息，改天去补一下。

upd：补了，比这题水多了。

CF 840E

补档...

咕咕咕

CF 1267G

咕咕咕

CF 1270H

没想到最后一步...一开始想了一个线段树维护单调栈，发现假了。

先分成很多的“块”，块满足这一块的 \min> 下一块的 \max。然后这个怎么维护？线好像不可以直接做。

想到了枚举分界点：找出有多少个点满足前缀 \min> 后缀 \max，好像还是不可以直接做。我的思路到此为止。

如果我们换一个思路，枚举后缀最大值呢？注意到关键性质，所有数互不相同，所以如果枚举了一个出现过的 x 满足：

所有大于它的设为 1，小于的为 0，只有一组相邻的 10。

然后就是线段树维护区间最小值了。时间复杂度 O(n\log n)，神啊！

总结：

能转化就转化，挖掘特殊性质！

不要拘泥于枚举位置！枚举最大值找到关键计算方法！从前缀最小>后缀最大，转成枚举最大值！！！

果然这种东西就是开我脑洞的，下次做类似的题能不能做出来啊？/kk

CF 1270G

这也太妙了...

这个条件化一下发现就是一个“跳”的形式。如果做过 AGC 008E 对这个就会非常敏感：连边，基环树，可惜我没有。

利用这个“跳基环树”的环即可。时间复杂度 O(n)。

总结：

这种跳跳的东西，不妨也连边，建图？迭代出 0 的观察力需要锻炼了...

这个套路很重要了啊！

CF 1404E

咕咕咕

我菜炸了 /kk

这题我已经找到了 3 种方法，除了第三种看不懂，以后再说（

方法 3：来自 dqa2020，居然没有题解，谁看懂了告诉我好吗 /kel

CF 1025F

好妙的题目啊！枚举公切线也太抽象了...

转相交更不可做...还好这个出题人没有来一波正难则反...

不相交利用 NOI 模拟赛自己 yy 的东西，用一条线分开然后计数。这题也是这样，枚举的直线就是题解里说的“公切线”。这样极角排序一下就好了，时间复杂度 O(n^2\log n)。

总结：

...不相交，枚举分割线！

CF 1326F

从未见过的全新解法与套路...

首先限制有点恶心，不好做，考虑容斥，打破 i 条边。这最后 IFWTand 一下就出来正确答案了。

容斥完了怎么做？一些段一定要成链，一些段没有限制？如果对于 2^n 的每一种状态都 dp 一下时间复杂度就暴毙了，只能过 F1？

找它的共性：发现打破的限制是 i 与 i+1 的，然后这些东西重排不重排对答案毫无影响。

神仙操作来了：18 的无标号整数拆分很小（大概 385？），直接枚举即可。

对于每一种整数拆分我们要快速算出答案。可以先 dp 出一个状态形成一种链的方案数，然后怎么合并？显然可以子集卷积，这样就可以做到做到 O(n^2\cdot2^n\cdot P_n)，还是只能过 F1。

观察性质去掉子集卷积：第 i 次子集卷积的多项式只有 |S|=t_i 处有值（t_i 指整数拆分第 i 项）。

然后 \sum t_i=|n| ，所以并的个数为 n 的时候已经满足了不交！直接 or 卷积即可。

然后 or 卷积可以直接预处理拿出来，时间复杂度就变成了 O(2^n\cdot (n+n^2+P_n))。然后就能过了。

总结：

重复了亿遍的有限制想容斥...

全新套路：可以利用整数拆分预处理合并 dp，优化复杂度！枚举子集划分也是，一个拆分数，一个贝尔数。以后对这些要敏感！

还有，子集卷积可以在一些特殊情况下转化成正常的卷积...

CF 1418F

咕咕咕

CF 1261F

咕咕咕

CF 494E

翻硬币结论：只有这个硬币存在的 \text{SG} 的异或和的值是游戏的 \text{SG}。

~~这玩意还能循环利用，真的厉害~~

打表出一个很 nb 的东西：

\text{SG}(x,y)=\min(\text{lowbit}(x),\text{lowbit}(y),\text{greatbit}(k))

然后是套路了，还是挺不错的。

考虑求每一个 \text{SG} 有多少种。设当前枚举到 2^i，然后直接做不好做，正难则反！矩形缩小后求扫描线面积并即可。时间复杂度 O(n\log ^2 n)。

总结：

翻硬币结论要记住！不能忘了，以前做过一遍地。

打表找规律！注意 \text{lowbit} 这个东西非常厉害，下次找规律可以考虑这个玩意。

## CF 1175G 咕咕咕 ## CF 1254D 咕咕咕 ## CF 1205E 洛谷博客太垃圾了，又丢档了，所以咕咕咕了。 ## CF 1365G 咕咕咕又丢人了，第一步想了好久。以前我爸和我讲过奇怪的老鼠试毒问题，我居然看了 40 分钟才想到二进制分组... 打开题解我发现如果从直接求值得方向还更简单...我是不是思维定式太严重了... ## CF 1149D 这题真的 nb 啊，根本没想到这题的复杂度还是指数级的。首先利用最小生成树的性质：插入所有 $\leq w$ 的边后连通性唯一。所以我们先加入小边，原来的图就被分成了好多块。如果做到枚举“所有的生成树”？观察就可以发现内部可以走随便的边，因为显然不会出现自环——不可能出现非哈密顿路。外面的也随便走？样例就把你 hack 了，事实上一个小边连通块只能进一次！不然就不是最小生成树了。那怎么办？这是一个哈密顿路径问题，怎么做到多项式？找性质失败，然后我就不会了。题解很妙：不要挑战世界难题！！！考虑优化指数！！！仔细观察就可以发现一个小边连通块如果大小为 $3$，那么一定不会出事，因为内部显然更有优（$2a<2b$）。因此只状压 $\geq 4 $ 的即可。时间复杂度是神仙的 $O(2^{\frac n4}m\log m)$。如果使用双端队列跑最短路可以去掉 $\log$。 ------------ 总结：最小生成树的性质！不要想着挑战难题...可以想一下怎么优化状态啊！找性质也要找对方向！这种题真的不可多得，最近见到好多个 $O(2^{\frac nk})$ 复杂度，不一定要死磕多项式算法！ ## CF 986C 这是一道经典题，noip 2018 前我还不会，感觉还不错这题，虽然没有很难想，但是还要想一会儿... 如果直接建虚点可能要搞一个 FWT？这题的精髓就在于不建出边，连通性就用 dfs 染色。具体就是暴力搜索，如果当前有一个原数组的值就 dfs 它的补集。这样就可以做到不漏地染色了。时间复杂度 $O(n2^n)$。 ------------ 总结：不一定要建出边！思路开阔一点！单纯求连通性可以直接 **dfs** 染色！不要思维僵化！ ## CF 1305G 咕咕咕打开思路神题...不愧是现场几乎无人 AC 的神题...tourist 也不会... 先想到建虚点（根），接下来就是最小树形图？？？这东西怎么搞啊？？？~~不会最小树形图，我觉得接下来应该看一下。~~ 考虑把他转化成我们熟悉的模型。注意到边权和点权有关，考虑性质。仔细观察发现，建完根以后，一个点的贡献 $=$ 度数 $-1$！这说明了什么？我们可以把又有向图转化成无向图！把边权设为 $a_i+a_j$ 跑最大生成树再减掉所有点的点权各一次就是答案！问题简单多了，接下来就是怎么求最大生成树？ #### 方向 $1$：kruskal。每一次加入最大的边即可。考虑枚举边权，然后枚举子集，暴力连边即可。时间复杂度 $O(3^n\alpha)$。实测不加按秩合并 tle 了... #### 方向 $2$：Boruvka。咕咕咕 ------------ 总结：打破思路！转化成熟悉的模型，观察图的性质，最大树形图转最大生成树！思维要活跃啊！不要轻易弃疗... 如果卡常不要忘记搞并查集！这东西真的很有用！ kruskal 也可以优化最小生成树...其实 prim 也很 nb... ## CF 1192B 咕咕咕 ## CF 1178G 以前不会做，题解都看不太懂...现在在想线段树当堆用，没想到拆绝对值？？？虽然只想了 3 分钟没什么好说的... 变成区间操作。接下来又是恶心的双数组问题： - 区间对 $a_i$ 加 $x$。 - 区间询问 $\max \{|a_i|\cdot b_i\}$。把后面绝对值拆掉！！！变成 $2$ 个问题： - 区间对 $a_i$ 加 $x$。 - 区间询问 $\max \{a_i\cdot b_i\}$。接下来是经典问题... 如果是全局操作，怎么做？注意到 $b_i$ 都是正数，对于 $b_i$ 排序，设点初始坐标 $(b_i,a_i\cdot b_i)$，然后一次操作相当于每一个点 $(x,y)$ 都加 $x$，询问最大值最小值... 这个都加 $x$ 的操作很有内味啊...凸包！！！所以做一个凸包，然后对于当前多少个 $x$ 就直接在凸包上二分即可。现在是区间操作，直接块内打标记，块外重构凸包，询问就块内二分块外暴力，时间复杂度 $O(q\sqrt n\log n)$ 。如果把块内二分改成暴力指针的话，时间复杂度就是 $O(q\sqrt n)$ 。因为加的数都是正数，分析一下发现一次只有 $2$ 块被重构，在重构之前一个块最多跑 $\sqrt n$ 次，所以复杂度是对的。 ------------ 总结：求绝对值（切比雪夫距离）最大值可以 tm 拆掉... 经典问题搞清楚！全局 $+\ x\times a_i$ 不要忘了凸包！套路做的还是太少啊... 总算搞清楚分块维护修改的本质了！牺牲复杂度完成全局操作！所以以后如果全局好做可以考虑分块？关于暴力重构的复杂度分析！！！ ## CF 1178F 咕咕咕为什么我当时不敢搞 F2 a1。。。这 F1 F2 有本质的区别吗？~~看来我变强了？~~ ## CF 724E 咕咕咕 ## CF 724F 咕咕咕 ## CF 724G 降智了，一道 ** 题想了 30 分钟...主要是一开始想错了。首先按照套路直接拉出一个 dfs 树搞出环扔到线性基里。一开始一直以为直接做就好了，然后拆位考虑，然后发现没看清题... 然后开始疯狂想 trie+线性基，想着枚举 s，后来 tm 发现 s 不可枚举...我...然后意识到可以把一开始假的拆位考虑给拼上去，然后仔细想一下就做完了？直接枚举怎么做都出事，按位考虑，然后看看线性基上有没有这位，如果没有就只能路径有，否则可以利用线性基的性质——有这位就可以表示出来。 ~~然后一边想一边搞混搞混，以为是每个路径都要算一次。~~ 这样就没了。~~心态崩了，没时间了，直接抄，爽~~ ------------ 总结：想清楚这样做会不会出事！怎么枚举不会爆炸！按位考虑的思想一定要有！异或按位考虑有时候会方便很多！这种求和题按位考虑就很有优势！避免了很多不必要的枚举！线性基不要忘了... ## CF 938F 咕咕咕 THUWC 前做过，当时还是周老师教我的，现在我居然忘了...啊丢人。重新看了一遍题解，感觉我当时是 sb？ ## CF 1017G 咕咕咕 ## CF 183D 咕咕咕