Codeforces Round #737 Editorial

本来只想写 \(E\) 的题解,但因为 D fst 了,所以全部写一遍吧,反正不多。

CF1557A

直观感受了一下,感觉最大值一组,其他一组最优,因为把最大的分成若干段直观感受不优,然后就过了。

CF1557B

题目问的是子段,不是子序列,因为这个wa了一发,并收获了干瞪眼 40min 。

显然只有排序序列中存在的子段才能分成一组,模拟即可。

CF1557C

将 n 分奇偶讨论,从高到低位枚举,若n为偶数,则全部&起来该位有值时,亦或起来一定没有值,剩下位随便选,若为奇数则不管,若&起来没有值则只有偶数个数该位有值,即 \(2^{n-1}\) 种方案,注意讨论 n 为偶数的情况。大力计算一波即可。

CF1557D

定义 \(dp_i\) 表示保留第 \(i\) 行,在 \(i-n\) 行中最多留多少行。线段树优化 \(dp\) 即可。

好像必须离散化而不能用动态开点代替,因为开不下,开小了会 RE ,而pretest很弱,大概就是这样 fst 的。

CF1557E

看了 Hint2 之后大概就会做了。

这里给出一种构造方案。首先将皇后安排在左上角,同时我们认为当我们的皇后在第 \(x\) 行时,国王一定不在 \(1-x\) 行中。考虑如何使棋盘始终满足该性质。

考虑从左往右遍历当前行 \(x\) ,如果遇到国王往下方走,则国王必不在 \(x+1\) 行,皇后往下走一步即可。

若国王往上走,则从头遍历当前行 \(x\)。

显然,若国王在第 \(x+1\) 行,则从左往右遍历一遍必然会逼迫国王往下走一格。因此若一通遍历下来,国王没有在竖直方向上的移动,则国王必不在第 \(x+1\) 行,往下移动即可。

该做法正确性可以保证,考虑询问次数。

国王最多往上走 7 步,则最多重复遍历行 7 遍。除去这些,除去最后一行的每一个格子都可能会被遍历一遍,以及皇后最多往下走 6 步,因此询问次数最多为:56+56+6=118次,而且实测远远低于该数目。(官方数据中似乎没有让我步数超过60的)。

可以通过本题。

上一篇:JDBC(JAVA与数据库的连接)


下一篇:Linux系统管理上机作业7