2020-2021:teams:hotpot:200509-200515
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200509-200515 [2020/05/15 17:47] lotk |
2020-2021:teams:hotpot:200509-200515 [2020/05/15 19:23] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 20: | 行 20: | ||
| [[tarjan|Tarjan]] | [[tarjan|Tarjan]] | ||
| + | |||
| + | ====题目==== | ||
| + | |||
| + | * Codeforces641Div2-E（同本周推荐） | ||
| + | * Codeforces642Div2-D | ||
| + | * 题目大意：给出一串数，每次可以把区间$[l,r]$中得数变成其中得中位数（若长度为偶数则取小的），问能否在有限次把所有数变成$k$。 | ||
| + | * 解题思路：首先数列中一定要有$k$，然后发现只要能够找到一个大于等于$k$的数并且是其与$k$相邻即可，所以任意相邻的三个数中只要有两个数大于等于$k$，我们就可以变化出一个大于等于$k$的数，然后我们一步一步扩展到一个$k$旁边即可。 | ||
| =====郭衍培===== | =====郭衍培===== | ||
| - | [[Burnside引理和Polya定理|置换群论]] | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | [[Burnside引理和Polya定理|置换群论]] | ||
| =====本周推荐===== | =====本周推荐===== | ||
| 行 31: | 行 39: | ||
| 郭衍培：一棵树n个点中选m个，要求不能有孤立点（即每个被选的点旁边还有选中的点），求方案数。dp0[i][j]表示i的子树中选j个，且根节点不选的合法方案数；dp1[i][j]表示i的子树中选j个，根节点选中且子树中有与根连接的点被选中的合法方案数；dp2[i][j]表示i的子树中选j个，根节点选中且子树中无与根连接的点被选中的合法方案数。递推的时候，对根节点的每个子节点，类似01背包（取max改为加）。最终答案为dp0[1][m]+dp1[1][m]。[[https://nanti.jisuanke.com/t/A1362|这里是网址]] | 郭衍培：一棵树n个点中选m个，要求不能有孤立点（即每个被选的点旁边还有选中的点），求方案数。dp0[i][j]表示i的子树中选j个，且根节点不选的合法方案数；dp1[i][j]表示i的子树中选j个，根节点选中且子树中有与根连接的点被选中的合法方案数；dp2[i][j]表示i的子树中选j个，根节点选中且子树中无与根连接的点被选中的合法方案数。递推的时候，对根节点的每个子节点，类似01背包（取max改为加）。最终答案为dp0[1][m]+dp1[1][m]。[[https://nanti.jisuanke.com/t/A1362|这里是网址]] | ||
| + | |||
| + | 林星涵：Codeforces642Div3-F,$n\times m$的格子，每个格子给定一个高度。要从(1,1)走到(n,m)，只能往下或右走，且只能走到比当前高1的格子。花费1的代价可以让一个格子高度减1，问使得存在合法路径的最低花费。思路:最优策略下，最终的合法路径上，一定有一个格子没有更改高度。枚举每个格子，要求不更改其高度且强制走过这个格子。对每种情况，可以dp求出最小花费（或不存在这种可能）。[[https://codeforces.com/contest/1353/problem/F|这里是网址]] | ||
2020-2021/teams/hotpot/200509-200515.1589536043.txt.gz · 最后更改: 2020/05/15 17:47 由 lotk
