Test18 contest20201025
A reversal
题意
给定一个长为 $2n$ 的 01 串 $s$，请将其两两配对，形成 $n$ 个区间，使得反转每个区间的 01 后变为全 $0$ 串。
题解
暴力 40pts
暴力枚举所有配对的可能，答案为 $ans\times (n!)$。
复杂度 $O(2^nn!)$。
正解 100pts
考虑可行解的条件，即 0 的覆盖厚度为偶数，1 的覆盖厚度为奇数。
还有一个很重要的 observation，所有方案中，每个点作为区间左端点还是区间右端点是固定的。于是接下来就简单了。我们先考虑如何确定左端点和右端点。
由于 $i$ 后面的左右端点安排并不会影响 $i$ 的覆盖情况，于是我们扫一遍就可以知道。假如目前在没有决定的情况下 $i$ 的覆盖厚度同奇偶，那么 $i$ 为右端点；否则为左端点。
还有一个需要注意的，假如 $s_1=0$ 或者 $s_{2n}=0$，那么答案一定是 $0$。假设最终 $2n+1$ 的覆盖厚度不为 $0$，答案也一定是 $0$。
然后计算统计答案。每一个右端点可以匹配前面任意一个未被匹配的左端点，即此时尚未决定的情况下的覆盖厚度。
1 |
|
B clique
题意
将一个无向图点集划分为两个子集，使得两个子点集都构成团。设两个点集大小为 $n_0,n_1$，最小化 $\frac{n_0(n_0-1)+n_1(n_1-1)}{2}$。
$n\le 2000$。
题解
暴力 30pts
枚举每个点属于那个点集，然后判断一下即可。
$O(n^22^n)$。
正解 100pts
非常显然两个子集的点数差越小越好。
团一般可以去思考一下补图。这道题中补图的可行方案为划分成两个独立集，即二分图。题中要求的即二分图的最优染色方案使得两色差最小。
我们设这个二分图化为很多的联通分支。每个连通分支内分为两部是固定的。于是我们对于所有联通分支背包一下即可。
1 | namespace subtaskac { |
C chain
题意
一个 $n\times n$ 白色棋盘格，初始 $m$ 个格子为黑色。假设 $(x,y)$ 和 $(y,z)$ 都为黑，那么 $(z,x)$ 会变黑。问最终由多少个黑格子。
$n, m\le 10^5$
题解
暴力 20~30pts
就暴力模拟即可。
正解 100pts
首先可以转化为图论问题。$n$ 个点 $m$ 条边的有向图，若存在 $x\to y\to z$，则有 $z\to x$，问最终边数。
然后又很烦的 observation。然后可以发现，这张图要么是二分图，要么是三分图，要么是三元环，要么是完全图。
对于每一个连通分支，如果是二分图，则答案为边数；若是三分图，则答案为 $tot_xtot_y+tot_ytot_z+tot_ztot_x$；若是其他情况，答案为点数的平方。于是我们做一下有向图三分图染色即可。
主要难点在于这个 observation。
1 |
|