2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 23/663 | 9 | 11 | 11 |
A¶
upsolved by
题意¶
题解¶
B¶
upsolved by JJLeo
题意¶
给定一颗 \(n\) 个节点的二叉平衡搜索树，每个节点的权值为 \(1\) 到 \(n\)，你需要保留包括根节点内的 \(k\) 个节点，使得剩下的部分连通且仍是一颗二叉平衡搜索树。要求将留下的 \(k\) 个数排序后序列字典序最小。
平衡树是指每个节点左子树和右子树的树高之差绝对值不超过 \(1\)，树高是指所有节点距离根节点的最大值，空子树的树高为 \(0\)。
搜索树是指每个节点的权值大于左子树所有节点权值，小于右子树所有节点权值。
(\(2 \le n \le 2 \times 10^5\)，\(1 \le k \le n - 1\))
题解¶
设树高为 \(i\) 的二叉平衡搜索树最少点数为 \(f_i\)，则有： $$ f_i=\begin{cases} 1, &i=0 \newline 2, &i=1 \newline f_{i-1}+f_{i-2}+1, &i \ge 2 \end{cases} $$ 即左右子树高度尽可能消，一个高度为 \(i-1\) 另一个为 \(i-2\)，再加上自己这个点。
接着可以发现，如果一个二叉平衡搜索树的树高为 \(i\)，那么一定存在一种删点方案使得保留部分树高为 \(j\) (\(j \le i\)) 且节点数为 \(f_j\)。
我们贪心地决定每个点要不要留下，一个点留下那么它的祖先肯定都留下，因此从根节点开始先序遍历，尽可能选左子树的点因为它们更小，对于那些还没遍历到的右子树，令他们的树高为左子树 \(-1\)，因为原树是二叉平衡搜索树，这一定是可以做到的。由此计算最少增加的节点数，若增加后总节点数 \(\le k\) 则可以保留，否则不保留，终止遍历并回溯。
假设遍历到了 \(x\)，如果 \(x\) 想要留下，依次考虑 \(x\) 及其每个祖先 \(y\)：
-
如果 \(y\) 是其父亲 \(z\) 的左儿子，那么 \(z\) 的左子树高度可能增大，此时 \(z\) 的右子树的最小高度也会随之增大，设 \(z\) 的树高由 \(a\) 变为了 \(b\)，则最少增加节点数为 \(f_b-f_a\)。
-
如果 \(y\) 是其父亲 \(z\) 的右儿子，那么 \(z\) 的左子树已经遍历完成，可以直接根据平衡性规则判断当前点能不能加。
(这里默认能加也是对的，不懂，可能是性质。) -
\(x\) 要留下，因此最少增加节点数增加 \(1\)。
由此计算最少增加节点数并判断是否保留。
接着有一些点是必须留下的，例如上述过程会确定一些祖先右节点的树高，当遍历这些节点时，它们必须留下，且它们的两个子树树高也被确定，设一个节点的树高被确定为 \(d\)，若左子树树高 \(\ge d-1\)，则确定左子树树高为 \(d-1\)、右子树树高为 \(d-2\)，否则确定左子树树高为 \(d-2\)、右子树树高为 \(d-1\)，这样保证了节点数最小和字典序最小。
若一个节点的树高被确定的值 \(<0\)，则等价于没确定，
因为原树是二叉平衡搜索树，总时间复杂度为 \(O(n \log n)\)。
C¶
upsolved by
题意¶
题解¶
D¶
upsolved by
题意¶
题解¶
E¶
upsolved by
题意¶
题解¶
F¶
upsolved by
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by JJLeo
题意¶
海面上有 \(n\) 个陆地，覆盖 \([l_i,r_i]\)，互不相交，你想要从位置 \(0\) 到位置 \(s\)，你有两种操作：
- 冲浪，移动 \(1\) 单位距离花费 \(1\) 时间。
- 跳跃，移动至多 \(d\) 个单位距离，花费 \(t\) 时间。
冲浪不能越过陆地，跳跃可以越过陆地但不能落在陆地上，任意时刻不能停留在陆地上 (陆地的两个端点除外)。
求最小花费时间。(\(0 \le n \le 500\)，\(1 \le s,d,t \le 10^9\)，\(0 < l_i < r _i < s\)，\(r_i-l_i \le d\))
题解¶
直接 dp 关键位置太多，需要用到一个非常重要的性质：一定存在一个最优方案，满足所有冲浪结束后要么接下来一步会直接跳到一个陆地的终点，要么已经冲浪到达 \(s\)。
如果一个最优方案中存在一段冲浪结束后不满足上述两个情况，因为不满足第二种情况，其后面必然是一个跳跃，如果这个跳跃没有跨过陆地，则将其和跳跃交换，直到其后面的跳跃跨过了陆地 (或到达 \(s\)，则已满足条件)，此时不断减少该冲浪的长度，将减少的部分放到该跳跃之后，直到该跳跃落在陆地的右端点，得到了一个时间相同的方案，因此仍是最优方案。
从而一旦开始冲浪，只需考虑其到之后 \(O(n)\) 个右端点的移动即可。具体来说，枚举要跳到的右端点 \(i\)，检查当前位置到 \(r_i-d\) 是否没有其它陆地，若是则用最小代价到达该位置后进行一次跳跃。最小代价一定是全部跳跃、除最后跳不全的部分冲浪其它跳跃、全部冲浪三种情况的最小代价。
还需考虑一直不冲浪的情况，也就是一直跳跃，那么显然每次都跳 \(d\)，最终要么跳到 \(s\)，要么被一个陆地卡住，那么最后一次会少跳一些到这个陆地的左端点。只需考虑转移到越过下一个陆地时的关键点，或越过下一个陆地失败，此时转移到下一个陆地的左端点。一直跳的起点一定为 \(0\) 或某个陆地的左右端点，每个起点最多延伸出 \(O(n)\) 个关键点，因此总关键点数量为 \(O\left(n^2\right)\)。
最后，一个关键点如果距离位置 \(s\) 中间没有其它障碍，可以直接算出最小代价得到可能的答案。
总时间复杂度为 \(O\left(n^3\right)\)。
记录¶
-1h：貌似🐍寄了
0~1h：🐍复活了，MJX看A好像签到，ZYF看I好像签到，CSK看F好像签到，CSK看E好像签到，MJX看C好像签到，CSK ZYF看G好像签到，签签签！三人各签IFC，然后一起讨论小心翼翼地签了E，接着 ZYF 吃饭＋写A，竟然一发过了，之后 ZYF 写 G，有个地方脑瘫了呼唤 CSK 帮忙 debug，之后找到交了，结果 WA 了，发现 100 / i 写成了 i / 100，改完过了。CSK和MJX说了半天H的几何做法，想了大半天不可做。MJX和ZYF玩D感觉能玩出一个 \(O(nm\log{n})\) 的做法，不会优化了，不过也许大概可能能过。
2h：ZYF推了个H的式子就感觉很可做就做了，MJX才发现H题自己理解错了，ZYF去写H，MJX喂给CSK D的做法，CSK感觉显然可以消掉一个 \(\log\) ，ZYF写的过程中因为没加 eps 被迷惑，加了交了就过了，之后 CSK 把D做法喂给ZYF，消了 log 不仅更快还更好写，感觉很对就开始写了。
3h：MJX看了看J题感觉不可做，又想了想感觉是个简单题随便维护一下就行了，然后喂给了CSK，感觉挺对的，MJX CSK帮ZYF debug D，WA了一发。MJX给ZYF喂了个J的做法，ZYF感觉用个链表维护就行，还有一点情况MJX没想到，MJX感觉自己是个nt。ZYF写的时候CSK在帮忙debug，发现top = 1 的特判放 while (top >= 2) 的前面了，改了就过了。ZYF J写了过了。
4h：看了看BK，不会，仨人闲逛去了...