====== Contest Info ======

[[http://codeforces.com/contest/1344|practice link]]

====== Solutions ======

===== A. Hilbert’s Hotel =====

签到题。

===== B. Monopole Magnets =====

签到题。

===== C. Quantifier Question =====

**题目大意**：给定一个逻辑命题 $?x_{1}?x_{2}\cdots?x_{n}\bigwedge_{i=1}^{m}(x_{i_{1}}<x_{i_{2}})$，其中每个 $?$ 填上 $\forall$ 或 $\exists$，使得命题成立。求 $\forall$ 的最大数量。

**题解**：建图。如果有环显然无解。否则，对于一个 $i$，如果存在 $j<i$ 使得 $j\to i$ 或 $i\to j$，那么 $i$ 只能选择 $\exists$。那么对于每个 $j$ 在正反图上分别 bfs 一遍标记一下 $i$ 即可。

===== D. Résumé Review =====

**题目大意**：最大化 $\sum_{i=1}^{n}b_{i}(a_{i}-b^{2}_{i})$，其中 $b_{i}\in[0,a_{i}]\cup\mathbb{Z}$。要求 $\sum_{i=1}^{n}b_{i}=k$。

**题解**：注意到这个式子在 $b_{i}\ge0$ 时是凸的，可以盲猜一个 wqs 二分。

===== E. Train Tracks =====

**题目大意**：给你一棵有根树组成的铁轨，父亲连到儿子的边相当于一些分岔道，同时只能连接在一个儿子上。每条边有个权值。有 $m$ 辆火车，从 $1$ 开始，已知它们进入 $1$ 的时间和目的结点。在一个单位时间，依次发生以下两个事件：

  * 扳动某**一个**结点的分岔道，注意一个单位时间只能扳动**一个**
  * 所有火车向目的地移动一个单位

如果一辆火车开出了轨道，它会立刻爆炸；如果火车到达目的地，它会停下来，不再移动。

问最晚的爆炸时间，以及在此前提下的最小扳动次数。

**题解**：用 ''%%set%%'' 维护经过每个点的火车及经过时间，可以发现很容易用 dsu on tree 处理。在 ''%%set%%'' 中，如果有两个时间相邻且走向不同子树的火车，设时间分别为 $t_{1},t_{2}$，那么必须在 $[t_{1}+1,t_{2}]$ 之间扳动一次轨道。这样我们就得到了一些区间，需要在每个区间中选一个点，且不重复。这是一个很经典的区间二分图匹配。

所以说这题真就硬拼两个老 idea 啰，除了难写之外有个啥意思。

===== F. Piet’s Palette =====

**题目大意**：有 $R,Y,B$ 三种颜色方块组成的序列，从左往右依次消除。如果只剩一个方块，那么序列的颜色就是它；如果不剩方块，那么序列颜色为白色。如果开头两个方块异色，那么把它们替换为剩下的一种颜色；否则删除这两个方块。

现在给你一个长度为 $n$ 的序列，依次有 $m$ 个操作：

  * mix，选取序列的一个子集和一定的操作顺序进行消除，告诉你消除后的颜色
  * RY，选取一个子集，交换子集中的 $R,Y$ 两种颜色
  * YB，RB 同理

原序列中可以有空的方块，它们不参与上述操作

要求你构造一个原始序列满足操作结果。

**题目大意**：定义 $R=1,Y=2,B=3$，定义白/空为 $0$，将两个相同方块的消除看做是替换为一个白方块。我们会惊喜的发现，替换操作事实上就是异或！最终序列的颜色即为序列的异或和。

如果只有第一种操作，小朋友都知道可以高斯消元来解。对于后三种操作，如果把两位看做向量的两维，可以发现后两种操作竟然是线性变换：

$$
RY:\begin{pmatrix}
0&1\\
1&0
\end{pmatrix}
YB:\begin{pmatrix}
1&1\\
0&1
\end{pmatrix}
RB:\begin{pmatrix}
1&0\\
1&1
\end{pmatrix}
$$

那么我们只要将两位看做两个变元来列方程即可。

时间复杂度 $\mathcal{O}(\frac{nm^{2}}{64})$。