T1.Adore

描述:

原题:

小 w 偶然间⻅到了一个 DAG。
这个 DAG 有 m 层,第一层只有一个源点,最后一层只有一个汇点,剩下的每一层都有 k 个
节点。
现在小 w 每次可以取反第 i(1 < i < n − 1) 层和第 i + 1 层之间的连边。也就是把原本从
(i, k 1 ) 连到 (i + 1, k 2 ) 的边,变成从 (i, k 2 ) 连到 (i + 1, k 1 )。
请问他有多少种取反的方案,把从源点到汇点的路径数变成偶数条?
答案对 998244353 取模。

输入格式:
一行两个整数 m, k。
接下来 m − 1 行, 第一行和最后一行有 k 个整数 0 或 1,剩下每行有 k 2 个整数 0 或 1,第
(j − 1) × k + t 个整数表示 (i, j) 到 (i + 1, t) 有没有边。

输出格式:
一行一个整数表示答案。

数据规模与约定:
20% 的数据满足 $m ≤ 10, k ≤ 2$
40% 的数据满足 $m ≤ 10^3 , k ≤ 2$
60% 的数据满足 $m ≤ 10^3 , k ≤ 5$
100% 的数据满足 $4 ≤ m ≤ 10^4 , k ≤ 10$
一行一个整数表示答案。

思路:

由于每层只有k(k<=10)个节点,而且只需要求满足某种奇偶性的解的个数。我们可以用二进制保存每一层的状态。接下来进行状态压缩DP。

注意以下的问题:

1.边的表示?

为了达到更高的速度,边可以用邻接矩阵表示,而这个邻接矩阵又是由二进制构成的,因此可以用位运算加速连通性的计算。

比如:
$$
\begin{bmatrix}
1 & 1 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{bmatrix}
$$
这个矩阵表示,每一列对应的左侧节点与每一行对应的右侧节点联通,当且仅当这一列这一行的元素为1。

而每一层的状态我们又可以用一个k维向量表示,

比如:
$$
\begin{bmatrix}
1 \\
0 \\
1
\end{bmatrix}
$$
这个向量表示,从起点到这一层的1,3个节点有奇数中走法,第2个节点有偶数种走法。这样,如果我们将这连个矩阵相乘:
$$
\begin{bmatrix}
1 & 1 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{bmatrix} \times
\begin{bmatrix}
1 \\
0 \\
1
\end{bmatrix} =
\begin{bmatrix}
1 \\
0 \\
2
\end{bmatrix} =
\begin{bmatrix}
1 \\
0 \\
0
\end{bmatrix}(mod2)
$$
然而,由于我们用一个int型数就可以表示矩阵的一行,我们就可以在O(k)的时间复杂度内完成这个矩阵乘法。具体的实现是:将矩阵的每个行向量与当前层的k维向量按位与,取答案中1的个数。很快,对不对?不够快。

注意到上面的式子中出现了取1的个数操作。如果这个操作仅仅使用x=x&(x-1)这样的操作来读取的话,恭喜你,时间复杂度不幸地变成了$O(k^2)$。如何才能更快求1的个数呢?我们以空间换时间,结合本博客中另一篇有关位运算的"位运算那些令人咋舌的操作"文章,大家一定可以找到更快速的方法。我最终采用的算法时间复杂度约为$O(mk2^k)$

2.思考的复杂度

由于这道题的内容及我所选择的做法,我的程序频繁地涉及位运算相关的代码。而位运算代码的编写由略为困难。如何在代码执行高效的基础上减少位运算的思考复杂度,已知是一个值得权衡的问题。

3.时间的复杂度
使用的第一个问题所提到的架构,时间复杂度已经得到了保证。谁知当我采用x=x&(x-1)取得答案中1的个数时,却发生了60分TLE惨案...。在考场上我最初的邻接矩阵甚至没有用到位运算,速度更慢,计算时间复杂度为$O(mk^22^k)$,有对于后40分有危险,为了确保万无一失我才改成了位运算,谁知....还是TLE,而且T了60分。数据实在是没有梯度,这种出题人该裱该表。


T2.Confess

描述:

原题:

小 w 隐藏的心绪已经难以再隐藏下去了。
小 w 有 n + 1(保证 n 为偶数) 个心绪,每个都包含了 [1, 2n] 的一个大小为 n 的子集。
现在他要找到隐藏的任意两个心绪,使得他们的交大于等于n/2。

输入格式:
一行一个整数 n。
接下来每行一个⻓度为 k 的字符串,该字符串是一个 64 进制表示,ASCII 码为 x 的字符代
表着 x − 33,所有字符在 33 到 33 + 63 之间。
转为二进制表示有 6k 位,它的前 2n 个字符就是读入的集合,第 i 位为 1 表示这个集合包
含 i,为 0 表示不包含。

输出格式:
一行两个不同的整数表示两个集合的编号。
如果无解输出”NO Solution”。

数据规模与约定:
对于 20% 的数据满足 $n ≤ 100$
对于 50% 的数据满足 $n ≤ 1 \times 10^3$
对于 100% 的数据满足 $n ≤ 6 \times 10^3 $

思路:

我首先想到的是随机化算法。因为我只想着去骗分了。后来发现其实这就是正解。为什么随机化算法骗分是可行的呢?我们来考虑任意两个集合的交集大于等于n/2的概率:

设这两个集合为[1,2n]中的n个整数组成的集合,设P(i)为它们交集大小为i的概率,那么:
$$
P(i)=\frac{C_{2n}^{i}C_{2n-i}^{n-i}C_{n}^{n-i}}{C_{2n}^{n}C_{2n}^{n}}
$$
其中分数线上方第一个C表示从2n个元素里选出i个作为它们的交,后两个表示从剩下的里面选出不重复的n-i和n-i个分别作为两个集合的元素。而我们要求的是:
$$
P=\sum\limits_{i=n/2}^{n}{P(i)}
$$
随手用计算机一算,这个结果还是蛮大的。

假设,P=0.01(是不是非常小),那么我们只需要随机选1000组集合,它们都没有大于等于n/2的交集的概率为0.00004,显然是符合要求的。因此,我们可以大胆地骗分了。

优化:

对于暴力求交集,我们是可以优化的。我们不需要一个一个元素地比较,而可以保存在二进制数里用位运算求交集(即按位与)。同时又可以结合"位运算那些令人咋舌的操作"中介绍的方法,快速求交集大小。这种方法在图像处理等现实应用中十分有效,即"汉明距离"的快速求法。结合这种优化,我们可以在1s内求大约10倍于普通做法的交集次数,对大数据范围内的求解帮助还是很大的。


T3.Repulsed

描述:

原题

小 w 心里的火焰就要被熄灭了。
简便起⻅,假设小 w 的内心是一棵 n − 1 条边,n 个节点的树。
现在你要在每个节点里放一些个灭火器,每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多 k 条边远的灭火器,每个灭火器最多能分配给 s 个节
点。
至少要多少个灭火器才能让小 w 彻底死心呢?

输入格式
第一行三个整数 n, s, k。
接下来 n − 1 行每行两个整数表示一条边。

输出格式
一行一个整数表示答案

数据规模与约定
对于 20% 的数据满足 $n ≤ 100, k ≤ 2$
对于另外 20% 的数据满足 $k = 1$
对于另外 20% 的数据满足 $s = 1$
对于 100% 的数据满足$ n ≤ 10^5 , k ≤ 20, s ≤ 10^9 $

思路:

当初没有想出来,也没有时间想了,于是看数据范围骗了40分。

实际上的思路是这样的:

设G(x,i)表示x节点及其子树中还没有被灭的火的个数。

设F(x,i)表示x节点及其子树中多余的灭火器能灭的火的个数。

策略1:对于每一个火,我们尽量在靠近树根的地方灭掉。

策略2:对于每一个x及其子树中多余的灭火器和火,我们在两者距离为k或k-1时让它们相互泯灭。

按照这两个策略,我们就可以快捷地写出代码。。。原来比骗分还简单。