2020-2021:teams:hotpot:200711-200717
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200711-200717 [2020/07/17 14:54] misakatao 更新 |
2020-2021:teams:hotpot:200711-200717 [2020/07/17 17:16] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 无 | ||
| =====比赛===== | =====比赛===== | ||
| + | 2020.07.11 [[tyxaisingprogrammingcontest2020|AIsing Programming Contest 2020]] ''prob:4/5/6'' ''rank:590'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | *atcoder E - Camel Train | ||
| + | *分类：贪心 | ||
| + | *题目大意：对于一个队列，里面每个元素有 $li,ri,ki$ 三个量。当期排在前 $ki$ 时价值为 $li$, 否则为 $ri$, 求一个序列最大化价值。 | ||
| + | *题目解法：我们对其按 $li-ri$ 正负进行分类再按k从小到大/从大到小排序，并分别从前后用小根堆来进行贪心即可（随时保证堆内元素小于等于 $ki$ 个或是 $n-ki$ ） | ||
| ======陶吟翔====== | ======陶吟翔====== | ||
| 行 51: | 行 58: | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | [[矩阵树|矩阵树定理]] | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.07.11 [[tyxaisingprogrammingcontest2020|AIsing Programming Contest 2020]] ''prob:4/5/6'' ''rank:826'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | *Codeforces Round #655 (Div. 2) C - Omkar and Baseball | ||
| + | *分类：思维 | ||
| + | *题目大意：给定一个1到n的排列，一次操作选中连续的一段，改变其中每个元素的位置（不能还在原来的位置）。问最少几次操作使其递增。 | ||
| + | *数据范围：$1 \le n \le 10^5$ | ||
| + | *解题思路：对任意一段，我们一定可以通过一次操作使得$a_i\neq i$ | ||
| + | *Comment：不是很难 | ||
| + | |||
| + | *Codeforces Round #655 (Div. 2) D - Omkar and Circle | ||
| + | *分类：思维 | ||
| + | *题目大意：给定一个长度为2n+1的环。每次操作，可以选中一个数，用它两边的数之和代替这个数，并删除它两边的数。最终只会剩一个数，问这个数最大是多少 | ||
| + | *数据范围：$1 \le n \le 10^5$ | ||
| + | *解题思路：显然，最终的结果一定是这个序列中若干元素之和。可以证明，这些元素最多有一组在原先数列中是相邻的。所以只需要看是哪组相邻，然后剩下的隔一个选一个。 | ||
| + | *Comment：结论很难想 | ||
| + | | ||
| + | *Codeforces Round #655 (Div. 2) E - Omkar and Circle | ||
| + | *分类：区间dp | ||
| + | *题目大意：n行m列的方格，每行被划分为连续的若干块。在每块中选一个地方填1。设第i列有$q_i$个1，使得$\sum^n_1q_i^2$最大。求这个最大值 | ||
| + | *数据范围：$1\le m,n\le 100$ | ||
| + | *解题思路：大致的思路是区间dp。dp[i][j]表示所有完整包含在[i,j]列的块所能做出的贡献，最终答案即为dp[1][m]。首先证明，在最优策略中，对于[i,j]区间，一定存在一列k，满足所有完整包含在[i,j]列且覆盖k的块都在k填了1。因为我们显然希望1尽量地聚集，我们选择1最多的一列，将其他列的1移到这一列，一定使结果变优。所以$dp[i][j]=max\{dp[i][k-1]+dp[k+1][j]+(num[i][j]-num[i][k-1]-num[k+1][j])^2\}$，其中num[i][j]表示在[i,j]列内的块数。 | ||
| + | *Comment：很好的区间dp | ||
| ======本周推荐====== | ======本周推荐====== | ||
| 行 60: | 行 92: | ||
| 林星涵： | 林星涵： | ||
| - | 陶吟翔： | + | [[https://atcoder.jp/contests/aising2020/tasks/aising2020_d|题目链接]] |
| + | |||
| + | 题目大意：给一个 $N \le 200000$ 位的二进制数，定义 $f(x)$ 为这个数除以其二进制中 1 的个数的余数。问依次将其每位的0、1互换，得到的数需要经过几次 $f(x)$变为0. | ||
| + | |||
| + | 解题方法：我们不难发现这种变的方式 1的个数只会进行正负1的变化，这样的话我们只用对两个模数进行预处理。第一次取模之后数据范围变小便可以进行暴力处理。 | ||
| + | |||
| + | 推荐理由：这种表面上范围很大的题目，很多时候可以考虑第一步的特殊情况进行处理，达到从第二步开始范围就缩小的效果。这种思想极其重要，运用也较为广泛（像是区间取根号）。 | ||
| + | |||
| + | 陶吟翔：[[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)$走向对角线，我们可以断开其中某些地方使得不能从起点走到对角线上，这显然是一个最小割模型，考虑到这道题数据规模较大而图又比较规则，所以我们可以采取建对偶图的方式求解 | ||
| + | |||
| + | 推荐理由：这道题看似是一道区间题，但是可以通过转化将其与最小割模型建立联系，考察了做题者对模型进行转化和理解的能力，并且本题建立对偶图虽然有多种方式，但是都必须要保证从起点到终点所经过的一条路径能够组成一组割，考察了做题者对对偶图的理解。 | ||
| 郭衍培： | 郭衍培： | ||
| + | |||
| + | [[http://codeforces.com/contest/1372/problem/E|题目链接]] | ||
| + | |||
| + | 题目大意：n行m列的方格，每行被划分为连续的若干块。在每块中选一个地方填1。设第i列有$q_i$个1，使得$\sum^n_1q_i^2$最大。求这个最大值 | ||
| + | |||
| + | 数据范围：$1\le m,n\le 100$ | ||
| + | |||
| + | 解题思路：大致的思路是区间dp。dp[i][j]表示所有完整包含在[i,j]列的块所能做出的贡献，最终答案即为dp[1][m]。首先证明，在最优策略中，对于[i,j]区间，一定存在一列k，满足所有完整包含在[i,j]列且覆盖k的块都在k填了1。因为我们显然希望1尽量地聚集，我们选择1最多的一列，将其他列的1移到这一列，一定使结果变优。所以$dp[i][j]=max\{dp[i][k-1]+dp[k+1][j]+num[i][j][k]^2\}$ | ||
| + | |||
| + | 推荐理由：这道题其实不难想要采用区间dp，但在dp过程中，状态和转移都不太好想，尤其是转移。转移需要一个结论，而这个结论我一开始没有想到。事实上，这刚看到题解的时候（题解无证明），我甚至还感到惊讶。但仔细一想，其实并不是很难，这需要对这个模型有一定的理解，发现取到最优情况时的一个性质。 | ||
2020-2021/teams/hotpot/200711-200717.1594968894.txt.gz · 最后更改: 2020/07/17 14:54 由 misakatao
