• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

题解

admin

11月 28, 2021

场上题目看错两次,day2 成功爆炸 /ll

为什么我总是拿不到自己该拿的分呢?

本文下标从 1 开始

算法 1

我会容斥!

先把问题转化成统计不存在一个合法位置的方案数。

接着统计有钦定 (k) 个合法的,其他随便的方案数。其容斥系数为 ((-1)^k)

在一次机器人的操作后,所有输入的数在经过机器人在操作后的输出都可以表示成 (0)(1)(x)(1-x) 的形式((x) 是这个位置上输入的数)

考虑一个纸带:对于一个被钦定的每一个位置,要求输入经过这个机器人操作之后一定等于输出。仍然把输出表示成输入的形式,只不过这个输出可以以多种方式被输入表达。

对于每一个位置分类讨论:

  1. 如果这个位置上表示成的结果 既有 0 又有 1既有 x 又有 1-x:输入输出都为空。方案数为 1。
  2. 如果不满足条件 (1),这个位置上表示成的结果 有 0 或 1有 x 或 1-x:输入输出都为空,否则输入输出就被固定了。方案数为 2。
  3. 条件 1,2 都不满足:对于每一个输入都对应一个唯一的输出,方案数为 3。

这个纸带上每一个位置就是独立的了,最后把每个位置的答案乘起来即可。

注意机器人爆炸的情况。

时间复杂度 (Theta(n^22^nm)),期望得分 (20)

code

算法 2

我会优化算法 1!

对于第 (i) 个机器人,考虑实际进行修改了的位置只有 R 的个数个(设为 (c_i))。

考虑枚举最后一个钦定的位置在哪里(设为 (r))。这样就可以知道哪些机器人是爆炸的了:有且仅有 (c_i > n – r) 的爆炸了。

然后对于前 (r) 个位置 (m DP)。状压记录前面的元素中哪些元素被钦定了。钦定了一个位置就给答案乘上 (-1)。在 (m DP) 的过程中,做到第 (i) 个数就把第 (i) 个位置的贡献(即输入输出方案数)统计掉。

但我们发现并不是所有元素都需要记录下来的:只用记录与当前位置距离不超过 (n – r) 的和与当前位置距离超过 (n-r) 的位置中有没有 (1) 即可。

最后再处理一下位置超过 (r) 的元素即可。

时间复杂度 (Theta(n^2m2^{n/2})),期望得分 (48)

code

算法 3

我会 bitset!

发现我们统计一个位置的贡献的时候,只有 是否有... 有用。所以考虑用 (m bitset) 同时处理一堆纸条是否有 0,1,x 和 1-x

这样复杂度就降到了 (Theta(frac{n^2m2^{n/2}}{omega})),常数巨大。但是还可以优化。

其实我们要求的是类似于一个子集中的 (m bitset) 的子集并,这个东西仍然可以优化,就是类似于 f[x] = f[x & -x] | f[x ^ (x & -x)]

时间复杂度 (Theta(frac{nm2^{n/2}}{omega})),期望得分 (100)

code

感觉讲的有些抽象,不过相信大家想到算法2 之后就会做了。

算法 4

考虑换个维度思考,对于每一个纸条,考虑他对哪些集合的贡献是 (1),哪些集合的贡献是 (3),算出来这两个就可以算出哪些集合贡献为 (2)

问题基本转化成了这样:(n) 个元素被划分为 (4) 个集合 (S_0,S_1,S_2,S_3),要将满足 [有 (S_0)(S_1) 中的元素] 或 [有 (S_2)(S_3) 中的元素] 的集合权值 +1,最后求每一个集合的权值和。这个东西可以用容斥解决(转换成多个对 (T_i) 的所有子集 (S) 权值增加 (W_i)

感觉我讲不太清楚。。。。。

时间复杂度 (Theta(n^2 (m + 2^{n / 2})))。期望得分 (100)

code


祝大家学习愉快!

发表评论

您的电子邮箱地址不会被公开。