Codeforces Round 961 (Div. 2)

C：log 推柿子
D：正难则反，dp 补集
比赛链接

Problems	AC
A. Diagonals	○
B1. Bouquet (Easy Version)	○
B2. Bouquet (Hard Version)	○
C. Squaring	⊕
D. Cases	⊕
E1. Let Me Teach You a Lesson (Easy Version)
E2. Let Me Teach You a Lesson (Hard Version)

B2

这是问题的困难版本。唯一的区别是，在这个版本中，不是列出每朵花的花瓣数量，而是为所有类型的鲜花设置了花瓣数量和商店中的鲜花数量。

一个女孩正在准备她的生日，想要买一束最美丽的花束。商店里共有 $n$ 种不同类型的鲜花，每种鲜花的特征是花瓣数量和该类型鲜花的数量。一朵有 $k$ 片花瓣的花需要 $k$ 个金币。女孩决定，她用来装饰蛋糕的任何两朵花之间的花瓣数量差异不应超过一朵。与此同时，女孩想要组装一束花瓣数量尽可能多的花束。不幸的是，她只有 $m$ 币，她不能花更多的钱。她最多可以在花束中组装多少片花瓣？

这个 B2 主要的难点是，每个物品的数量可以有多个。这其实变成了一个类似于背包的问题。但是因为题目里面有个限制，你最多只需要同时考虑两个物品。

现在问题转化为，你有两种物品，价值分别是 a 和 a + 1，分别有 x 和 y 个，你需要在价值不超过 k 的情况下尽可能多拿。

那我们的策略就是先把能拿的 a 都拿了，剩下还有钱的话把 a + 1 都拿了。如果还有剩的话，可以把 a 替换成 a + 1。

这种策略显然正确，但是赛时又脑瘫代码出小问题了。。。。。。

C

ikrpprpp 找到一个由整数组成的数组 $a$ 。他喜欢正义，所以他想让 $a$ 公平——也就是说，让它不减。为此，他可以对数组的索引 $1 \le i \le n$ 执行正义行动，将 $a_i$ 替换为 $a_i ^ 2$ （位置 $i$ 处的元素及其平方）。例如，如果 $a = [2,4,3,3,5,3]$ 和 ikrpprpp 选择对 $i = 4$ 执行正义行动，则 $a$ 会变为 $[2,4,3,9,5,3]$ 。

最少需要多少次正义行为才能使数组不减？

$1 \le n \le 2 \cdot 10 ^5$

$1 \le a_i \le 10 ^ 6$

这什么屑题啊。。。。。首先你是知道怎么操作的，唯一的问题就是会爆 ll。那么你知道的，我们肯定是开 log。

假如 $a[i]$ 被操作了 $c[i]$ 次。我们需要满足 $${a_i}^{2^{c_i}} \le {a_{i+1}}^{2^{c_{i+1}}}$$

$$2^{c_i} \ln a_i \le 2^{c_{i+1}} \ln a_{i+1} $$

$$2^{c_{i+1}} \ge 2^{c_i} \frac{\ln a_i}{\ln a_{i+1}}$$

$$\displaystyle c_{i+1} \ge c_i + \log_2 \frac{\ln a_i}{\ln a_{i+1}}$$

D

每组数据给定 $n, c, k$ 三个数和一个长度为 $n$ 、包含 $c$ 个不同字母的字符串 $s$, 要求将 $s$ 拆成若干个长度不超过 $k$ 的子串，使所有子串的末尾字符种类数最小，并输出最小数量。

$1 \le k \le n \le 2^{18}$, $1 \le c \le 18$

题目给定的限制相当于：选出一个字符集合 $S$，原字符串中每个长度为 $k$ 的区间至少有一个字符 $\in S$，且原串的最后一个字符一定 $\in S$。并使得 $\left| S \right|$ 最小。

相当于，对于任何一个合法的 $S$，与每一个子区间的字符集都有交。

因为不合法的 $S$ 的子集一定也是不合法的，所以我们考虑 dp 不合法的 $S$。也就是合法的 $S$ 的补集。

$f[S]$ 表示 $S$ 中的字符都不存在是否会使得答案非法。

初始我们令：

• 每个长度为 $k$ 的区间构成的字符集合 $s$，$f[s] = true$。
• 仅包含最后一个字符的状态 $s$，$f[s] = true$。
• 除此之外的其他状态都为 $false$。

转移就是 $\forall 1<s < 2^c, f[s]=\operatorname{AND}_{2^i \in s}{f[s-2^i]}$

复杂度 $O(cn + c \times 2 ^ c)$