模拟赛 10 题解

思维+状压+数据结构+dp

A.分配

结论题，有专门的海盗分钻石问题。

$s=1$， 考虑倒推，只要保证有 $\lceil\frac n 2\rceil$ 支持即可。

$s=2$，只剩四个人的情况，肯定编号为奇数的人必死。

所以他会无条件支持jack。

之后贪心想一想，看看证明，打个表，二进制找找规律即可。

B.游戏

先预处理出对于每一列，哪些位置是相同的。

接着我们采取两次状压：$st[S]$ 表示问了 $S$ 中的列，还不清楚的行有哪些。

这个可以根据最后一列进行转移，同时统计问到每个状态还有几个不清楚的。

之后我们倒序考虑每个状态，考虑每个没问的行，加上问到这个行的次数。

最后统计完后/siz，还记得加一。

转移：

f[S]=E(\sum_{S\subseteq T\and siz[T/S]=1}f[T]\times siz[T])+1

C.数列编辑器

这个由于是单点操作，区间查询，可以采用树状数组来实现。

分别建出前缀和后缀树状数组，它们之间的位置就是指针的位置。

不难发现，每次加入和删除都是对前缀的末尾进行操作，这个可以轻松维护。

指针移动时，只需要像栈一样，将元素由前缀向后缀移动即可。

区间查询时，如果区间被树状数组完全包含，那么可以直接查询。

反之可以将区间拆成两段来合并。

单点修改直接做就好，判断位置在前缀还是后缀。

D.牢不可破的子序列

考试的时候没切，真是丢死人了。

我们设 $f_i$ 表示已经处理到 $i$ 的最大权值和，发现转移并不好转移。

一开始的想法是从 $f_{i-k}$ 转移，加上中间的那一段。

强制加上 $sum_{i}-sum_{i-k}$ 是为了保证区间长度大于 $k$ 的约束，使其满足条件。

这样看起来是对的，但是忽略了一种情况：

我最后用 $k$ 拼起来的那一段，他前面的部分不一定大于等于 $k$，只要保证最后拼起来大于等于 $k$ 即可。

而如果我们用 $f$ 数组转移，就忽略了这一点（可以看图）。

所以我们要引入一个新数组 $g$，其中 $g$ 的最后一段长度可以是任意的，那么就有

$f_i=\max(f_{i-1},g_{i-k}+sum_{i}-sum_{i-k})$

同时我们还要更新 $g$，这就类似于最大子段和。

注意不连续时要保证合法性，即从 $f_{i-1}$ 转移。

$g_i=\max(f_{i-1},g_{i-1}+a_i)$