差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_639_div._1 [2020/05/09 01:22]
admin
+++ 2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_639_div._1 [2020/05/09 11:56] (当前版本)
toxel fix
@@ 行 1: / 行 1: @@
+====== 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}
+&1\\
+&0
+\end{pmatrix}
+YB:\begin{pmatrix}
+&1\\
+&1
+\end{pmatrix}
+RB:\begin{pmatrix}
+&0\\
+&1
+\end{pmatrix}
+$$
+那么我们只要将两位看做两个变元来列方程即可。
+时间复杂度 $\mathcal{O}(\frac{nm^{2}}{64})$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具