B
有 n 种物品,每种物品价格为 $a_i$,数量为 $c_i$。
要求选取物品的方案,满足价格极差不超过 1,价格总和不超过 m。
最大化价格总和。
$n\le 10^5,m\le 10^{18},a_i,c_i\le 10^9,a_i\neq a_j$
显然只有 \(x\) 和 \(x,x+1\) 两种选择情况。
\(x\) 直接贪心选即可,考虑 \(x,x+1\)。
发现可以先尽量选 \(x\),再尽量选 \(x+1\),再试图进行调整即可。
调整法是解决这种二元规划问题的利器。
C
给定一个序列,可以单点作平方,求使得序列单调不降最小操作步数。
$n\le 10^5,a_i\le 10^6$
存在不是前缀的 1 时无解。
显然从左到右考虑,然而这个数可以积累到很大,我们只能记上一个位置的操作次数。
两个位置之间的操作次数的差形如一个 \(\log\left( \frac{\log}{\log} \right)\),精度误差难以处理。
注意到这个值很小,暴力找即可。
代码
D
给定一个字符串,要求把它分配为若干长度不超过 k 的子串,最小化每个子串结束字符构成的集合的大小。
$1\le k,n\le 2^{18},\lvert\Sigma\rvert\le 18$
转化的好题。
思路解析
注意到转化中有很多优美的性质。
把都合法,在状压意义下变为哪些不合法。
正解
本题一开始有很多转化方式。
注意到字符集很小,那么本题的基调是状压上的。
考虑一种转化:
最后一个位置必选,然后把我们的集合放到串上,此时不存在两个相邻位置距离 \(\geq k\)。
也就是合法当且仅当不存在任何一个长为 k 的子串中不包含选定的字符。
那么若刻画这些子串的字符集合为 \(T_{1},T_{2},\cdots,T_{n-k+1}\),则合法当且仅当 \(S\) 与这些集合都有交。
由于字符集很小,我们可以去判断每一个 \(S\) 是否合法,做到最小化。
使得 \(S\) 与每一个 \(T_{i}\) 都有交比较困难,但容易知道哪些 \(S\) 和某个 \(T_{i}\) 无交(正难则反)。
于是只需对 \(U-T_{i}\) 打上标记,那么它的所有子集都不合法。
高维前缀和维护即可。
实现细节
值得注意的是根据题意,我们的转化是不充要的。
必须钦定把最后一个位置的字符选上。
E
给定长为 $2n$ 的序列,可以任意交换 $a_i,a_{i+n}$。
定义一个序列的权值为把所有 $\forall i\in[1,n],~a_{2i}+a_{2i-1}$ 拍下来后的极差。
最小化序列的权值。
$n\le 10^5$
思路解析
分析,简单变换。
考察性质,使用双指针。
使用 dp 和动态 dp 来实现。
正解
偶数情况直接贪心即可。
奇数情况下的情况非常复杂,进行抽象。
考虑了交换和贡献,可以通过重标号,把原问题变为一个奇环,每个边的两边各有一个权值,可以翻转边的一个模型。
极差的性质很差无法直接 dp,二分加 2-sat 也完全做不了。
但是注意到这样操作生成的数值只有 \(4n\) 种,并且极差具有一定意义下的单调性。
具体来说,在值域序列上考虑的话,固定一个端点,则合法性有单调性。
所以祭出 双指针。
(枚举加二分因为枚举的一维复杂度,大概率没有前途了)
那么只需支持加入删除位置来判定。
Easy Version 可以 2-sat,但是看起来就没前途。
注意到,这个环的只在相邻处有影响,容易想到 dp,发现我们加入删除,只需改变共 \(\mathcal O(n)\) 个相邻的转移关系。
于是 动态 dp,使用矩阵刻画转移,是一个位运算的 and or 矩阵,想一下是有结合律的,线段树维护即可。