这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:hotpot:2020nowcoder2 [2020/07/17 15:21] misakatao 更新 |
2020-2021:teams:hotpot:2020nowcoder2 [2020/07/17 17:11] (当前版本) misakatao 更新 |
||
---|---|---|---|
行 117: | 行 117: | ||
===题意=== | ===题意=== | ||
- | 有一个区间$[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]$,如果能,最小化费是多少 | + | 有一个区间$[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]$,如果能,最小花费是多少 |
===数据范围=== | ===数据范围=== | ||
行 152: | 行 152: | ||
* 要注意循环中的变量问题 | * 要注意循环中的变量问题 | ||
+ | * gcd除了可以用log的时间单独求以外还可以用$O(n^2)$的时间预处理1到$n$之间两两之间的gcd |