CF724 题解

[toc]

AC代码

A. Omkar and Bad Story

容易发现只有存在负数时无解。

B. Prinzessin der Verurteilung

根据题目条件，字符串的 $MEX$ 最长只有 $3$ 位，直接暴力找就行。

C. Diluc and Kaeya

给定一个长度为 $n$ 的字符串 $s$ ，串中仅含有 D, K 两种字符。对于字符串 $s$ 的每个前缀询问：你最多将这个前缀子串划分为几部分，使得每一部分中 $D$ 的数量与 $K$ 的数量比例相等。

$n\leq 5\times 10^5$ 。

对于每个长度为 $i$ 的前缀串 $pre(s,i)$ 记录 $D,K$ 的数量，设为 $d_i,k_i$ 。 $pre(s,i)$ 能够划分成的最多段数就是 $\frac{d_i}{k_i}$ 在长度小于 $i$ 的前缀串中的出现次数，即 $\frac{d_i}{k_i}=\frac{d_j}{k_j}(j<i)$ 。

D. Omkar and Medians

给定一个大小为 $n$ 的数组 $b$ 询问是否存在一个数组 $a$ 使得 $b_i$ 是 $a_1,a_2,\ldots,a_{2i-1}$ 的中位数，数组 $a$ 中不存在重复元素。

$n\leq 2\times 10^5$ 。

直接给出结论：不存在 $b_j(j<i)$ 使得 $\max(b_i,b_{i+1})<b_j< \max(b_i,b_{i+1})$ 时存在，否则不存在，下面naive地证明一下：

不妨先假设 $b_i<b_{i+1}$ 方便讨论，考虑反证法，由于 $b_i$ 是 $a_1,a_2,\ldots,a_{2i-1}$ 的中位数，假设 $a_1<a_2<\ldots<a_{2i-1}$ ，那么 $b_i=a_i$ 。当我们加入 $a_{2i}$ 和 $a_{2i+1}$ 时，因为 $b_{i+1}>b_i$ ，因此 $a_{2i},a_{2i+1}$ 必须同时 $>a_i$ ，因此 $b_{i+1}=a_{i+1}$ 。但是如果存在 $b_j$ 使得 $b_i<b_j<b_{i+1}$ ，就会导致不存在与 $b_j$ 恰好相等的 $a_k$ ，因此不成立。

E. Omkar and Forest

有一个 $n\times m$ 的网格图，每个单元 $A_{i,j}$ 有一个数值，输入时 $A_{i,j}$ 由 0 或 # 两种字符构成，0 表示该单元的数值为 $0$ ，否则表示该单元的数值不确定。询问有几个满足以下条件的图：

• 任意两个相邻（四联通）单元格之间的差值不超过 $1$ 。
• 如果某个与单元格 $A_{i,j}$ 相邻的所有单元格的数值都大于等于它，那么 $A_{i,j}=0$ 。
• 任意 $A_{i,j}$ 是一个非负整数。

$n,m\leq 2000$ 。

根据评论区，本题有一个原题 USAJMO T2 。

由于每个单元格 $A_{i,j}$ 的相邻单元权值只能为 $A_{i,j}-1,A_{i,j},A_{i,j}+1$ ，并且至少存在一个单元格的数值严格小于 $A_{i,j}$ ，因此一定可以从 $A_{i,j}$ 每次走到一个数值恰好为 $A_{i,j}-1$ 的单元格，直到走到 $0$ 。这说明 $A_{i,j}$ 的数值就是到距离他最近的0的曼哈顿距离。

因此，如果确定了图上的 $0$ ，整张图就唯一确定了，这说明合法的图的数量就是 $2^{mn-zero}-[zero=0]$ ，其中 $zero$ 表示图中初始为 $0$ 的单元格数量。注意，如果一开始没有 $0$ ，要排除整张图没有 $0$ 的情况。

F. Omkar and Akmar

有 $n$ 个点 $p_i$ 围成一个圆环，编号分别为 $p_i=i$ ，所有点初始都是空的。

Omkar 和 Akmar正在这个圆环上玩一个游戏：每次选择圆环上的一个点，在这个点上写一个字符 A 或 B ，注意环上不能有两个相邻的相同字符，当某一方无法继续写下字符时他就输了。

询问一共有几种不同的游戏？一个游戏只有在某一方无法再写下字符时才会结束，并且任意两个游戏被认为是不同的当且仅当至少某一轮中两次选择不同。

$2\leq n\leq 10^6$ 。

感觉本题真正的难点就是理解什么叫不同的游戏！

首先考虑这个游戏先后手谁必胜，这个问题只需要考虑终结状态，这个游戏的终结状态一定是 $ABAB\ldots AB$ 或者 $BABA\ldots BA$ 。因此本游戏一定会进行偶数轮，后手必胜。这是因为如果连续出现了两个 $A$ ，由于这两个 $A$ 不能相邻，因此他们之间一定能插入一个 $B$ 。

搞清楚这个问题之后，本题变成了：圆环上有几种不同的合法 $AB$ 序列（或者 $BA$ 序列，本质相同，只需要在最后 $\times 2$ 即可）。由于 $AB$ 一定是交替出现的，因此我们可以枚举圆环上有几个空位来解决这个问题。假设环上有 $k$ 个空位，下标分别为 $x_i$ ，那么这些空位一定满足一系列不等式：

这个东西是个经典问题，最近已经有三次CF出现了。。。具体解决方案可参考 CF1523E的题解 。结论是 $\binom{k}{n-k+1}$ 。但是要注意这是在圆环上，这个不等关系有可能会导致 $x_1=0\cap x_k=n-1$ ，也就是首尾都为空位的情况。因此需要容斥一下，去掉这种情况，最终结论为 $\binom{k}{n-k+1}-\binom{k-2}{n-k-1}$ 。