2020-2021:teams:acm_life_from_zero:8.8-8.14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:8.8-8.14 [2020/08/14 17:05] lak [李元恺] |
2020-2021:teams:acm_life_from_zero:8.8-8.14 [2020/08/14 18:12] (当前版本) lak [姜维翰] |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| + | 小学期咕咕咕 | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| =====比赛===== | =====比赛===== | ||
| 行 23: | 行 23: | ||
| [[https://codeforces.com/contest/1394/problem/B|CF1394B]] | [[https://codeforces.com/contest/1394/problem/B|CF1394B]] | ||
| - | 题意：一张n点m边有向图（n,m~1e5），每个点最多k条边（$k \leq 9$） | + | tag：图论、搜索 |
| + | |||
| + | 题意：一张n点m边有向由边权图（n,m~1e5），每个点最多k条边（$k \leq 9$）,对于一个长度为k的数组{$c_k$}，满足$c_i \leq i$，定义图对其的转移：一个点，若出度为x，则走边权第$c_x$小的出边。求有多少个${c_k}$满足任意一个点出发经过有限步可以返回出发点。 | ||
| + | |||
| + | 思路：对于一个合法转移，每个点都在一个简单环内，即每个点的入度都必须为1，于是对于每个点的任意两个入边，可以得到一个四元组$(c_i,c_j,v_i,v_j)$表示$c_i = v_i,c_j = v_j$不能同时发生。预处理一下所有的四元组，然后O(k!k)暴搜所有解判断是否合法即可。 | ||
| + | |||
| + | comment:一道解法众多的题，上面只是一种可以通过的解法。 | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| [[https://codeforces.com/contest/1393/problem/E1|cf1393E Twilight and Ancient Scroll]] | [[https://codeforces.com/contest/1393/problem/E1|cf1393E Twilight and Ancient Scroll]] | ||
2020-2021/teams/acm_life_from_zero/8.8-8.14.1597395957.txt.gz · 最后更改: 2020/08/14 17:05 由 lak
