2020.07.25 2020牛客暑期多校训练营(第五场)
2020.07.27 2020牛客暑期多校训练营(第六场)
2020牛客暑期多校训练营(第五场)
2020牛客暑期多校训练营(第六场)
Codeforces Educational Round #92
点分治
倍增优化DP
Codeforces Educational Round #92
Codeforces Educational Round F
题意
思路:
评论:
Chess Strikes Back
来源:Codeforces Round #657 (Div. 2) F
算法:思维+set+线段树
题意:
给一个2n*2m的棋盘。该棋盘只有i+j为偶数的地方可以放子。如果一个位置放一枚棋子,那么它周围8联通的位置不能放子。有q组询问,每次占用或解除占用一个格子,询问当前棋盘是否可以放下nm个棋子。
思路:
将(x, y)-(x+1,y+1)的四个格子看成一个大格,这个大格里面左上角和右下角可以放置棋子。一个大格里只能放置一个棋子,因此每个大格都要放棋子。
一个神奇的结论: 如果存在这样两个大格,(x$_{1}$, y$_{1}$)在(x$_{2}$, y$_{2}$)的左上,(x$_{1}$, y$_{1}$)大格的左上角小格被占据,($_{2}$, y$_{2}$)大格的右下角被占据,那么不合法。因为(x$_{1}$, y$_{1}$)的大格只能放一枚棋子在右下角小格,相应的(x$_{1}$ +1, y$_{1}$)、(x$_{1}$, y$_{1}$ +1)、(x$_{1}$+1, y$_{1}$+1)这三个大格也只能放右下角……以此类推,(x$_{2}$, y$_{2}$)的大格也只能放右下角,但是这个位置被占据了,因此不合法。
实现:
用set记录每一行的纵坐标。在线段树中,对于大格中左上角的位置,记录该行最小值;对于大格中右下角的位置,记录该行最大值。对于线段树上每一个节点维护flag,如果左边最小值小于右边最大值,flag为1。询问看flag就好。
思维好题,需要发现有趣的性质,也考察线段树的灵活使用。