ChangKe's Blog

ZLXSCDay2验题报告

这次比赛的出题人有ZLX,Austin Bannister,Brian Dean,Nathan Pinsker。
后面几位的出现是因为引用了USACO月赛原题。
我是本次比赛的验题人,因此没有参加比赛,当然你们要吐槽题目也不要怪我啊~(逃
下面是正文,顺序为随机顺序。

4.黑心买卖

比赛开始前我问出题人,说你出这题有什么意义,然后他沉默了。
看这道题之前,请先学习并查集的相关知识,最好AC掉下面这道题:打击犯罪.pdf,目前我只发现在AYYZVijos上可以在线提交,地址http://pingce.ayyz.cn/vijos/Problem_Show.asp?id=1949

算法一

暴力模拟所有的操作,每进行一次操作后用BFS更新连通性。
时间复杂度,期望得分30分。

算法二

这里只有删除操作,我们完全可以把所有操作倒过来,变成只有插入点的操作。而每次插入操作又等价于合并一些连通块,所以我们用并查集进行维护。每插入一个点,我们把所有与之相连的点所在的集合进行合并,并在合并中随时更新最大集合所含的元素个数,如果这个数等于当前插入的点的个数,那么本次输出YES,否则输出NO
时间复杂度,期望得分100分。

1.梦游仙境

看这道题之前,请先学习2014年国家集训队的这篇论文:根号算法——不止是分块.pdf,作者王悦同。

算法一

很显然直接暴力统计就可以了。
时间复杂度最坏是,期望得分30分。

算法二

就是那个论文里的例1。文中的标题是“从一道水题说起”。
时间复杂度最坏是,期望得分100分。

2.撩妹高手

比赛开始前我问出题人,说你出这题有什么意义,然后他BlahBlah说这题不水,然后我发现我想简单了。

算法一

题目的描述很容易使人想到动态规划。我们设表示前个蛋糕所能获得的最大总体积。显然,状态转移方程是

按照这个方程直接DP就行了。
时间复杂度,期望得分40分。

算法二

上面这个DP方程里,对变量只用到了它所对应的,这启示我们可以用某种数据结构来避免这一层枚举。因为方程中的限制条件是,而我们是从前往后做的,所以在计算时只有在前面的才可能放进数据结构里,因此暂时不必管的条件。
而对于另一个条件,如果我们构造另一个序列,它的下标范围是,每一个位置上存的值,就是半径等于下标的位置对应的值中最大的一个。这样,我们的询问就成了询问这个序列的某一个后缀的最大值,用树状数组或线段树维护就可以了。当然计算出新的值之后,不要忘了更新。
时间复杂度,期望得分100分。

3.卡牌游戏

In the simple case where high card always wins one optimal strategy that Bessie can take is to always answer FJ's plays with her lowest card that is still higher than FJ's card (or her lowest card in the case she can't beat FJ). This works because if we can take something we should; otherwise the best that the card we didn't end up using can gain us is 1 trick so there can be no net gain.
This strategy informs the more complicated scenario where we switch from high card wins to low card wins at some point. In this case we should always allocate our highest cards to the section where high card wins and are lowest cards to the latter section. Then this reduces to the simpler case.
To solve this problem where we need to determine the best switch point we can make use a segment tree data structure that will enable us to solve the online version of the simple case. We will be able to insert a card for each player and determine the max score Bessie could achieve. Using this data structure we can determine how many points Bessie will get from the high card wins and low card wins part of each game and output the switch point that yields the highest overall score.
Building this data structure can be done by tracking for each segment in the tree the number of available cards in this segment that Bessie could play over lower cards, the number of coverable cards that FJ has played in this segment that haven't been covered, and the number of points we can score in this segment. Combining two segments is then done by summing the points and awarding points based on the min of coverables on the left and coverers on the right. The other fields are updated similarly (see comb() in my code below). The rest is a standard segment tree implementation.

啊哈,美国人的题解,简单易懂,对吧!我就不解释了~

5.哞哞城堡

This problem suggests a DP approach, and the bounds suggest that $O(n^3)$ is a comfortable target to aim for. There are several ways to approach this problem, but all of these focus on fixing some property of the rectangle, iterating over all possible values of that property, and finding the best rectangle for each iteration. One of the simpler ways is to fix an edge of the rectangle, and calculate the maximum possible rectangle with that edge.
For simplicity, we will fix the left edge of the rectangle. There are $O(n^2 \cdot n) = O(n^3)$ possible left edges, so we will reach our desired runtime if we can compute the best possible rectangle with this edge in $O(1)$ time. Luckily, we can use a sliding window to do so: if we process the left edges in order from left to right, we can note that the right edge of the rectangle must also move to the right over time. This is because a candidate rectangle will never become invalid as we move its left edge more to the right. We can use a simple data structure to query subrectangles of our given array in $O(1)$ time (see the code below if you're not quite sure how).

啊哈,美国人的题解,简单易懂,对吧!我就不解释了~

什么,你想打我?快跑啊……
如果你阅读上述内容有困难,请拿出《牛津高阶英汉词典》。