Codeforces 补题 and 练题计划

_sunkuangzheng_ · 2023-08-29 13:45:14 · 个人记录

设有两段区间 a,b，我们希望 a 成为最大值，b 成为最小值，那么我们一定会问只有 a 会的问题；问 a,b 都会/都不会的问题没有意义。因此，答案是 2(|a|-|a \cap b|)。我们枚举 a，考虑什么样的 b 是有意义的。分类讨论：

显然答案是 2|a|。

我们贪心的选择右端点最靠左的区间 和 左端点最靠右的区间，进行比较。

此时答案为 2(|a| - |b|)。发现我们只需要找长度最小的区间。如果这个区间并没有包含，那么显然已经考虑在情况 1,2 中，而这种情况比包含任意一个长度大于等于这个长度的区间都优。如果包含，选择这个即可。

时间复杂度 \mathcal O(n)。评测记录。

• CF1861D Sorting By Multiplication ^*1800

策略是前半部分变成负的，后半部分变成正的。考虑在正负两种情况下你需要操作一次的条件是什么。枚举分界点，动态更新答案。时间复杂度 \mathcal O(n)。评测记录。

• CF1862F Magic Will Save the World ^*1800

显然的是，一边攒魔法一边打怪物没有任何意义，我们的策略是先攒够魔法再一次性暴击怪物。枚举用多少“水系咒语”打怪物，剩余的用“火系咒语”。但是你要保证那个值可以恰好打死若干只怪物，不能出现打不死怪物的情况。

那么我们背包一下，时间复杂度 \mathcal O(n^2s)，卡着能过。要想卡个常的话可以 bitset。评测记录。

• CF1846G Rudolf and CodeVid-23 ^*1900

状压 + 最短路裸题，几乎是板子就不说了。时间复杂度 \mathcal O(2^nm \log (2^nm))。

• CF1841C Ranom Numbers ^*1800

说句闲话：这题想了半小时，写了半小时，拍了半小时，最后假了。

贪心。变小只改最后一个，变大只改第一个，感性证明。时间复杂度 \mathcal O((|\Sigma|)^2n)，本题 |\Sigma| = 5。评测记录。

• CF1833G Ksyusha and Chinchilla ^*1800

首先 n \bmod 3 \ne 0 肯定无解；然后随便找个点当根 dfs 一遍，f_u 表示 u 为根的子树里的多余点的剩余量，直接搜即可。评测记录。