某种特殊的解题方法

一次遇见两个同种思路的解题小技巧...

[ABC266G] Yet Another RGB Sequence

Solution

先分别取出 $k$ 个 $r$ 和 $g$ 组成 $rg$（重点技巧）；再对 $r$ 和 $g$ 进行插入操作，先插入 $b$，$g$ 和 $rg$，再插入 $r$。

这里需要注意一个坑点，在插入 $rg$ 时，我们考虑在已有的字符前插入，但 $rg$ 的个数已经确定，所以在后面的插入 $r$ 的时候要舍去 $g$ 前面的位置，最后得出 $C_{(G-k)+B+k}^k\times C_{(G-k)+B}^B\times C_{B+(G-k)+k}^{(R-k)}$。

[ARC050B] 花束

Solution

首先这道题可以考虑二分答案，思考一下，如果 $k$ 个花束都能做得出来，那么 $k-1$ 个花束也能做的出来，具有单调性。

同样的，我们运用技巧，发现题目中无论做哪一种花束都至少需要用到 $1$ 朵红花和 $1$ 朵蓝花，由于一个花束拥有两个量的时候很不好处理，那就不妨都减去 $k$，就把题目转化为用 $x-1$ 朵红花做第一种花束，用 $y-1$ 朵蓝花做第二种花束，设二分答案到 $k$，那么 $k$ 应该满足 ${\displaystyle \lfloor \frac{R}{x-1}\rfloor +\lfloor \frac{R}{x-1}\rfloor \ge k}$ 即可。

---

其余题目

[ABC140F] Many Slimes

前言

考场上想出解法，细节没有到位...

原来还有 $O(n^2\times 2^n)$ 的做法，但我的可是 $O(n\times 2^n)$ 啊！

Solution

看数据范围，一眼算出大概是$ O(n \times 2^n)$，小小思考一波，发现题目只与数的大小有关，所以先离散化，设离散化后的数量为 $m$；

我们可以尝试枚举第 $i$ 轮，接着可以想到在执行到第 $i$ 轮时，已经存在 $2^{i-1}$ 个数，也就是这轮最多会出现 $2^{i-1}$ 个新的数；

接着考虑枚举数的大小 $j$，显然的只有当数值 $k$ 满足 $k>j$ 的时候，$k$ 才能产生 $j$，即 $k$ 的范围是 $[j+1,m]$，可以想到对这个范围区间做后缀和维护，以此判断 $j$ 在当前轮次最多能生产出多少个，细节较多...

---

[ABC283E] Don‘t Isolate Elements

前言

考场上一直想 $f_{i,0/1}$ 的解法，想了 1h 发现转移不了一点。

Solution

考虑 dp，因为每一行的改变只会对上下两行影响，所以我们尝试设 $f_{i,0/1,0/1}$ 表示到第 $i$ 行时，当前行是否异或 $1$，前一行是否异或 $1$且保证前 $i$ 行全部符合要求，转移时暴力判断状态是否不存在孤立点即可。

---

[ABC148F] Playing Tag on Tree

Solution

解题思路也是非常值得学习的，开始分析吧！

很容易转换题意为小A追小T，小A和小T均以最优策略时小A的最小追逐路径；

以后遇到此类题，可以先以追的人为根建树（小A），否则会把题目变得更加麻烦，有时还需要分类讨论。

有多种解法，百解不离其宗，讲我用的吧，我这里用 LCA 维护树上距离，由于小T的最优策略就是跑到叶子节点，然后反复横跳，所以使叶子节点离小A的距离越远越好；

同时要判断小A是否可以提前阻拦小T，怎么判断呢，可以把其转化为求小A和小T哪个更先到某个叶子节点即可。

这里有个需要注意的点，就是最后到底计算到的步数是否要 $-1$，但画几个图会发现，我们只需要计算小A到叶子节点前的节点就可以了，自己证明...

---

P1417 烹调方案

Solution

可以发现，如果没有 $b_i$ 的话，这就是个01背包板题，考虑对所有美食按优先度排序，这里不多分析，自己推...

那为什么排序呢，而不能像平常一样做呢？

平常做01背包的题时，由于 $i$ 的价值永远是不变的，所以 $i$ 讨论的顺序对结果不影响；

但是这道题中，如果你先讨论了 $i$，再讨论 $j$，$j$ 的价值会减小，反之 $i$ 的价值会减小，而先讨论哪个会使答案更优是不确定的，所以直接讨论是错误的。

后记

• 总而言之，对于背包中价值会变时，需要先注意和考虑排序！！！

---