这次不看题解只会 AB 两题。

A

这个题当时还是会做的。

如果 $\exists i,A_i > B_i$ 就无解,否则我们就每次暴力找到当前 $A$ 中字典序最小的一起往上提升即可。

Code

B

有些博弈论问题要去关注一下题目里的不动量。

设先手的得分为 $x$,后手的得分为 $y$,$n$ 个数的 xor 和为 $sm$,那么有 $x \text{ xor } y = sm$。

按位考虑:如果 $sm = 0$ 就是平局,因为每一位都是相等的。

考虑 $sm$ 的最高位,现在变成了你有 $a$ 个 $1$, $b$ 个 $0$,问先手能否拿到奇数个 $1$。

首先我们考虑一下 $b=0$ 的情况:首先 $a$ 一定是奇数,然后我们发现如果 $a \bmod 4 = 3$ 那么先手就必败否则先手必胜。

那么我们考虑一下 $b$ 的用处:如果先手选了一个 $0$ 就可以把局面推给后手。

如果 $b$ 是偶数就对局面完全没影响:后手只需要在先手选择 $0$ 的时候模仿他的操作即可,下面考虑 $b$ 是奇数的情况:

如果 $a \bmod 4 = 3$ 的话,那么先手通过取了一个白色棋子将其变成了后手的必败局面(白色妻子为偶数无影响,黑色棋子满足必败的数量),所以先手是必胜的。

如果 $a\bmod 4 = 1$,先手如果取黑色棋子,然后模仿后手操作的话,可以发现后手取到的黑色棋子一定是偶数个,所以先手必胜。

所以这个题目就是判断是否 $a \bmod 4 = 3$ 且 $b \bmod 2 = 0$ 。

Code

C

这个题和 $A$ 的想法完全不一样。

首先我们考虑如果有要求字符 $a$ 变成字符 $b$,我们就连有向边 $a \to b$。重边显然可以去掉,

我们发现题目可以转化为我们现在有一个 $20$ 个点的新图(初始无边),我们要按照一定的时间顺序加入一些有向边满足在原图中如果有边 $u \to v$ 那么新图中要求 $u$ 能经过时间顺序递增的边到达 $v$。

显然每个弱连通分量都是独立的,我们可以断言对于一个弱连通分量,设它最大的导出 DAG 子图大小为 $m$,它需要的最少操作次数为 $2n-m-1$。

这样可以感性理解一下:我们可以花费 $2n-2$ 的方法让所有点之间都是互相可达的,但是我们可以选出一个 DAG 让他们之间不用循环连两次边,因为 DAG 中只有前面连向后面的边,所以我们要找一个最大的 DAG。

证明:

首先我们先证明能取到:我们设不在 DAG 上的点编号为 $m+1,m+2,\ldots,n$,在 DAG 上的点按照拓扑排序编号后为 $1,2,\ldots,m$,那么我们可以连边 $(m+1,m+2),(m+2,m+3),\ldots,(n-1,n),(n,m+1),(m+1,m+2),\ldots,(n-2,n-1)$,共 $2(n-m)-2$ 条边。

然后我们连 $(m+1,1),(1,2),(2,3),\ldots,(m-1,m),(m,m+1)$ ,总共 $m+1$ 条边,所以总的操作次数为 $2n-m-1$ 次。

然后我们证明这是一个下界:下界好像不是很好证明,先咕一咕

D

首先我们发现如果我们想保证最大值的话我们可以从大往小填数,然后对于每个数我们可以预处理出来他是不是某一行的最大值,是不是某一列的最大值。

我们考虑维护一个长宽可变的答案矩阵,如果当前这个数是某一行的最大值,我们就新增一行并且将这一行最后一列的地方填上这个数,列同理。

如果这个数字根本不是最大值,我们就可以维护一个没有填的格子的矩阵,这里注意我们要用一个队列维护,每次从左到右(从上到下)按顺序加入新增的空格子,这样才能保证最大值左面(上面)是递增的。

这样构造显然满足性质,但是我想不到,以后构造可以尝试一下动态调整。

Code

E

操作实际可以看成我们每次一个 $1$ 可以吃掉相邻的一个数字,$0$ 可以吃掉相邻的一个 $0$。

遇到计数问题先考虑如何解决判定问题:我们假设匹配到了长串的第 $i$ 个,短串的第 $j$ 个,如果短串下一个是 $1$ 的话,我们找到长串中下一个是 $1$ 的位置,用它吃掉前面的 $0$ 就好了。

如果下一个是 $0$ 的话,假设当前短串 $0$ 的连续段长度为 $k$,我们找到一个最小的 $i' > i$,满足 $[i'-k+1,i']$ 都是 $0$。如果 $i' = i+1$ 就直接把这个 $0$ 接到后面就行,否则显然 $i'-k$ 是 $1$,用这个 $1$ 把前面的东西都吃掉就行了。

但是发现这个情况对于开头一堆 $0$ 的情况并不适用,所以我们需要特判掉开头的一堆 $0$ ,也就是从第一个 $1$ 开始计算。

发现这个贪心保证了每一个可行的串都只会在最前面被匹配完,类似这种的贪心我们可以直接对其设计一个 dp 去跑,是不重不漏的。

那么我们考虑设 $f_i$ 表示匹配到第 $i$ 个字符有多少个串能成功,转移只要预处理这个地方加一个 $0,1$ 后跳到哪里就好了。优化转移需要预处理出 $0,1$ 连续段个数,然后倒着求一下转移点。

设第 $i$ 个点距离上一个 $1$ 的距离为 $d_i$,最后统计答案的时候我们发现只有 $d_i \leq d_n$ 的点才能成为结尾(能被最后面的 $01$ 等效消过来),所以只加上这些位置的 dp 值就好了。

还是要看一下代码辅助理解。。

Code

F

最大流=最小割。首先考虑 $k=1$ 怎么做:我们就枚举是否割掉这一条边,分别跑一个最大流就好了。

到这个问题上,我们考虑去枚举所有 $2^k$ 种可能的割边方案,分别跑一个最大流就好了,这样复杂度一看就有点卡(实际上也是过不去的)。

我们可以考虑用递归的方式处理出来每种割边的方案对应的权值,我们要求的实际上就是支持加边删边查询最大流。

删边可以通过存分治树上 log 个残量网络的边权来实现撤销,加边我们可以暴力增广 $25$ 次。

然后就各种玄学卡常就过了吧。。建议没事不要写这题。

Code

Last modification:August 21st, 2020 at 08:59 pm
如果觉得我的文章对你有用,请随意赞赏