XXI Open Cup, Grand Prix of Samara
链接
| A | B | C | D | E | F | G | H | I | J | K | L | M | N |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\color{red}{\texttt{-}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{red}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{green}{\texttt{+}}$ | $\color{gray}{\texttt{+}}$ | $\color{green}{\texttt{-}}$ | $\color{green}{\texttt{+}}$ |
B. Fakes and Shidget
G. Lexicographically Minimal Subsequence
签到题。
D. Two Pirates - 2
首先最优策略显然是每次取最大的。问题在于如何求出第 $i$ 大的值被取走的概率。
考虑将问题转化成两人在给球染色，每次一方随机将球染白，另一方将最右边没有染色的球蓝黑。
正难则反，考虑倒过来处理，即白方随机插入一个白球，黑方往最右侧插入，这样可以 dp 求出每个位置是黑球的概率 $f_i$。
然后将原序列排序，求 $\sum f_ia_i$ 即可。复杂度 $O(n^2)$。
代码
1 |
|
L. Not the Longest Increasing Subsequence
和毛营的 Maximal Subsequence 很像。由于值域为 $k$，故最长上升子序列至多为 $k$，容易证明答案等于最多选取多少个互不相交的最长上升子序列。
用类似分层图的做法处理即可。复杂度 $O(n\log n)$。
F. Exactly One Point
考虑 dp。设 $i\in S$ 当且仅当存在一种合法方案，最后一个选取的点为 $i$。考虑如果 $i$ 合法要求存在一个 $j<i$，使得不存在一个区间同时包含 $i,j$，也不存在一个区间 $[l,r]$ 满足 $j<l,r<i$。换句话说，$j$ 必须在所有右端点不大于 $i$ 的区间左端点最大的位置的右边。
容易发现这个限制单调不降，直接用一个队列维护即可。复杂度 $O(n)$
代码
1 |
|
J. Lost Island
经典题。结论是：如果颜色为 $i$ 的人被告知 $b_i\neq 0$，那么颜色为 $i$ 的人会在第 $a_i-b_i$ 天后自尽。特别的，由于所有人知道颜色数，如果最后只剩下一种颜色的人，那么会在第二天全部自尽。
复杂度 $O(n)$。
代码
1 |
|
C. Cyclically Shifted Maze
先枚举一维，然后对于另一维，相当于每次循环位移一格，要求判断是否连通。
考虑对于一个网格，我们枚举一条竖线将其划成两块，对于每一块我们单独判断它的连通性。容易发现，如果某一块中存在一个点与两块相邻的边界处不连通，那么两块合并后一定也不连通。如果不存在这样的格子，那么我们只需要保存相邻边界处的连通性，然后合并相邻处的 $O(n)$ 个点，判断合并后是否连通即可。
这样对于原题，我们预处理只保留某个后缀情况下右边界的连通性 $G_i$，再预处理只保留某个前缀情况下左边界的连通性 $F_i$。假设循环位移后边界变成了 $j$，我们只需要合并 $F_{j-1}$ 与 $G_j$ 即可。
复杂度 $O(n^3\log n)$。
代码
1 |
|
E. Powerless Mage
考虑第一维排序扫描线，这样变成一个平面问题：每次加入一个点，询问所有不偏序任何一个集合中点的点中两坐标之和最大的点。
容易发现真正产生限制的点是一条折线。考虑维护这条折线，显然折线上的点 $x$ 坐标单增，$y$ 坐标单减，那么每次插入一个点就大力将无效的点弹出，然后用 STL 维护折线的所有上端点的两坐标之和即可。
注意特判 $\inf$ 的情况。复杂度 $O(n\log n)$。
代码
1 |
|
K. Bloodseeker
首先把奖励对 $m$ 取 $\min$，那么总有一种方案使这些奖励完全加到血量里。
这样题目可以抽象成：你一开始有 $m$ 的钱，有 $n$ 个物品，买第 $i$ 个需要 $t_i$ 的钱，然后会有 $h_i$ 的收益。你需要时刻保证钱数为正，问能否买完所有物品。
这是一个经典题。把所有物品按收益正负排序。显然先买收益为正的，在收益为正的部分中显然容易买的（$t_i$ 较小）先买。然后对于收益为负的，可以将其反过来看，即从最终状态不断卖这些物品。所以应该先买 $h_i$ 大的。直接按这个顺序排序然后贪心取即可。
复杂度 $O(n\log n)$。
代码
1 |
|
H. Video Reviews - 2
首先显然有一个二分答案然后贪心的做法，显然也过不去。
考虑倒过来做。假设我们最后已经获得了 $m$ 条评论，那么贪心找到前面第一个 $a_i<m$ 的位置，说明如果前面获得了 $m-1$ 的评论，那么之后就会获得 $m$ 条评论。
特别的，如果前面只剩下了 $m$ 个人，而当前人 $a_i\geq m$，那么我们不得不花费 $1$ 代价说服他。
这里空间只有 $64\texttt{MB}$，不过由于题目规定 $z_i$ 必须是质数，所以我们可以先顺序求出每个序列最后一个位置，然后倒过来用逆元推出上一个值。
复杂度 $O(n+k\log n)$。
代码
1 |
|
A. Absenteeis
首先，如果两个人的区间 $[l,r],[l’,r’]$ 满足 $[l’,r’]\subseteq[l,r]$，那么 $[l’,r’]$ 就没有用了：显然监视区间越长越容易抓你的车。
如果没有人的区间 $[l,r]$ 满足 $l\leq k,r\geq m-k$，那么你完全可以不工作，因为没有人可以确定你有没有工作完 $k$ 时间。反之，如果有这样的人，那么你的左端点必须 $\leq m-k$，右端点必须 $\geq k$，否则他就可以确认你工作时长 $\leq k$。
同时，如果你的工作区间 $[x,y]$ 被某个人 $[l,r]$ 包含了，那么你必须工作至少 $k$ 小时，这显然是一个 trivial 的情况。所以可以假设最优区间不被任何区间包含。
由于我们已经将被包含的区间去掉了，所以剩下的区间左右端点均单调。
N. Premove Checkmate
大致思路：
注意到虽然后很牛逼，但要将死对方本质上只有两种方式：
1
2
3
4
5
6
7
8
9
10
11?...
.Q..
..K.
....
和
?..Q
....
.K..
....下面的位置其实大概率是不合法的，因为王可以左右移到，大概率后会在王的攻击范围内。所以一般采用第一种方式。
如果对方可行空间只有 $1\times 6$，可以使用下述方式将死：
1
2
3
4
5
6
7??????.. ?????...
.......Q → ......Q.
......K. ......K.
↓
??...... ??......
.Q...... ← ...Q....
..K..... ..K.....首先，将王移到 f3，然后后移到 c5，这样对方的可能位置被分成一个 $3\times 5$ 的矩形和额外点 h3。然后移到 f4，将额外点分开。将后移到 h4，这样可以将后从两个状态区分开。
额外点的可行空间只有不到 $1\times 6$，直接用上面做法干掉即可。然后现在变成了 $3\times 5$ 的网格：
1
2
3
4...?.???
.K..????
...?????
.Q......此时王往右冲会分成两部分：
1
2
3
4
5
6
7
8
9
10
11...?....
.K......
...?....
.Q......
和
.....???
..K.????
....????
.Q......将上面的 K 上移，此时由于对面王必须移动，这样就让出了第 $4$ 行，王再往右下：
1
2
3
4........
..K.?...
....?...
.Q......由于皇后和王的位置与另一局面相同，可以合并两者。将后向右移一格，局面变成了 $3\times 4$ 的格子。
不断递归这个过程，当只剩下一行时用上面 $1\times 6$ 的方法解决即可。
模拟程序
1 |
|