Codeforces 1174D:Ehab and the Expected XOR Problem 题解

主要思路

这道题还蛮妙的，自己比较顺利的思考出来了。

考虑设置前缀异或和\(\{ S_i \}\)，根据异或按位处理的性质，显然对于所有的\(S_i\)都会小于\(2^n\)。最后，我们可以把限制变成：

不存在两个相同的前缀和。
不存在一对前缀和，其异或值为\(x\)。

针对\(x\)的大小关系，我们可以分成两种情况：

\(x \geq 2^n\)，不存在一对\((S_i, S_j)\)的异或为\(x\)，因为存在更高的位并不会被消除。
\(x < 2^n\)，我们发现每选择一个数作为前缀和，整个\(2^n\)中就会少一个对应的可以被选择的数。所以，我们每次选一个作为\(S_i\)的数时，都要把\(S_i xor \ x\)打标记。

结合一下就可以了。

继续阅读Codeforces 1174D:Ehab and the Expected XOR Problem 题解

「杂题集」- 2019年9月25日

[POI2008]BLO

一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：

此点延伸出去的点对。
连通块之间的点对。
本身就无法互通的点对。

第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。

综合起来就是，对于点\(u\)：

\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]

继续阅读「杂题集」- 2019年9月25日