11.08

感觉写的有点意识流。

A.BZOJ 5176

把 \(-1/1\) 转化为 \(0/1\)，问题就变为一个格子和它相邻四个格子异或和为 \(0\)。
容易发现第一行的状态确定了，整个网格的状态就确定了。
对于给定的 \(m\) 个格子，其实就是解 \(m\) 个异或方程，但是我们还需要让我们的状态合法，而合法的等价条件为最后一行每个格子与它相邻四(个格子的异或和为零，最后问题就是求 \(n+m\) 个异或方程解的个数，设自由元个数为 \(x\)，那么最后答案就是 \(2^x\)。

B.P3973 [TJOI2015] 线性代数

简单题，先把 \(B\) 的对角线减去 \(C\)，那么问题就是就是一个矩阵选若干行及其对应的列使相交和最大。
这个显然不能 \(dp\)，于是考虑优化退火，从删数的角度考虑，然后发现这不就是最大权闭合子图吗。

C.P5979 [PA2014] Druzyny

拿铁说这个东西很套路，我也觉得套路确实有点深。
赛时想着类似求值域连续段的做法：线段树+单调栈上二分，最后发现有的位置在作贡献与不作贡献之间反复横跳，遂寄。

从优化 \(O(n^2)\) 的 \(dp\) 入手，很容易发现这个从前面可以转移的位置断断续续的，于是考虑 \(cdp\) 分治下去，开一颗线段树，每次从左边把合法状态扔进去，右边区间查询进行转移。

A.Andryusha and Nervous Barriers

原来我开场 30min 就秒掉了 CF*2700（指思路）。
然后对着这个寻找最大的 \(j\) 使得 \(j<i\land l_j\le p\land r_j\ge p\land s_j+u_j\ge u_i\) 的问题，我说我超四维偏序，不太会写怎么办啊，不太能过怎么办啊，跟你拼了！！！
写了一整场没调出来。

一个球如果被一个板截住了，那么它后面的过程都是确定的了，也就是说我们只需要对每个球找出它下方第一个能借住它的板。
设板 \(i\) 生成的两个球下方第一个能借住它的板为 \(pre_{i,0/1}\)，那么 \(f_i=f_{pre_{i,0}}+f_{pre_{i,1}}\)，初始 \(f_0=1\)。

对一个球找出下方第一个能接住它的板，这个问题可以扫描线，开一棵以板的编号为下标的线段树，每次线段树上二分找出满足 \(j<i\land s_j+u_j\ge u_i\) 的最大的 \(j\) 即可。

B.钙铁锌硒维生素

把时间放在更有意义的事情上。

C.Bear and Chase

先用 floyd 算法预处理出任意两点之间的距离。时间复杂度 \(\mathcal{O}(n^3)\)。

记两次查询的节点分别为 \(a\), \(b\)，两次查询得到的结果分别为 \(d_1, d_2\)。

• 枚举 \(a\)。计算出第一步选 \(a\) 时的答案。因为我们要求最优策略下的答案，所以对所有 \(a\) 的情况取最大值即可。
  • 枚举 \(d_1\)。考虑所有距离 \(a\) 为 \(d_1\) 的节点，记为点集 \(U = \{u | \mathrm{dis}(u, a) = d_1\}\)。则得到回答 "\(d_1\)" 的概率是 \(\frac{|U|}{n}\)。求出 \(d_1\) 的答案后，乘以这个概率，累加起来，就是当前 \(a\) 的答案了。
    • 预处理出第二天罪犯来到 \(v\) 的概率 \(p(v)\)。具体来说，\(p(v) = \sum_{u\in U} \frac{1}{|U|}\cdot \frac{1}{\mathrm{deg(u)}} \cdot[(u, v)\in E]\)。把所有 \(p(v)\neq 0\) 的点（即与 \(U\) 中至少一个点有连边的点）存起来，记为集合 \(V = \{v | p(v)\neq 0\}\)。
    • 现在已经得到了回答 \(d_1\)。考虑我们接下来的最优策略，是两种情况的较大者：要么在 \(U\) 中随便猜一个点，并结束游戏，获胜的概率是 \(\frac{1}{|U|}\)。要么继续询问。
    • 如果继续询问。枚举接下来要询问的点 \(b\)。那这种情况下，获胜的概率就是所有 \(b\) 的答案的最大值。对每个 \(b\)：
      • 枚举得到的回答 \(d_2\)。考虑距离 \(b\) 为 \(d_2\) 的点，记为集合 \(W = \{w | \mathrm{dis}(w, b) = d_2\}\)。在知道了 \(d_2\) 后，我们有唯一的最优策略，且获胜的概率是 \(\frac{\max_{v \in (V \cap W)}\{p(v)\}}{\sum_{v\in(V \cap W)} p(v)}\)。同时，\(d_2\) 发生的概率是 \(\sum_{v\in(V \cap W)} p(v)\)。所以 \(b\) 的答案是：\(\sum_{d_2} \frac{\max_{v \in (V \cap W)}\{p(v)\}}{\sum_{v\in(V \cap W)} p(v)}\times (\sum_{v\in(V \cap W)} p(v)) = \max_{v \in (V \cap W)}\{p(v)\}\)。所以我们只需要在枚举 \(d_2\) 之前，先枚举一遍 \(v\)，就能预处理出每个 \(d_2\) 的答案。然后再扫描所有 \(d_2\)，把这些答案加起来。

上述的做法看起来是四重循环。但对于同一个 \(a\)，在所有 \(d_1\) 下 \(U\) 集合的大小之和为 \(n\)。\(V\) 集合里的点与 \(a\) 的距离要么是 \(d_1 + 1\)，要么是 \(d_1 - 1\)，所以 \(V\) 集合的大小之和也是 \(\mathcal{O}(n)\) 的。发现我们真正枚举的只有 \(a, b, V\)，时间复杂度是 \(\mathcal{O}(n^3)\) 的。