A-D，耻辱之夜。
A.Square
题意：以任意顺序给出正方形的四个顶点坐标，求面积。
解：
$(\max\lbrace x\rbrace-\min\lbrace x\rbrace)^2$ 即可。
B.Arranging Cats
题意：可以取出，交换，放入 $1$，求将 $a$ 变成 $b$ 的最小操作数。
解：
首先，对于 $a_i=b_i$ 的位置，不用考虑，
其次，那就只有 $a_i=1,b_i=0$ 或 $a_i=0,b_i=1$ 的情况了。贪心地想，先移动 $1$ 去匹配 $1
$，然后把多的 $1$ 取出即可。
答案就是 $\max\lbrace[a_i=1],[b_i=1]\rbrace$。
C.Sending Messages
题意：在 $t_i$ 时刻，手机必须是开机状态。开机状态下，每持续 $1s$，消耗 $a$ 能量；关机不消耗能量，但是开机消耗 $b$ 的能量，初始第 $0s$ 有 $c$ 的能量且出于开机状态。判断是否可以在能量耗尽前满足 $n$ 个时刻都是开机状态。
解：
$t_i$ 必是开机状态，那么 $t_i$ 时刻之后便与 $t_i$ 之前无关，即：贪心地让 $t_i$ 时刻的能量尽可能大即可。在 $t_{i-1}$ 到 $t_i$ 之间，只能是开机一次，或者全程开机。那么比较一下这两者的大小即可。
D.Very Different Array
题意：给定两个序列 $a_n$ 和 $b_m$，要求在 $b_m$ 中选出 $n$ 个数使得 $\sum\limits_{i=1}^n|a_i-c_i|$ 最大。求最大值。
解；
贪心地想，将 $b_m$ 中大的和 $a_n$ 中小的进行匹配，$b_m$ 中小的和 $a_n$ 中大的进行匹配。
答案与序列的顺序无关，那么可以先将 $a_n,b_m$ 升序，然后用 $b_m$ 的后缀和 $a_n$ 的前缀匹配，$b_m$ 的前缀和 $a_n$ 的后缀匹配即可。枚举这个分界点，一定可以找到最大值。
证明：
引理：
最后的答案形式一定是：
- 在分界点前（含分界点），$a_i<b_i$。
- 在分界点后：$a_i>b_i$
因为如果在分界点后，存在一个位置 $a_i<b_i$，那么 $b_i$ 完全可以移到 $a_i$ 的前面，因为 $a_j<a_i(j<i)$，在前面同样满足 $a_j<b_i$ 且此时答案会变大。
此时，若 分界点前的，不是 $b_m$ 的后缀，那么在 $b_m$ 中一定存在一个比分界点前的 $b_i$ 大的元素去替换它了。
E.Eat the Chip
题意：Alice 每次可以向 $(x+1,y-1),(x+1,y),(x+1,y+1)$ 移动，Bob 每次可以向 $(x-1,y-1),(x-1,y),(x-1,y+1)$ 移动。一方将棋子移动到另一方上则该方获胜，反之则是平局，求胜者。
解：
引理：
若 $y_0=y_1$，即 Alice 和 Bob 在同一列：
- $|x_0-x_1|$ 为奇数时，Alice 必胜。
- $|x_0-x_1|$ 为偶数时，Bob 必胜。
假设 $|x_0-x_1|$ 为偶数时，后手必胜。
那么，$|x_0-x_1|$ 为奇数时，先手往下走，使 $|x_0-x_1|$ 为偶数，且仍满足 $y_0=y_1$，那么此时的后手必胜即为初始时的先手必胜。
核心变成 $|x_0-x_1|$ 为偶数时，后手必胜：
策略：无论先手怎么走，后手都选择走到和对方同一列。
那么每次 $|x_0-x_1|$ 变小 $1$，因为 $|x_0-x_1|$ 为偶数，那么最后就是后手必胜。
对于 $y_0\neq y_1$ 的情况：
- 若 $|x_0-x_1|$ 为奇数，那么 Bob 不能获胜，容易发现 $|x_0-x_1|$ 为奇数时最后一步（使得 $x_0=x_1$ 的那步）一定是 Alice 走出来的。
- 若 $|x_0-x_1|$ 为偶数，那么 Alice 不能获胜。同上。
所以：
- $|x_0-x_1|$ 为奇数时，Alice 要在 y 轴追上 Bob，而 Bob 要尽可能地远离 Alice。因为一旦移动的过程中，出现了 $y_0=y_1$，那就是 Alice 获胜。所以 Alice 要朝 Bob 的方向移动，Bob 要朝面向 Alice 的另一个方向移动。
- $|x_0-x_1|$ 为偶数时，同上。
因为 $h\leq 10^6$，所以最多走 $10^6$ 步，所以模拟这个过程即可。
同时，因为奇偶交替的强性质，直接用式子 $O(1)$ 判断也可以。
F.Sum of Progression
题意：$q$ 次询问 $s,d,k$ 求 $a_s+a_{s+d}\times2+…+a_{s+(k-1)d}\times k$。
解：
对索引等差求和是根号分治的一种经典思路。
先考虑这样一个问题：
求 $\sum\limits_{i=l}^r(i-l+1)\times a_i$。
先把式子拆成：$\sum\limits_{i=l}^ri\times a_i-(l-1)\sum\limits_{i=l}^ra_i$。
然后对前后两部分分别做前缀和差分即可。
那么此题也是一样。
设阈值为 $t$：
- 若 $d>t$，$k\leq\lfloor\frac{n}{d}\rfloor<\lfloor\frac{n}{t}\rfloor$。暴力求和即可。
- 若 $d\leq t$，用上述套路解决。$sum[i][j][0/1]$ 表示公差为 $j$ 的前 $i$ 个数的两种前缀和。
时间复杂度：$O(q\lfloor\frac{n}{t}\rfloor)$。
空间复杂度：$O(nt)$。
直接将 $t$ 设为 $\sqrt n$ 即可。
时间复杂度；$O(n\sqrt n)$。
空间复杂度：$O(n\sqrt n)$。
addition：
看到一种不显式设阈值分析的根号算法。
将询问离线。对于每个 $s\bmod d$，求从 $s\bmod d$ 开始的公差为 $d$ 的一个序列。同样使用前文中的两种前缀和维护。每次询问时，直接 $O(1)$ 差分询问即可。这样的询问时间复杂度就是 $O(q)$ 的了。
考虑从 $s\bmod d$ 开始的公差为 $d$ 的序列的维护。对于一组 $s\bmod d$，直接暴力加公差的时间复杂度为 $O(\frac{n}{d})$。但是对于同一组 $(s\bmod d,d)$（即：起点和公差相同的情况）可以略去。
因为 $s\bmod d$ 的值只有 $[0,d)$，所以一种 $d$ 的值会产生 $d\times \frac{n}{d}=n$ 的时间消耗。那么总共只有 $n$ 个 $d$，所以最多只会有 $\sqrt n\times n$ 的时间消耗。
因为 $1+2+…+d=\frac{d\times(d+1)}{2}$，$d\leq \sqrt n$。所以最多也就只有 $\sqrt n$ 种 $d$，所以暴力预处理的时间复杂度也只有 $O(n\sqrt n)$。
空间复杂度同样为 $O(n\sqrt n)$。
但是是暴力。而且不用设阈值。
G.Mischievous Shooter
待补。