Contest Info

date: 2018.12.09 14:51-19:51

practice link

Solutions

A. Coloring Roads

题目大意：\(n\) 个节点的树，若干次询问，每次将点 \(u\) 到根路径上的每条边染色为 \(c\)，并询问出现次数恰好为 \(m\) 次的颜色个数。

类似的技巧

题解：

轻重链剖分后，暴力维护每条重链上不同的颜色段即可，时间复杂度\(O(n\log{n})\).

B. Dev, Please Add This!

题目大意：

给出一个\(h\times w\)的网格图，\(1\le h,w\le50\).

每个格子可能是障碍，或者是空地，或者是宝藏。

给定一个起点，该位置不存在宝藏。

每次移动时可以任意选择一个方向，滑行直到遇到障碍或边界停止（沿途的宝藏会被自动收集，然后该格子会变成空地）。

问是否能收集到全部的宝藏。

题解：

先求出每个点出发向四个方向移动到达的点，连边，求强连通分量，缩点。

因为起点处不存在宝藏，那么每次收集都一定经过了一次移动，即宝藏处四个方向移动的某个终点一定被访问过了。

而水平方向的两个终点一定可以相互到达，在同一个强连通分量内，同理竖直方向也是。

将每个强连通分量是否被访问作为一个二元变量，那么就转换为一个2-sat判定问题，约束如下：

• 对于每个宝藏点，水平方向终点的强连通分量和竖直方向终点的强连通分量，至少一个被访问。
• 对于起点，必须被访问；对于起点不能到达的点，不能被访问
• 对于任意一个强连通分量\(u\)，从它出发bfs，如果无法访问到强连通分量\(v\)，且\(v\)的编号比\(u\)更小（否则\(v\)可能在dag深度更小，可以从\(v\)到达\(u\)），那么\(u\)和\(v\)不能同时被访问

时间复杂度\(O(h^2w^2)\).

D. Dumae

题目大意：\(n\) 个人排队，每个人的位置在区间 \([L_i,R_i]\) 之间，并且有 \(m\) 对关系，每对关系是 \((u_i,v_i)\) 表示 \(u_i\) 要站在 \(v_i\) 前面，求一种可行的方案。

题解：我们增加一个 \(0\) 号点，然后建图，如果图不是一个 DAG 那么无解。否则，我们按照拓扑序，用当前节点的 \(R_u-1\) 更新（取 min）后继的 \(R_v\)。然后我们再按照逆拓扑序贪心，设当前要确定第 \(i\) 个位置，取出出度为 \(0\) 且 \(L \leq i\) 的点中有最小的 \(R\)（且大于等于 \(i\)）的人。

E. Electronic Circuit

题目大意：我们递归定义一个图（且必须指定两个不同点作为起点和终点）是好的：

• 只有一条边的图是好的，起点和终点就是它的两个端点；
• 图 \(G,G'\) 都是好的，把 \(G\) 的终点和 \(G'\) 的起点合并的新图也是好的；
• 图 \(G,G'\) 都是好的，把 \(G,G'\) 的起点、终点分别合并的新图也是好的。

给出一个图，让你随意确定起点和终点，判断图是否为好的。

题解：考虑递归定义的逆过程，我们每次删掉所有的重边（定义第三条），然后删掉所有度为 \(2\) 的点（定义第二条），不断如此。如果最后图只剩下两个点和一条边（定义第一条），那么图是好的。

F. Fake Plastic Trees

逗你玩题。构造方式是唯一的。

G. Fascination Street

题目大意：给出一个序列 \(\{w_i\}\)，你可以交换两个数至多 \(k(k\leq 9)\) 次。要求你选择一些位置，最小化权值之和，满足每个位置要么自己被选择，要么左右两个位置至少有一个位置被选择（不允许连续三个位置不被选择）。

题解：

有意义的交换一定是交换一个被点亮的位置和一个不被点亮的位置，记录末尾两位的点亮状态和换入的个数以及换出的个数进行dp即可。

时间复杂度\(O(nk^2)\).

H. Fractions

签到题。

I. Game on Plane

题目大意：给出一个正 \(n\) 边形上的 \(n\) 个点，两人组合游戏，每次可以选择两个点连一条边。要求边不交叉，任意时刻出现一个凸包，则获胜。

题解：容易发现连一条边把点分成了两堆，并且每次选择的两个点都只能是孤立点（否则对方下一步获胜），得到：\(\text{sg}_n=\displaystyle\text{mex}_{a+b=n-2}(\text{sg}_a\oplus \text{sg}_b)\)。

J. Histogram Sequence

题目大意：有一个长度为 \(n\) 的数列 \(\{h_{i}\}\)，对于 \(1\le l\le r\le n\) 的每个区间 \([l,r]\)，定义它的价值为 \((r-l+1)\min_{l\le i\le r}h_{i}\)。现在将所有 \(\frac{n(n+1)}{2}\) 个价值排序，要求你给出第 \(L\) 个到第 \(R\) 个之间的值。

题解：二分求出第 \(L\) 个和第 \(R\) 个的值 \(a_{L}\) 和 \(a_{R}\)，\((a_{L},a_{R})\) 中间的值全部都要取。具体的个数使用单调栈计算。

K. Interesting Drug

题目大意：一条路上按顺序有 \(n\) 瓶毒药，对于每个 \(i\in[1,n]\)，求出如下的值：

从 \(i\) 出发，中途可以任意改变左右运动的方向，设吃到毒药的顺序是排列 \(p\)，若 \(p_{c_{i}}=i\)，那么获得 \(d_{i}\) 的伤害（\(c,d\) 给出）。问最大伤害。

题解：先考虑某个固定的 \(i\)。我们将式子变化一下，得到 \(p^{-1}_{i}=c_{i}\)。那么也就是说，我们要构造一个排列，使得 \(p_{i}=1\)，从 \(i\) 往左往右分别递增，且使得与 \(c_{i}\) 相同的位置对应的 \(d_{i}\) 最大。

我们很容易想到一个 \(dp\)：设 \(dp[j][k]\) 表示我们已经在 \([j,k]\) 中填好了数，得到的贡献的最大值。初值为 \(dp[i][i]=0\)，答案为 \(dp[0][n-1]\)。转移时只需要简单地枚举 \(k-j+2\) 填入左边还是右边即可。但是这样复杂度是 \(\mathcal{O}(n^{3})\)。

注意到这个 \(dp\) 也可以有如下意义：将每个转移看做一条带权的边，那么 \(dp[j][k]\) 就是 \((i,i)\) 到 \((j,k)\) 的最长路。那么我们把所有边反向，不会改变答案。于是我们可以从 \((0,n-1)\) 开始转移，计算每一个 \((i,i)\) 即可。此时复杂度降为 \(\mathcal{O}(n^{2})\)。最后再简单地用线段树优化即可。

时间复杂度 \(\mathcal{O}(n\log n)\)。

L. Timsort

签到题。

M. Utilitarianism

题目大意：

给出一棵\(n\le10^5\)条边的边带权树，求这棵树中恰好\(k\)条边的最大匹配。

题解：

二分一个偏移量\(offset\)，求每条边都加上这个\(offset\)的最大权匹配，如果不够\(k\)条边就调大\(offset\)，否则调小。

可以理解为每一个匹配对应了二维空间中的一个点，\(x\)坐标为边权和，\(y\)坐标为边数，这样其实是二分了一个斜率在凸包上查找\(y=k\)的最优解对应的点。

时间复杂度\(O(n(\log{n}+\log{\text{值域}}))\).