目录
开坑 主要是cf和atcoder 记录一下非水题
CF1404B
题意
博弈论，两人轮流在树上跑，每次分别可以移动不超过 $da$ 和 $db$ 的距离，问先手能不能追到后手。
题解
三种情况必胜：
- 两者距离不超过 $da$。
- $2 \times da \ge db$，以 $a$ 为根往下逼近即可。
- $2 \times da \ge \text{diameter}$，卡中点即可。
证明我吐了，有时间再来补。
CF1404C
题意
给定一个序列 $a_i$，如果 $a_i = i$，那么你可以将它删掉，多次询问如果强制前 $x$ 个数和后 $y$ 个数都不能删，最多能删几个数。
题解
发现问题的可二分性，巨佬题解。
设 $\text{lim}_i$ 表示如果禁止删除的长度 $\le \text{lim}_i$，那么该位置可以被删，否则不能被删。
考虑二分求解，对于我们正在二分的 $\text{mid}$，等价于求前面满足 $\text{lim}_j \ge \text{mid}$ 的有多少个，这个过程可以使用主席树优化到 $O(n \log n)$。
对于询问，直接询问 $[1,n-y]$ 中 $\text{lim}_i \ge x$ 的个数即可，主席树上查询即可。
CF1404D
题意
交互题，给定 $1$ 到 $2n$ 共 $2n$ 个数，你可以选择当 A 或 B。
- A 要将 $2n$ 个数两两一组分为 $n$ 个。
- B 要在上述 $n$ 组中每组选一个使得选择数之和是 $2n$ 的倍数。
你需要选择一个角色扮演并获胜。
题解
- $n$ 为偶数，根据奇偶分析可以得到 $$\frac{n(n+1)}{2} \equiv \frac{n}{2} \pmod n$$ 只要按照 $(i, i + n)$ 的方式分，就可以保证结果在模 $n$ 意义下不为 $0$，那么在模 $2n$ 意义下更不可能为 $0$，因此选 A 必胜。
- $n$ 为奇数，对于 A 给出的一种方案，我们将每组之间的两点连红边，在 $(i, i + n)$ 之间连蓝边，如下图所示，那么我们黑白染色后选黑点，可以发现选的所有点在模 $n$ 意义下两两不同，根据奇偶分析，有 $$\frac{n(n+1)}{2} \equiv 0 \pmod n$$ 因此选 A 必胜。
CF1404E
题意
给定一个 $n \times m$ 的方格图，分黑白格，要求用 $1 \times x$ 和 $x \times 1$ 的砖块铺满所有黑格，白格不能放砖，且所有砖不能重叠，问最少需要多少砖。
题解
考虑一开始一个黑格放一个砖块，然后进行合并，砖块不能拐弯合并等价于求如下二分图的最大独立集。
CF1406D
题意
给定一个序列 $a_i$，将其拆分成两个序列 $b_i$ 和 $c_i$，要求满足 $a_i=b_i+c_i$，且 $b_i$ 递增，$c_i$ 递减。求 $\max(b_i,c_i)$ 的最小值。多组询问，每次对 $a_i$ 进行区间加。
