Codeforces Round 959 sponsored by NEAR

發表於 更新於 分類於 ， Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘
F(欧拉回路,树,连通块,度)G(DP)H()

https://codeforces.com/contest/1994

F Stardew Valley

n点m边，边有颜色0/1

要求找方案 从某点开始 经过所有1的边回到你选定的点，其中每个边最多经过一次，颜色为1的边必须经过1颜色为0的边可以经过1次

保证任意两点之间有纯1的路径

输出具体方案 或 不可行-1

n,m 5e5

2s

256mb

我的思路

核心应该是欧拉回路，但是不知道如何选0边

题解

相成先全选，然后删除一些 颜色0的边，让剩下的点的度都是偶数（注意到保证任意两点之间有纯1的路径，所以如果这样能有方案，则一定是连通的）

计算每个点的度

只关心可以删的边，对于可以删的边考虑每个连通块

对于一个连通块中涉及的顶点的度之和 如果为奇，注意到删除的过程不会改变涉及的点的度之和，所以这一定无方案。

否则 一定存在方案！！！？？？

首先随便选根，dfs，只留它的生成树，从叶子向上考虑，如果一个点的度是奇数，则删掉它和它的父节点的边，这样除了根 所有点都能变成偶度，再根据删除过程不会改变涉及的点的度之和，所以根也是偶度。

最后跑欧拉回路就好了

G Minecraft

给定 a[n], s

找 x使得 $\sum (a_i\oplus x) = s$, 其中运算符号为异或

$a_i,s$ 足够长, 用二进制字符串表示

所有字符串长度和 <= 2e6

2s

512mb

我的思路

对于给定的bit, x选0和选1,其实就是 对于bit位 a_i的个数

例如 a_i 中 ，二进制 100 位有a个是1, b个是0, $a\le b$

那么 s -= 4(100) * a, 变成 考虑是否选 $(b-a)*4(100)$

问题是这样 低位可能比高位大, 例如

1
2
3 1
7 9

高位差是4,低位差是8，但是低位影响了更高位

另一个思路是 考虑2的倍数

如果 n是奇数, 那么 a_i最低位 0和1的个数一个奇一个偶，直接从低到高位 对s用奇偶判断就能做了

但是如果 n是偶数，这个方法会失效，一个办法是除以2,但是 就会导致奇偶不平衡

1
2
3
4
         去掉最小   除以2
3 4 2 => 0 0 0 => 0 0 0
5 4 6    2 0 4    1 0 2

也尝试了 从高向下，但是高位选择后依然有上面的 低位可能超过高位的 问题

然后 对于个数来说 虽然值 对应的长度不算长 log级别，但是这如果把剩余看成状态的话 那状态数又变成 2^长度 又很多

题解

hint1: Think of the most stupid solution you can do

hint2: Do memorization and some cuts

hint3: Done!

啥玩意儿 暴搜+记忆化+剪枝

从低位到高位

rec(i,sum)= 低i位选好, 高位剩余是sum, 低i位和s匹配

令 c[i] 表示 a中第i个bit是1的个数

那么 转移可以从 (i,sum)到（注意要和目标s的对应位相同

$(i+1,\lfloor \frac{sum+c_i}{2} \rfloor)$

$(i+1,\lfloor \frac{sum+(n-c_i)}{2} \rfloor)$

其实就是对应两种选法

注意到 $sum \le n$, 所以 总状态数少于 $n k$个 ！！？？

具体解直接靠反向的 来源链就好了。

总结

https://codeforces.com/blog/entry/131666

F: 评分2500

这个从删的角度，“单独”考虑连通块是有点神奇了，因为它这里的感觉上是“连着的”，但是只考虑 可删边，它的确是多个连通块，这里把全连通看成多个连通块着实没想到！

欧拉回路还是做少了

G: 评分2600

神奇啊，真就暴力一下

其实从事后诸葛亮的角度来讲，的确G比F简单很多，没啥我不熟悉的知识，应该要自己想出来的。