本文迁移自洛谷原文。
题目大意：
有一个 $4\times n$ 的 $01$ 矩阵。你每次可以选择一个 $k \times k (1 \le k \le 4)$ 大小的子矩阵，将其中的值都赋为 $0$，代价为 $a_k$。问你最小的代价使得整个矩阵的值都为 $0$。
题解：
萌萌题。
看到只有 $4$ 行就想到可以状压 $dp$。
令 $dp_{i,mask}$ 表示考虑到底 $i$ 列，当前第 $i-3$ 至 $i-1$ 列的状态为 $msk$。
我们考虑从前往后赋值。$dp_i$ 能够转移到 $dp_{i+1}$ 当且仅当第 $i-3$ 列已经全部赋值为 $0$了，因为到后面就再也不可能赋值它了。
但这个转移有点恶心，具体的可以参照代码里的注释。
1 | using namespace std; |
本文迁移自洛谷原文。
题目大意：
给你一个长度为 $n$ 的字符串 $s$。
每一次操作，可以选择一个位置（不为最后一位），然后删除它和它后面一位，在原来的位置上填上他们的或。每次操作会使 $n-1$。
问你执行最多 $n-1$ 次操作后能得到多少不同的串。
题解：
根据套路，就可以把相同的数分成一段一段的。又因为是或，所以我们可以认为 $1$ 永远比 $0$ 强，就统计相邻两个 $1$ 之间 $0$ 的个数。（记第 $i$ 段为 $cnt_i$，有 $m$段）
考虑操作过程：
如果选择的是两个 $1$，那么段数会 $-1$，但由于反正间隔都是 $0$ 个 $0$了，我们就可以不用管了。（有问题，后面会提到）
反之，删除的肯定是一个 $0$，就当那一段的 $0$ 个数 $-1$。
然后我们就相当于：统计数组 $a$ 的个数，满足 $a_i \le cnt_i$ 了
吗？
不，这题不会这么简单，因为很显然会重复计算。
所以，我们考虑怎么去重：
前面推的时候，对于选择了两个 $1$ 的情况，很难自圆其说是不是？
我们对这一块重新考虑下。
令 $dp_i$ 表示考虑到 $cnt_i$ 时的方案数。
为了去重，当 $dp_i$ 由 $dp_k$ 转移过来的时候，需要满足对于所有的 $k+1 \le j \le i-1,cnt_j<cnt_i$，这样就限制了多次转移的情况，而且不会使答案遗漏。
处理 $k$ 的话，打个标记就好了。
最后用前缀和优化把复杂度从 $O(n^2)$ 降到 $O(n)$
Code:
1 | string s; |
我只是去摸鱼的。
总的来说机试要比去年难的多，大概CSP2019Day1的难度。
事实上这篇游记的目的大概就是介绍流程。
本文迁移自洛谷原文。
Warning：可能比官方题解复杂的多，思维难度估计要上紫，但推出来了能有很好的训练效果
$\color{white}\text{然后你们知道为啥 div2 rank1 的 YuezhengLing 最后才过D了吧}$
令 $x$ 为隐藏的数组。
这个方法的大体思路就是，通过两次全数组的询问，得到两个数的位置（$0$ 和最大的数），然后上传这两个位置。
我们考虑这么询问:
固定前两个数 $(1,2)$ 不动，询问 $(1,2,i)$，记得到的序列为 $a$。询问 $n-2$ 次。记最大的 $a_i$ 的下标 $i$ 为 $pos_1$。
然后固定 $(1,pos_1)$ 不动，询问 $(1,pos_1,i)$，记得到的序列为 $b$。询问 $n-2$ 次。记最大的 $b_i$ 的下标 $i$ 为 $pos_2$。
显然，$pos_1 \neq pos_2$，因为我们 $b$ 询问不会询问 $(1,pos_1,pos_1)$
然后我们来想，如何利用 $a$ 数组和 $b$ 数组，来推断出答案。
我赛时的注释：
1 | //now if both x[1] and x[2] isn't 0 this is okay |
我们要分类讨论（如何判断是哪一类待会儿讲）：
显然，对于这种情况，我们求得的 $pos_1$ 和 $pos_2$ 就可以做为答案上传。因为，如果 $x_1$ 和 $x_2$ 都不是 $0$ 或最大值的话，第一遍求得的 $pos_1$ 肯定是 $0$ 或 最大值。（如果想不明白的话，画个数轴看看就知道了）
然后第二遍询问，因为询问的东西带上了 $pos_1$，故得到的 $pos_2$ 一定是另外一个极值。（因为这样的话 $max-min$ 才会最大）
我们的 $pos_1$ 肯定是一个极值（排除 $x_1,x_2$ 均为极值的情况），然后就可以肯定 $(1,pos_1)$ 为两个极值，上传。
有可能 $x_1$ 是极值，所以我们需要用一次询问来特判这种情况。
询问$(1,pos_1,pos_2)$，返回值记为 $tmp$。
如果说，$tmp$ 大于任意 $a_i$ 的话，我们可以直接返回 $(1,2)$，感性理解容易。
通过不断的尝试，我发现此时询问 $(2,pos_1,pos_2)$ 可以有很大的用处：
我们令这次询问的返回值为 $rt$。
注意，一个是严格小于，另一个是小于等于。
这种情况对应了 $x_1$ 或 $x_2$ 为 $0$，因为：
$a_{pos_2}$ 查询的是 $(1,2,pos_2)$，$rt$ 查询的是 $(2,pos_1,pos_2)$
两者的区别就在于，一个是 $1$，一个是 $pos_1$。
然而，此时的 $rt$ 小于 $a_{pos_1}$，就说明，$x_1$ 会更往极端走一些。
然后到了这里，我们似乎发现了一个漏洞：$x_1$ 也许是最大值呀？
但这里我们之前已经排除这种情况了（$a$ 数组全部相同的情况），故排除。
但上述讨论都是基于 $x_2$ 不为 $0$ 的情况。保险起见，我们上传 $(1,2)$ 做为可能的答案。
通过比较 $a_pos1$ 和 $rt$ 查询的内容可以发现，在这种情况下，$x_2$ 和 $x_{pos_1}$ 中必然有一个是 $0$。应为此时的 $pos_2$ 也应该是向着极值发展的，然而改变后并没有使 $rt$ 和 $a_{pos_1}$ 变得不同，故 $x_2$ 和 $x_{pos_1}$ 为两个极值，上传 $(2,pos_1)$
同理，上传 $(2,pos_2)$
平凡情况，上传 $(pos_1,pos_2)$
次数：
询问次数为 $2n-3$ 或 $2n-2$ 次，符合要求。
code:
1 |
|
本文迁移自洛谷原文。
此题我们可以考虑费用流
我们考虑建出一张 $n+2$ 个点的图（本文字符串下标从 $1$ 开始）
首先对于 $s$ 的一个子串 $s_{l\dots r}$，如果它可以和一个权值为 $w$ 的串匹配上，那么就建立一条从 $l$ 个点出发，连向第 $r+1$ 个点，流量为1，费用为 $w$ 的边；
然后，我们对于所有的 $1 \le i \le n+1$，建立一条从 $i$ 号点 出发，连向 $i+1$ 号点，流量为 $x$ （如题目所给，一个字符能被覆盖的最大次数），费用为0。
然后以 $1$ 号点为源点，$n+2$ 号点为汇点，跑最大费用最大流就可以了。
然后解释一下为什么这么建图是正确的：
建立从 $l$ 到 $r$，流量为 $1$ 的边很好理解，就是为了满足题目中所给的“每个串在每个位置只能匹配一次”的条件；
那么为什么建立从 $i$ 到 $i+1$，流量为 $x$ 的边就可以满足题目中要求“一个字符能被覆盖的最大次数为 $x$ ”的条件呢？
我们考虑一下，把那 $n+1$ 个点平铺在一个坐标轴上，这张流量网络大概长成什么样：（样例，边的方向都是从前往后，绿色为费用，蓝色为流量）
然后我们再尝试着把这张图拍扁。
如果对于一个点，它对应的字符出现了多于 $x$ 次，会出现什么情况？
它上面那些“高速公路”上的流量，最终一定会都流到“主路”上！
然而，如果他对应了多余 $x$ 次，那么它上方的“高速公路”上的流量就会大于 $x$，就超过了主路上相邻两点之间流量 $\le x$ 的限制。
那么为什么要建立这看似多余的第 $n+2$ 个节点呢？
其实很简单，万一有很多高速公路在 $n+1$ 号节点上才下来，这就不会受到主路的流量限制了啊！我们再连一条从 $n+1$ 号点通往 $n+2$ 号点的边，流量为 $x$，就正好处理了这种特殊情况。
Code:
1 |
|
本文迁移自洛谷原文。
晚上有点累就没打 Edu，感觉亏大本了。
首先，我们需要一个性质：
合法的图中不存在两个有着公共边的环
证明：
设环 $a$ 中不与环 $b$ 公用的部分的异或值为 $x$，环 $b$ 中不与环 $a$ 公用的部分的异或值为 $y$，环 $a$ 与 $b$ 公共部分的异或值为 $z$
那么，有:
$x \oplus z = 1$
$y \oplus z = 1$
$x \oplus y = 1$
(对应了环 $a$，环 $b$ 和新构成的环 $c$，其中 $\oplus$ 表示异或)
将这三个式子一起异或起来，就可以得到 $0 = 1$，显然不成立，故不会有两个有着公共边的环。
所以说，每次询问，就相当于询问，加上这条边后，会不会生成一个新环，且这个环与已经存在的环有着公共边。
还有一个性质：
如果我们把所有边离线下来，按照顺序加边，如果当前这条边不会生成一个环，那么它一定是可以加入的。
证明：
因为只有加上这条边后，会生成一个新环，且这个环与已经存在的环有着公共边，才会不能加，故在不生成环的情况下，是可以随便加边的。（也可以感性理解下）
所以我们就可以先按照第二个性质建出一棵树来，然后对于非树边一个一个判断。
于是，我们对于每一条可以加入的非树边，就对 $u_i$ 到 $v_i$ 的简单路径上的所有边权加一。在询问的时候，看 $u_i$ 到 $v_i$ 的简单路径上所有边的边权和是否为 0 即可。
看到是对树上的路径操作就很容易的想到了树剖。
至于题目要求是对边权进行加，我们可以把边权转换到点上：点 $i$ 的权值为连接 $i$ 与 $i$ 父亲的边的权值。
然后就可以码码码了。
我想练练手，所以代码里判断异或和就单独写了个倍增，没有再在树剖里搞，导致巨大多常数，1497ms
Code: 5130 Byte
1 |
|
本文迁移自洛谷原文。
这道题的一血，纪念一下
观察一个数什么时候能对答案产生贡献。
从前往后数，如果在第 $i$ 个数之前，有 $j$ 个数被删除了，那么这个数现在的位置变成了 $i-j$，故当且仅当 $i-j = a_i$ 的时候会对答案产生贡献。
所以我们可以列出 dp 方程：
令 $dp_{i,j}$ 表示考虑到从前往后第 $i$ 个位置，在它之前已经删除了 $j$ 个数时，最大的答案。
可以得到如下的转移方程：
1 | dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(bool)(a[i]+j==i)); //保留这个数 |
完事了~
Code:
1 |
|
本文迁移自洛谷原文。
赛后写题解补教训。
场上数组开小本机 AC，但开了 O2 就会 RE，最终爆零。
洛谷上测由于数组开小导致访问不到、死递归 MLE，我还以为还是开大了。
小心，小心，再小心。
我们尝试建立一棵线段树。
线段树的每一个叶子节点是一行，每一个节点是一段行。
每一个节点存上两个东西：
两个并查集，记录这个节点所对应的行区间的最上面一行和最下面一行的状态（后面会讲到）
这个区间内部两种颜色的连通块的个数
对于单独的每一行，我们搞一个并查集：如果在这一行中，$i\dots j$ 的颜色相同，那么我们把 $i\dots j$ 都放到同一个集合中。用最小表示法，这个集合的代表就是最小的元素 $i$。
我们考虑合并两个行区间。
显然，新的行区间的上并查集就是左儿子的上并查集，新区间的下并查集就是右儿子的下并查集。
考虑左儿子的下并查集与右儿子的上并查集结合所带来的贡献。
首先令新节点的颜色 $c$ 的连通块数等于其两个儿子的该颜色的连通块数之和。
然后枚举，对于第 $i$ 列，如果 $gird_{md,i} = gird_{md+1,i}$，那么显然这两个在同一个连通块中，要将该颜色的数量-1。
然后写个标准的线段树就完事了~
总时间复杂度 O(能过) $O(n^2+mnlogn)$
Code:
1 |
|