Petrozavodsk Winter 2015. Day 9. Michael Tikhomirov Contest 1 题意：有 $n$ 个数 $h_1,h_2,\dots,h_n$ 。你想让这些数非递减，也就是对于任意 $i$ ，都有 $h_i \le h_{i+1}$ 。有 $m$ 个操作，第 $i$ 个操作可以选择一个长度为 $l_i$ 的区间，都加上 $t_i$ ，代价为 $c_i$ 。最后每个数可以是负数，求出最小代价。
$1 \le n, m \le 200, 0 \le h_i \le 10^6, 1 \le c_i \le 10^6, 1 \le l_i \le n, t_i \in {-1, 1}$
题解：令 $a_i=h_i-h_{i-1}$ ，显然一个长度为 $l$ 的操作，就是把某个 $a_i$ 减去 $t$ ，$a_{i+l}$ 加上 $t$ 。显然，是从正的 $a_i$ 到某个负的 $a_j$ 比较优。
于是可以建立费用流模型，源点到所有正的 $a_i$ 连边，所有负的 $a_j$ 到汇点连边。如果负的 $a_j$ 满流的话就是有解，否则无解。
题意：长度为 $L$ 的线段，上面有 $n$ 个障碍物，第 $i$ 个在 $x_i$ ，质量为 $m_i$ 。你可以给第 $i$ 个障碍物一个初始速度 $v_i$ ，然后选择匀速往左或者往右，消耗能量为 $\frac{m_iv_i^2}{2}$ 。
问在 $T$ 时间内，总能量不超过 $E$ 的情况下，最长的无障碍物子段的长度。
$1 \le n \le 10^5, 1 \le L, T, E \le 10^6, 0 < x_i < L, 1 \le m_i \le 10^3$
题解：二分答案 $d$ ，考虑如何判定。假设这个没有障碍物的区间左端点是 $z$ ，那么在区间 $[z, z+\frac{d}{2}]$ 里的障碍物显然都要往左走，在区间 $[z+\frac{d}{2}, z+d]$ 里的障碍物都要往右走。
可以发现 $z$ 的关键点有 $x_i$ ，$x_i-\frac{d}{2}$ 和 $x_i-d$ 。把关键点拿出来排序，那么如果 $z$ 在相邻两个关键点对应的区间里，$[z, z+\frac{d}{2}]$ 和 $[z+\frac{d}{2}, z+d]$ 里的障碍物集合是一样的。
于是对于每个这样的区间，都可以列出一个一元二次方程，求一下最值即可。
关键点可以通过归并的方式合并，这样就可以做到线性判定。
C. Collections In Containers 题意：给你一个 $n$ 个 $d$ 维的向量集合，满足，如果存在向量 $a_1, a_2, ..., a_d$ ，那么对于任意 $b$ ，满足 $0 \leq b_i \leq a_i$ 都存在。
给出一个长度为 $n$ 的数组 $c_1,c_2,\dots,c_n$ 。你需要找到一个长度为 $n$ 的排列 $p$ 和 $q$ ，使得 $a_{p_i,j} + a_{q_i,j} \le c_j$ 。
$1 \le nd \le 10^5, 0 \le c_i \le 10^9, 0 \le v_{i,j} \le c_j$
题解：题目给定的 $c$ 其实没有多大用处，因为我们总是可以构造出一个 $c_j = \max_i(a_{i,j})$ 时候的解。
可以发现，题目给出的限制很强，我们任意去掉一维后这个性质还是满足的。其实题目给出的限制就是说集合是一个凸集。
考虑按照维数递归构造答案，假设我们需要构造满足前 $k$ 维的答案。把所有向量按照第 $k$ 维归类，值一样的归为同一类。那么对于同一类，我们可以递归搞出一个符合前 $k-1$ 维的解。接下来考虑如果使得第 $k$ 维也满足条件。
假设第 $k$ 维的最大值为 $m_k$ ，那么对于 $2 a_{i,k} \le m_k$ 的，肯定是满足条件的，因此我们需要调整 $2 a_{i,k} > m_k$ 的。对于这种 $a_{i,k}$ ，肯定存在另一个 $a_{j,k}=m_k-a_{i,k}$ ，使得 $a_{i,1..k-1} = a_{j,1..k-1}$ 。只需要交换它俩的匹配就可以使 $a_{i,k}$ 满足条件。
对于一个 $i$ 求出对应的 $j$ 的话，可以使用字符串 hash 来加速判定。
题意：有 $n$ 个格子，一开始第 $i$ 个格子包含一个数 $a_i$ 。有 $q$ 个操作，
令格子 $i$ 包含数 $x$
令格子 $i$ 指向格子 $j$
求出格子 $l$ 到格子 $r$ 的权值和
如果一个格子包含一个数，那么这个格子的权值为这个数；否则这个格子的权值为它指向的格子的权值。保证不会出现循环指向。
$1 \le n, q \le 2 \times 10^5, -10^4 \le a_i, x \le 10^4, 1 \le i, j \le n, 1 \le l \le r \le n$
题解：考虑把操作分块，每 $L$ 次操作重建格子的指向关系和权值。对于一个询问操作，我们只需要关心最近的 $O(L)$ 个修改操作。
把这些操作涉及到的格子拿出来，记为关键点。那么我们可以先基于未修改的权值，求出一个答案来。由于这些关键点都被修改过了，那么需要减去这些关键点对答案的贡献，就是对应子树里面有多少节点在区间 $[l, r]$ 里。同时我们也可以在 $O(L)$ 时间处理出，这 $O(L)$ 个关键点现在的权值是多少。把新的权值乘上子树里面合法节点个数加回贡献即可。
令 $L = \sqrt{n \log n}$ 的话，复杂度是 $O(n \sqrt{n \log n})$ 。
题意：给出 $n$ 个点 $m$ 条边的无向图。你需要把点分成两组，使得删掉连接不同组的边之后，每个点的度数都是偶数。
$1 \le n \le 500, 0 \le m \le \frac{n(n-1)}{2}$
题解：考虑用 $x_i=0/1$ 表示每个点属于哪个组，$deg_i$ 表示第 $i$ 个点当前的度数。可以发现，
如果 $deg_i$ 是偶数，那么 $\sum_{j \in N(i)} x_j \equiv 0 \pmod 2$
如果 $deg_i$ 是奇数，那么有 $\sum_{j \in N(i)} x_j \equiv \overline{x_i} \pmod 2$ ，即 $x_i + \sum_{j \in N(i)} x_j \equiv 1 \pmod 2$
于是，我们得到了一个异或方程组，高斯消元解一下就好了。
题意：考虑这样一个随机序列：$a_0 = 1$，$a_n$ 是随机选出来的 $a_i$ 和 $a_j$ ($0 \le i, j \le n - 1$ )的和。
你需要求出 $a_n$ 的方差。
$0 \le n \le 10^6$
题解：考虑方差的公式 $Var(X)=E(X^2) - E^2(X)$ ，我们仅需要求出 $a^2_n$ 和 $a_n$ 的期望值。
先考虑 $a_n$ 的期望值，根据期望的线性性，显然有
$$
E(a_n) = \frac{\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1} E(a_i)+E(a_j)}{n^2}=\frac{2\sum\limits_{i=0}^{n-1}E(a_i)}{n}
$$
最终其实可以发现，$E(a_n)=n+1$。
接下来考虑 $E(a^2_n)$ ，显然有
$$
\begin{aligned}
E(a^2_n) &=& \frac{\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1} E((a_i+a_j)^2)}{n^2} \\
&=& \frac{\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1} E(a_i^2+a_j^2+2a_ia_j)}{n^2} \\
&=& \frac{2 \sum\limits_{i=0}^{n-1}E(a_i^2)}{n}+\frac{2E((\sum\limits_{i=0}^{n-1}a_i))^2}{n^2}
\end{aligned}
$$
我们需要求出 $E((\sum\limits_{i=0}^{n}a_i)^2)$ ，可以拆成 $(a_n+\sum\limits_{i=0}^{n-1}a_i)^2$ ，化简下得到
$$
E((\sum\limits_{i=0}^{n}a_i)^2)=E(a_n^2)+E((\sum\limits_{i=0}^{n-1}a_i)^2)+E(a_n(\sum_{i=0}^{n-1}a_i))
$$
继续把 $a_n$ 拆掉的话，最终可以得到
$$
E((\sum\limits_{i=0}^{n}a_i)^2)=E(a_n^2)+\frac{(4+n)\cdot E((\sum_{i=0}^{n-1}a_i)^2)}{n}
$$
递推就可以算出答案了。
题意：交互题。有一个长度不超过 $500$ 的字符串 $s$ ，仅有小写字母组成。每次你可以询问一个串 $t$ 是不是 $s$ 的子序列。所有询问中 $t$ 的总长不能超过 $6 \cdot 10^5$ 。
题解：先问出每个字符出现的次数，然后每次拿出两个最短的字符串合并。假设当前是 $z$ ，还剩 $x$ 和 $y$ 没有合并，就查一查 $z+x[0]+y$ 或者 $z+y[0]+x$ 是不是子序列就可以确定下一个字符是 $x[0]$ 还是 $y[0]$ 。
题意：给出一个 $k$ 阶的 Hilbert's Maze，一个起点 $(x_s,y_s)$ 和终点 $(x_t, y_t)$ 。求出起点到终点的最短路。
$0 \le k \le 30, 1 \le x_s, y_s, x_t, y_t \le 2^{k+1}-1$
题解：对于每个点，我们先构造出一条从 $T_0$ 怎么演变到 $T_k$ 的路径。这条路径只需要记录：当前从这四条边的哪个位置出来以及到这个位置经过了多少距离。
对于两条这样的路径，我们可以找到他们的公共前缀，从这个位置开始，距离就可以独立计算了。因此，我们仅需要计算在这个公共前缀处，我们从一个点到另一个点的距离。
这个基本上可以分成三部分：外面正方形的轮廓线；上面的 $1 \times 2^k$ 的小区域；下面的 $T$ 型区域。对于后两者，我们最终都是要走到外轮廓的，除非两个点属于同一个区域。
I. Infinite Binary Embedding 题意：给定一棵 $n$ 个节点的满二叉树 $T$ 和一棵无穷满二叉树 $I$ 。问有多少个从 $T$ 的结点到 $I$ 的结点的单射 $f$ , 使得
若 $v$ 是 $T$ 中的叶子，则 $f(v)$ 在 $I$ 中的深度为 $h_v$
若 $v$ 是 $T$ 中 $u$ 的左孩子，则 $f(v)$ 在 $I$ 中是以 $f(u)$ 的左孩子为根的子树中的一个结点
若 $v$ 是 $T$ 中 $u$ 的右孩子，则 $f(v)$ 在 $I$ 中是以 $f(u)$ 的右孩子为根的子树中的一个结点
$1 \le n \le 2000, 0 \le h_v \le 10^9$
题解：令 $dp(v, x)$ 表示 $T$ 中以 $v$ 为根的子树，$f(v)$ 在 $I$ 中深度至少为 $x$ 的方案数。显然，我们就是要求出 $dp(1, 0)$ 。
可以发现，$f(v)$ 在 $I$ 的哪个深度为 $h_v$ 的位置上并不重要，因为所有子树都是对称的。考虑如下的递推式
$$
dp(v, x) =
\begin{cases}
2^{h_v} & v \text{ is leaf }, x \le h_v \\
\sum_{x \le y \le h_v}\frac{dp(lson(v), y+1)}{2^{y+1}} \cdot \frac{dp(rson(v), y+1)}{2^{y+1}} \cdot 2^y & \text{otherwise}
\end{cases}
$$
可以发现，如果我们令 $dp(v, x) = \sum_{i} a_i \cdot 2^{ix}$ ，那么我们就可以很方便的维护上面的转移式子。
对于一个 $v$ ，最大的 $i$ ，使得 $a_i$ 非零，只和 $v$ 的子树大小有关。因此可以在 $O(n^2)$ 做好转移。
题意：给出 $n$ 和 $b$ ，构造一个 $n$ 个点的图，使得从 $1$ 到 $n$ 的期望步数是 $b$ 。
$n = 200, b = 10^6$
题解：先构造 $100$ 个点的团，然后构造 $100$ 个点的链，接上即可。