2020-2021:teams:hotpot:200815-200821
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:200815-200821 [2020/08/21 17:11] lotk |
2020-2021:teams:hotpot:200815-200821 [2020/08/23 13:13] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 45: | 行 45: | ||
| =====题目===== | =====题目===== | ||
| - | 本周无 | + | *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，只需看对应的哈希乘积是不是所有点的乘积即可。 | ||
| ======本周推荐====== | ======本周推荐====== | ||
2020-2021/teams/hotpot/200815-200821.1598001102.txt.gz · 最后更改: 2020/08/21 17:11 由 lotk
