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