2020-2021:teams:hotpot:200815-200821
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200815-200821 [2020/08/21 13:07] 喝西北风 |
2020-2021:teams:hotpot:200815-200821 [2020/08/23 13:13] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====专题===== | =====专题===== | ||
| - | 本周无 | + | [[ac自动机|ac自动机]] |
| =====比赛===== | =====比赛===== | ||
| + | 本周无 | ||
| =====题目===== | =====题目===== | ||
| 行 22: | 行 23: | ||
| =====专题===== | =====专题===== | ||
| - | 本周无 | + | [[treediff|树上差分]] |
| =====比赛===== | =====比赛===== | ||
| 行 30: | 行 31: | ||
| =====题目===== | =====题目===== | ||
| + | 本周无 | ||
| ======郭衍培====== | ======郭衍培====== | ||
| 行 39: | 行 41: | ||
| =====比赛===== | =====比赛===== | ||
| + | 本周无 | ||
| =====题目===== | =====题目===== | ||
| - | 本周无 | + | *Codeforces Round #664(Div.1) - Boboniu Walks on Graph |
| + | *分类：图、哈希 | ||
| + | *题目大意：给定一个n个点m条边的有向图。每个点的出度最大为k，每条边的权值各不相同。对于序列$\{c_k\}$，满足$1\le c_i \le i$。设点u的出度为i，则要求从u走其边权第i小的边。问有多少种c，使得从图上任意一点都能走回来。 | ||
| + | *数据范围：$1\le k\le 9$，$1\le n,m\le 2\cdot 10^5$ | ||
| + | *题目解法：首先证明，对于一个c，满足题目中的要求等价于每个点都能被走到，也就等价于每个点都被走到一次（因为是n个点走到n个点）。必要性显然，下面证明充分性。这可以看做一个n个点的置换。由于置换一定是若干个环，因此每个点都能走回自己。那么接下来就是枚举所有c看哪些符合这个要求。hash[i][j]表示若$c_i=j$，所有度为i的点指向的点的乘积模一个数。对于一个c，只需看对应的哈希乘积是不是所有点的乘积即可。 | ||
| ======本周推荐====== | ======本周推荐====== | ||
| - | 林星涵： | + | 林星涵：[[ac自动机]] |
| - | + | ||
| - | 题目大意： | + | |
| - | + | ||
| - | 数据范围： | + | |
| - | + | ||
| - | + | ||
| - | 解题思路： | + | |
| - | 推荐理由： | + | 推荐理由：模式串匹配基础模板 |
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：给出一个有$n$个点的树，$m$此操作，每次操作新加一条非树边，问最后有多少种方法使得删掉一条树边，一条非树边使得这个图不连通。 |
| - | 数据范围： | + | 数据范围：$1 \le n,m \le 10^5$ |
| - | 解题思路： | + | 解题思路：我们可以确定是一个边数最多有$2 \times 10^5$的图上进行。首先肯定不可能是连通块相关算法，所以我们要想非树边的性质，我们的要求是删掉一条树边和一条非树边使得图不连通，单独考虑树的话，只需要随便删掉一条边就不连通了，所以我们只需要保证删掉一条非树边以后不会有其它非树边覆盖我们要选的树边。问题转化成对树边的路径加并且只有一次询问，使用树上差分解决即可。 |
| - | 推荐理由： | + | 推荐理由：考察了做题者的问题转化能力，转化后是树上差分的经典题目，细节处理和对答案的统计也需要做题者谨慎 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200815-200821.1597986451.txt.gz · 最后更改: 2020/08/21 13:07 由 喝西北风
