2020-2021:teams:hotpot:200711-200717
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200711-200717 [2020/07/17 17:04] 喝西北风 |
2020-2021:teams:hotpot:200711-200717 [2020/07/17 17:16] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 无 | ||
| =====比赛===== | =====比赛===== | ||
| 行 17: | 行 19: | ||
| =====题目===== | =====题目===== | ||
| - | *atcoder E - Camel Train | + | *atcoder E - Camel Train |
| - | + | *分类：贪心 | |
| - | *分类：贪心 | + | *题目大意：对于一个队列，里面每个元素有 $li,ri,ki$ 三个量。当期排在前 $ki$ 时价值为 $li$, 否则为 $ri$, 求一个序列最大化价值。 |
| - | *题目大意：对于一个队列，里面每个元素有 $li,ri,ki$ 三个量。当期排在前 $ki$ 时价值为 $li$, 否则为 $ri$, 求一个 | + | *题目解法：我们对其按 $li-ri$ 正负进行分类再按k从小到大/从大到小排序，并分别从前后用小根堆来进行贪心即可（随时保证堆内元素小于等于 $ki$ 个或是 $n-ki$ ） |
| - | 序列最大化价值。 | + | |
| - | *题目解法：我们对其按 $li-ri$ 正负进行分类再按k从小到大/从大到小排序，并分别从前后用小根堆来进行贪心即可（随时 | + | |
| - | 保证堆内元素小于等于 $ki$ 个或是 $n-ki$ ） | + | |
| ======陶吟翔====== | ======陶吟翔====== | ||
| 行 101: | 行 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.1594976678.txt.gz · 最后更改: 2020/07/17 17:04 由 喝西北风
