Warning: session_start(): open(/tmp/sess_7c3f47346eade2a332ff1ef4c2852720, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
======= 2020/08/08-2020/08/14周报 =======
====== 团队训练 ======
====== 李元恺 ======
=====题目=====
=====比赛=====
[[http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=892|2020 年百度之星·程序设计大赛 - 复赛]] ''rk:69 pros:3/6''
[[https://codeforces.com/contest/1394|Codeforces Round #664 (Div. 1)]] ''rk:131 pros:2/5''
====== 姜维翰 ======
小学期咕咕咕
====== 袁熙 ======
=====比赛=====
[[https://codeforces.com/contest/1395|Codeforces Round #664 (Div. 2)]] \\
[[https://codeforces.com/contest/1391|Codeforces Round #663 (Div. 2)]]
====== 本周推荐 ======
====== 李元恺 ======
[[https://codeforces.com/contest/1394/problem/B|CF1394B]]
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]]
tag:hash,dp
题意：给n个词构成的串，词之间按字典序不降，可以选择对每个词进行一次操作：在某个字母后添加一个字母之后选择某个词。之后，选择一个词，撤销此操作。问操作后可能产生的串的不同版本数量
思路:考虑dp时，对相邻的两个词$S_1,S_2$，在题意的操作下分别产生$|S_1|+1，|S_2|+1$个子串。如果对子串排序后，对$S_2$的每个子串，可以二分找到合法的$S_1$的子串数量，完成转移。为了在转移时找到合法子串的数量，还需要对每个词hash一下。
comment:补之前的题（ 大概是常规的dp
====== 姜维翰 ======