Codeforces 题目选做 III

· · 个人记录

补两个月前的笔记。

Anti-theft Road Planning

真 试错 + Brainstorm。显然是要给每个位置赋个权值 a_{ij}，使得 w((i,j),(p,q))=a_{ij}\operatorname{xor}a_{pq}。发现题目要求的边权和卡得很死。

考虑一维情况怎么构造，经过一些试验发现格雷码的递归构造方法能达到理论下界（最小化 1 在最高位的个数，然后递归下去）。因此考虑在二维上也用类似的递归，把整个区域分为 4 块，每块递归，并适当反转每块内部，使得接口处 xor 最小。

具体构造可见 https://codeforc.es/problemset/submission/1673/155417304

Power or Xor?

根据套路，先枚举一段连续的 power，算它对答案的贡献。可以发现，power 超过了 20 个，它本身的值 mod 2^{1048576} 就是 0 了，所以这里暴力枚举所有较短（长度 \le 20）的区间就行。

接着，要算这一段对答案贡献的奇偶性。可以发现就是算 \sum_{i=0}^m \binom ni 这种东西的奇偶性，通过打表发现与 \binom{n-1}{i-1} 的奇偶性相同。

Cut

注意到如果 [l,r] 符合要求，[a,b]\subset [l,r] 也符合要求，所以每次直接贪心选跳得最远的即可，这个过程倍增维护。

接着要求每个左端点最远能到哪里，可以双指针。

Cut and Stick

如果整个区间中出现次数最多的数出现也不超过一半，答案就是 1；否则，设其出现次数为 x，答案为 x-(r-l+1-x)。

如果存在这样的 x，采用随机化策略容易将其找到，两个 log。

还有一种比较高明，而且能拓展到任意 k（出现至少 A=(r-l+1)/k 次）的单 log 做法：注意到从小到大排序后，x 一定是区间中位数，故判断其是否合法即可。拓展方法就是只需要判段第 1,1+A,1+2A,\dots 小的数是否合法（显然 x 一定在它们中出现）。

Baby Ehab's Hyper Apartment

看到 9n,2n 容易想到分别表示二分和 two-pointers。

第一步：找出一条哈密顿链。考虑使用类似插入排序的方法，二分答案，找到最靠右的 p\to x 的边，并把 x 插在 p 之后。这样不一定找到的是最靠右的，但可以发现得到的序列一定合法（感性理解一下吧。。。）这一步也可以换成归并排序。

然后考虑从后往前（这里要试错）双指针，求出当前后缀最远的返祖边。

Omkar and Forest

注意到如果一个位置不是 0，它的值就是确定的。

故答案是 2^{cnt\#}，如果整个地图全是 \#，答案要减一。

Omkar and Akmar

终态具有以下性质：

由第二点可知后手必胜，且无论怎么放都是最优策略。

枚举最终有 i 个空格，剩下 n-i 个位置，有两种交错 AB 的方式；在 n-i 个位置排成的环中间插进空格有 \binom{n-i}i 种方式；把环标号有 n 种方式；把 AB 的行动圆排列有 (n-i-1)! 种方式。故答案是

2n\sum_{i\equiv n\pmod 2} \binom{n-i}i(n-i-1)!

Phoenix and Socks

首先把已经配对的删掉。现在剩下的有同色同左右，异色异左右，异色同左右。每一对最后一种需要 2 的代价，其它都只要 1。

不妨假设左袜子数量大于右袜子数量，右袜子肯定尽量去配左边数量是奇数的袜子，把它们全配成偶数。配得越多 2 越少。

Phoenix and Computers

从前往后 dp，只需要记录 i,i-1 被打开的时刻（还是相对顺序？有点记不清了！）就可以做到 O(n^3)。

还有一个类似于 ZJOI2012 波浪那题的做法（维护一些有序但不确定段间距离的全部开启的连续段），只用记录段数和总电脑数，可以做到 O(n^2)。

Phoenix and Bits

不妨假设操作都对 trie 的子树进行。否则拆开成 log 个。

xor 操作，对于低位的影响可以直接在 trie 上打标记，对于高位改变就暴力 trie 合并。

and or 更暴力，找到所有会产生合并的位（可以 pushup 时顺便更新，xor 不影响这个），然后内部暴力合并，外部也暴力合并。

复杂度是 2log。

Colors and Intervals

这题有 educational intuition。

考虑递归，每次让 k 减小 1。设 m=ceil(n/(k-1))，找出第二次出现最靠左的 m 个颜色，直接取出这 m 个颜色出现的前两个位置作为答案，然后 n 减小 m、k 减小 1，递归。注意到其它颜色出现次数不小于 k-1 了，而且 ceil((n-m)/(k-2))\le m（右半部分放缩掉 ceil，然后通分化简即得），故递归是合法的。

Telepanting

为啥才 *2200 啊？？？做了至少一个多小时吧。。。

注意到如果走到 i 传送门了，之前的传送门必须全是打开状态。

设 f(i) 表示在之前的传送门全都打开的前提下，从 l_i 走到 r_i 需要的时间，则中途每个传送门都会被走过一遍。有 f(i)=r_i-l_i+\sum_{r_j\in [l_i,r_i]} f(j)。答案就是 \sum_{b_i=1} f(i)+r_n。

Two Houses

由兰道定理，仅从入度或出度就可以恢复出每个强连通分量，故只需要 0 次询问。

Christmas Game

阶梯博弈模板，维护模 2k 意义下每种距离点权异或和即可。