2020-2021:teams:hotpot:codeforces_round
|
2020-2021:teams:hotpot:codeforces_round [2020/05/15 16:42] 喝西北风 创建 |
2020-2021:teams:hotpot:codeforces_round [2020/05/15 17:18] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | === | + | ====A - Most Unstable Array==== |
| + | |||
| + | ===题意=== | ||
| + | |||
| + | 给定n和m。问长度为n且总和为m的非负整数数列，相邻两项差的绝对值之和最大为多少。 | ||
| + | |||
| + | ===思路=== | ||
| + | |||
| + | 贪心。n=1时答案为0，n=2时答案为m，n>2时答案为2m | ||
| + | |||
| + | ====B - Two Arrays And Swaps==== | ||
| + | |||
| + | ===题意=== | ||
| + | |||
| + | 水题，过 | ||
| + | |||
| + | ===思路=== | ||
| + | |||
| + | 略 | ||
| + | |||
| + | ====C - Board Moves==== | ||
| + | |||
| + | ===题意=== | ||
| + | |||
| + | $n\times n$的方格，每个格子内有一个棋子。每次移动可以将一枚棋子移动到相邻的八个格子中的一个。每个格子中棋子最大数不限。现要将所有棋子移动到一个格内。问最少移动步数。 | ||
| + | |||
| + | 保证n是奇数 | ||
| + | |||
| + | ===思路=== | ||
| + | |||
| + | 显然，最优策略是将所有棋子移到中间。然后随便推一推即可。 | ||
| + | |||
| + | ====D - Constructing the Array==== | ||
| + | |||
| + | ===题意=== | ||
| + | |||
| + | 长度为n的数列一开始全是0。第i次操作，将最长的全为0的子段的中间改为i。求最终的数列。 | ||
| + | |||
| + | ===思路=== | ||
| + | |||
| + | 用堆存下所有长度为0的子段。每次取出最长的，修改中间，并将两边再放进堆。 | ||
| + | |||
| + | ====E - K-periodic Garland==== | ||
| + | |||
| + | ===题意=== | ||
| + | |||
| + | 长度为n的灯，给定开关状态。再给定k。现要求开/关某些灯，使得最终任意两个相邻的开着的灯距离都为k。求最少开关次数。 | ||
| + | |||
| + | ===思路=== | ||
| + | |||
| + | s1，s2分别记录原先开着的灯的前缀、后缀和。dp[i]表示，只考虑前i盏灯，且必须开第i盏灯的最小开关次数。 | ||
| + | |||
| + | 若i原先开着，$dp[i]=\min(dp[i-k]+s1[i-1]-s1[i-k],s1[i-1])$，否则$dp[i]=\min(dp[i-k]+s1[i-1]-s1[i-k],s1[i-1])+1$。 | ||
| + | |||
| + | 最终答案为$\min(dp[i]+s2[i+1],s1[n])$ | ||
| + | |||
| + | ====F - Decreasing Heights==== | ||
| + | |||
| + | ===题意=== | ||
| + | |||
| + | $n\times m$的格子，每个格子给定一个高度。要从(1,1)走到(n,m)，只能往下或右走，且只能走到比当前高1的格子。花费1的代价可以让一个格子高度减1，问使得存在合法路径的最低花费 | ||
| + | |||
| + | ===思路=== | ||
| + | |||
| + | 最优策略下，最终的合法路径上，一定有一个格子没有更改高度。 | ||
| + | |||
| + | 枚举每个格子，要求不更改其高度且强制走过这个格子。对每种情况，可以dp求出最小花费（或不存在这种可能）。 | ||
2020-2021/teams/hotpot/codeforces_round.1589532135.txt.gz · 最后更改: 2020/05/15 16:42 由 喝西北风
