2020-2021:teams:hotpot:200711-200717
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:200711-200717 [2020/07/17 17:09] misakatao 更新 |
2020-2021:teams:hotpot:200711-200717 [2020/07/17 17:16] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 100: | 行 100: | ||
| 推荐理由：这种表面上范围很大的题目，很多时候可以考虑第一步的特殊情况进行处理，达到从第二步开始范围就缩小的效果。这种思想极其重要，运用也较为广泛（像是区间取根号）。 | 推荐理由：这种表面上范围很大的题目，很多时候可以考虑第一步的特殊情况进行处理，达到从第二步开始范围就缩小的效果。这种思想极其重要，运用也较为广泛（像是区间取根号）。 | ||
| - | 陶吟翔： | + | 陶吟翔：[[https://ac.nowcoder.com/acm/contest/5667/I|传送门]] |
| + | |||
| + | 题目大意：有一个区间$[1,n]$，现在可以进行操作把区间$[l,r]$变成$[l-1,r],[l,r-1],[l+1,r]$或$[l,r+1]$，但是一旦区间变成$[l,l]$就不能再变，现在有$m$个选择，你可以花费$c$把某一个区间$[l,r]$向$[l-1,r]$或$[l,r-1]$的操作禁止，问能不能完全避免把区间变成$[l,l]$，如果能，最小花费 | ||
| + | |||
| + | 数据范围：$2 \le n \le 500$，$0 \le m \le n(n-1)$，$1 \le c \le 10^6$ | ||
| + | |||
| + | 解题思路：可以把整个过程看作在一个$n \times n$的网格上从$(1,n)$走向对角线，我们可以断开其中某些地方使得不能从起点走到对角线上，这显然是一个最小割模型，考虑到这道题数据规模较大而图又比较规则，所以我们可以采取建对偶图的方式求解 | ||
| + | |||
| + | 推荐理由：这道题看似是一道区间题，但是可以通过转化将其与最小割模型建立联系，考察了做题者对模型进行转化和理解的能力，并且本题建立对偶图虽然有多种方式，但是都必须要保证从起点到终点所经过的一条路径能够组成一组割，考察了做题者对对偶图的理解。 | ||
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200711-200717.1594976970.txt.gz · 最后更改: 2020/07/17 17:09 由 misakatao
