CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2020/07/10 – 2020/07/10 周报 ======

<html><br/></html>

===== 团队训练 =====

  * 2020.08.08 [[https://ac.nowcoder.com/acm/contest/5674|2020牛客暑期多校训练营（第九场）]] ''%%pro: 6/6/12%%'' ''%%rk: 88/975%%''

  * 2020.08.10 [[https://ac.nowcoder.com/acm/contest/5675|2020牛客暑期多校训练营（第十场）]] ''%%pro: 3/3/10%%'' ''%%rk: 135/906%%''


<html><br/></html>

===== 李英龙 =====

==== 专题 ====

无

==== 比赛 ====

无

==== 题目 ====

无

<html><br/></html>

===== 陈源 =====

==== 专题 ====

无

==== 比赛 ====

[[cf662cy|Codeforces Round 662 div2]]    ''%%pro:4/6%%'' 

[[cf663cy|Codeforces Round 663 div2]]    ''%%pro:4/5%%''
==== 题目 ====

无

<html><br/></html>

===== 胡琎 =====

==== 专题 ====

无

==== 比赛 ====

[[2020-2021:teams:too_low:cf1395_hj|Codeforces Round 664 Div2
]]
==== 题目 ====

无

<html><br/></html>

===== 本周推荐 =====

==== 李英龙 ====

[[https://blog.csdn.net/dragonylee/article/details/107895708|ACM算法总结 prufer序列]]

==== 陈源 ====

CF1391E-Pairs of Pairs

**题意：**给定一个联通图，无重边无自环，保证以下两个条件只满足一个

  - 存在一条简单路径（路径上每个点只经过一次），这条简单路径覆盖了至少n/2向上取整个点
  - 可以从图中选出至少n/2向上取整个点，将其两两分组，任意两组点(A,B),(C,D)，原图中这四个点的诱导子图，至多有两条边。

如果满足第一个则输出路径上的点，满足第二个则输出分组。


这道题利用了图的dfs树，dfs树就是平时tarjan算法用的那个，之前基本都是当作黑盒算法来用的，dfs树可以用来解决一些和tarjan算法看起来关系不大的问题，也是解决仙人掌问题的利器。

==== 胡琎 ====

Codeforces 1394B - Boboniu Walks on Graph 
 
题意：对于一个每个点出度最大为k，最小为1的点有向图，寻找（c1,...,ck）的种数，使得当出度为i的点的出边中，至保留第ci小的边时，图中的每个点都可走n步回到该点。k <= 9, n <= 2e5. 

要满足的条件等价于每个点都位于一个回路中。由于仅保留n条边，因此也等价于保留的边终点并集为整个图。记录出度为k的点选c时集合，枚举k!种情况，使用哈希函数判断是否为整个图。注意哈希函数需要满足结合律。 

Tag：Hash 

Comment：一个需要使用哈希函数的判断集合求并相等的例子。
CVBB ACM Team

用户工具

站点工具

页面工具
