practice link

签到题。

签到题。

题目大意：给定一个逻辑命题 $?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$ 即可。

题目大意：最大化 $\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 二分。

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

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

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

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

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

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

题目大意：有 $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})$。