Warning: session_start(): open(/tmp/sess_ef9f6db530cc18547dd73c05ac9eea34, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:running_chicken:2020_summer_week3_report [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:running_chicken:2020_summer_week3_report

2020/07/25 -- 2020/07/31 周报

团队

个人

todolist(补题)

2020牛客暑期多校训练营(第五场)

2020牛客暑期多校训练营(第六场)

Codeforces Educational Round #92

CJY

专题

比赛

题目

ZRX

专题

比赛

题目

XX

专题

点分治

倍增优化DP

比赛

Codeforces Educational Round #92

题目

Codeforces Educational Round F

本周推荐

zrx

cjy

题意

思路

评论

XX

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就好。

题目

代码

思维好题,需要发现有趣的性质,也考察线段树的灵活使用。

2020-2021/teams/running_chicken/2020_summer_week3_report.1596124713.txt.gz · 最后更改: 2020/07/30 23:58 由 selia