随机做提记录

· · 个人记录

带 * 的是看题解的。

P5101

首先可以发现，颜色提前染好肯定是优的。

然后我们先钦定一下最后状态是哪两个颜色，设最终状态为 ab，然后可以发现显然初始状态也只能有 a,b 两种颜色。

而且不难发现，以下策略是最优的：

那么可以得到一个结论：我们将相同颜色的段缩起来，那么除了两边的段，每段长度都必须是偶数。

考虑如果全部强制是偶数的话怎么做。

可以发现这完全等价于将 [1,2]，[3,4]，[5,6] 这些绳子一起分组。

那么问题就变成了有一些数对，然后我要找出一个数对使得与它们的交尽量大。

显然可以用一个桶+指针维护这个东西。

如果允许两边段落为奇数的话，直接修改一下两端的奇偶性，然后重新绑定，再做一遍即可。

时间复杂度 O(n)。

*CF1605F

被牛逼题打爆了。

原题的形式不是很好做，考虑怎么转化。

发现找序列的过程可以转化为以下形式：

转化成这种形式后，发现或许能建立一个好序列到坏序列的映射。

我们可以找出一个坏序列的极长好序列，然后就能转移过来了。

同时为了避免算重，我们将单独的 0 给放入极长好序列当中。因此剩下的坏序列所有数互不相同且不为 0。

首先我们设 f_{i,j} 为当前用了 i 个位置，所有位置或起来有 j 个 1 的方案数。

简单容斥一下即可：f_{i,j} = \sum_{k = 0} ^ {j} (-1)^{j - k} \binom{j}{k} 2^{ik}。

然后考虑怎么建立映射。

设 g_{i,j} 为当前用了 i 个位置，所有位置或起来有 j 个 1 的坏序列个数，与之相对的，r_{i,j} 为当前用了 i 个位置，所有位置或起来有 j 个 1 的好序列，同时再设 h_{i,j} 为当前用了 i 个位置，所有位置或起来有 j 个 1 的所有数都互不相同的序列。

同时不难发现 $g_{i,j} + r_{i,j} = f_{i,j}$。 对于 $g_{i,j}$，考虑直接钦定好序列的长度和好序列用的位置，可以得到式子： $$g_{i,j} = \sum_{k = 0}^{i-1} \sum_{t = 0}^{j-1} \binom{i}{k} \binom{j}{t} 2 ^{t \times (i-k)} r_{k,t}h_{i-k,j-t}$$ 注意判断 $i$ 是奇数的情况。 直接做即可，时间复杂度 $O(n^4)$。 ### *CF1552H 不是我能想出来的东西。 首先先用 $1$ 次询问查出矩阵的面积，然后考虑怎么用 $3$ 次询问求出矩阵的周长，可以转换为求一条边的长度，设为 $l$。 可以尝试每 $w$ 行问一次，发现只要当 $w|l$ ，那么答案就是 $S/w$，否则的话既有可能是 $S/w$，也有可能是 $S/w + 1$。 我们取 $w$ 为 $2^k$，可以通过二分找出最大的 $w$ 使得 $w|l$，不难发现宽即为 $w$ 时候的答案减去 $w\times 2$ 时的答案乘 $2$ 后的差。 直接二分即可，次数 $O(\log \log n +1)$，可以通过本题。 ### *CF335F ~~没吃过馅饼能不能不做这个题啊~~ 首先从大往小做非常显然。 然后考虑反悔贪心。 我们可以发现，每次反悔贪心相当于说选择一个之前免费的馅饼，然后将当前两个价格相同的馅饼都填进去。 也就是说本来是 $1$ 号和 $2$ 号馅饼配对的，现在改为 $1$ 号和 $3$ 号馅饼，$2$ 号和 $4$ 号馅饼配对（其中 $3$ 号馅饼和 $4$ 号馅饼价格相同） 同时我们的反悔贪心也要保证每个免费的馅饼都能拆贡献给 $2$ 个馅饼用。 以上面为例子，我们假设 $2$ 号馅饼的价格为 $k$，$3$ 号馅饼的价格为 $w$。 那么如果 $2 \times w >k$ 的话可以用两个价格为 $w$ 的馅饼替换 $2$ 号馅饼，并且我们考虑如果再加入两个价格相同且比 $3$ 号更低的馅饼的话，显然是将两个 $3$ 号馅饼给他们并且 $2$ 号馅饼还给 $1$ 号，所以说可以设置此馅饼的贡献为 $2 \times w - k$，这样只要拆掉这个馅饼就可以直接还原 $2$ 号给 $1$ 号的情况。 因为上面加入了一个价值为 $2 \times w - k$ 的馅饼，因此当前价值 $w$ 可能大于 $k$，那么显然 $w$ 大于 $k$ 的时候直接拿 $w$ 替换即可。 最后堆内的馅饼价值和即为免费的馅饼价值和，与总和减一下就是答案。 时间复杂度 $O(n \log n)$。 ### CF1713F 首先有个通过 Lucas 定理能得到的结论：对于组合数 $\binom{i}{j}$，它是奇数当且仅当 $i$ 包含 $j$。 然后先随便手玩一下，首先 $n = 2^k$ 的话直接 IFWT 即可，但是 $n$ 不是 $2$ 的次幂的话有点难做。 我们考虑递归求解，不难发现设 $n = 2^k + t$，其中 $k$ 取到最大值，那么求解 $[2^k + 1,2^k + t]$ 是可以直接递归下去的。 递归完后半部分后先经过一次 FWT 求出后半部分对前半部分的贡献，然后前半部分直接 IFWT 即可。 时间复杂度 $O(n \log n)$。 ### CF1483E 首先不难想到倍增。 然后考虑怎么在一个区间 $[l,r]$ 内找到答案。 首先有个不难想到的方案：定一个比例 $x$，然后每次将一个区间按照 $x$ 的比例裂开来。 但发现怎么卡都过不去，怎么办呢？ 考虑如果钱比较多的话，其实取 $(l+r) / 2$ 是更优的。 于是我们考虑当钱够多时，裂开成两份，否则按照我们的比例裂开。 首先我先尝试了一倍的 $mid$，发现不够，不过开成两倍，比例调成 $0.3$ 后就过了。 次数最多 $100$ 次，还挺优的。 ### *Gym101620 I 没见过的套路。 考虑一段什么时候是合法的。 假设区间长度为 $len$，那么显然只要存在 $len - 1$ 对相邻的数这个区间便是合法的。 直接维护相邻的数即可，这可以通过线段树维护区间 min 实现。 时间复杂度 $O(n \log n)$。