I
LYF 签到
F
ZRC&WD 签到
H
扫描线
题意：
平面上有 n 个矩形，给定d，需要找到一个位置 (x,y)，使得所有 (x+kd,y+kd) 均不落在矩形中
LYF解：
首先可以不移动兔子，而是移动矩形。把矩形都移到兔子初始在的d*d的方块内。然后扫描线看是否有空格即可。细节有些多。
补J
题意：
n个点，m条边的简单无向联通图，每个点一个权值 a_i
一个连通块的贡献：(-1)^块内点数⋅∑a_i [点 i 在该连通块内]；
可任意删除一些边，求连通块贡献之和最大是多少。
1≤n,m≤1e6, 1≤a_i≤1e9
解：
显然如果总点数为偶数时不需要删除，奇数时可以仅删除一个点，且删除一个点一定是最优解。
如果删除的点不是割点，则原连通块就被切成了包含这一个点的连通块和其余所有点的连通块，答案很方便统计。
若删除的是割点，只有当形成的新连通块都包含了偶数个点时方案才可能是最优解。
如何统计新连通块点数奇偶性？
魔改tarjan算法即可。dfs途中记录搜索树每个节点下的各个子树结点个数。