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日

[Fortuna OJ]Aug 10th – Group A 解题报告

A – 数学题

这道题二次函数的暴力分有 60 分,正解来自于论文。

这道题的主要是利用了一个结论,并且运用了辗转相除法的一种思想来对问题进行化简。首先,我们把向量调整至同向,且使\(|\vec{a}| < |\vec{b}|\),然后再来推导一个结论:

结论   对于\(\vec{a}, \vec{b}\),如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\),那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。

这个结论的证明参见《欧几里得算法的应用》。所以,我们就可以大概知道,我们可以将较长的向量分解:\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道,这道题可以笑掉这个\(k \vec{a}\),所以就可以用辗转相除法的套路进行处理。具体见代码:

继续阅读[Fortuna OJ]Aug 10th – Group A 解题报告

Codeforces Round #549 (Div. 2) 解题报告 (CF1143)

E – Lynyrd Skynyrd

题目大意

给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\),处理\(q\)个询问:在数组的字段\([l,r]\)内是否存在排列的环形偏移。

解法

考虑正向扫描,处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置,并同时更新自己所在的位置供下一次循环进行使用:

继续阅读Codeforces Round #549 (Div. 2) 解题报告 (CF1143)