2020.07.25 2020牛客暑期多校训练营（第五场）

2020.07.27 2020牛客暑期多校训练营（第六场）

Codeforces Round #659 zrx A/D xx B/E cjy C/F

2020牛客暑期多校训练营（第五场）zrx A/H xx K cjy G/J

2020牛客暑期多校训练营（第六场）zrx E xx I cjy A/F

Codeforces Educational Round #92 xx E zrx F cjy G

Codeforces Round #660 cjy C zrx D xx E

欧拉回路

本周未参加个人比赛

2020牛客暑期多校训练营（第六场）A

本周暂无

2020牛客暑期多校训练营（第五场）

2020牛客暑期多校训练营（第六场）

2020牛客暑期多校训练营（第五场） a、h

点分治

倍增优化DP

Codeforces Educational Round #92

Codeforces Educational Round F

2020牛客暑期多校训练营（第五场） h

题意：最后转化问题后，得到的是有n个物品，都只有一个，每个物品对应多个互不相交的区间，给定一个区间，如果覆盖了一个物品的对应的一个区间，那么这个物品就获得了，每次给定一个区间求得到多少物品，强制在线。

题解：首先，这样互不相交的区间可以化成二维平面上的点，一个待求，如果覆盖一次算一个物品的话，那么求[l,r]区间的答案就等于x大于等于l，且y小于等于r的点数，但是每个物品最多被加一次。假设一个物品是[l1,r1],[l2,r2] 那就两个两个区间之间加权值为-1的点，如[l1,r2]的权值为-1，这样最后二维区间求和就行了！主席树可以很好的在线解决。

思考：把区间转换成点，以及去重方式很好。

African Sort

题意

给你一个排列，你每次可以选择一个下标集合，并把这个集合的元素随机排列，代价是这个集合的大小，求把原序列变成递增序列的期望代价。

思路：

首先把代价转换为每一个元素被选择的次数。有一个推论对于一个n元环，随机一次后，每个元素所在环的大小等概率分散在1-n。因此最优策略应

该是原排列中的每一个小环分别进行操作。操作代价可以通过之前的推论进行预处理。

评论：

这个题的思维度大，很有意思。

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

题目

代码

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