2020-2021:teams:farmer_john:2sozx:codeforces_round_668_div._1
B
- 题意:给一棵树，$A,B$ 两人做游戏，各有一个起点，每个人都有一个步长 $da,db$ ，表示一次最多移动的距离，$A$ 先移动，如果$A$ 遇到了 $B$ 则 $A$ 获胜，否则 $B$ 获胜，游戏进行无穷次。
- 题解:先判断 $A,B$ 两点距离是否小于等于 $da$，在判断直径与 $2\times da$ 的关系，如果直径长度小于等于 $2\times da$ 则 $A$ 两次操作后必能遇到 $B$，否则直接判断 $db$ 与 $2\times da$ 的关系即可。
C
- 题意:给定一个序列 $a$ 每次可以删除一个满足 $a_i = i$ 得位置 $i$，后面的数依次向前移，每次询问一个区间，区间外得数不可被删除，问最多能删除多少个数。
- 题解:预处理出每个数在左侧最多多少数被删除后依旧可以被删除即可，预处理可以用二分加主席树维护，查询直接用主席树即可。
D
- 题意:一道让人自闭的交互题，调不对了，溜了溜了。
- 题解:溜了溜了
E
- 题意:给定一个 $nm$ 的网格图，问用最少多少个 $1\times x$ 或者 $x\times 1$ 的砖头能够覆盖网格图上所有的 $\#$ ，其中 $x$ 任意，每个砖头长度可以不一致，砖头不能重叠，$n,m\le 200$
- 题解:显然最劣的方案是全部都用 $1\times 1$ 的矩形，每次合并一个边可以让答案减一。考虑 $L$ 型，显然这种形状必然会用两个砖头，因此考虑每个冲突的 $L$ 型，将 $L$ 型拐弯处的矩形上右两侧连边，因此减去图中的最大独立集即可。
2020-2021/teams/farmer_john/2sozx/codeforces_round_668_div._1.txt · 最后更改: 2020/10/06 10:17 由 2sozx
