本周无

ac自动机

本周无

本周无

树上差分

本周无

本周无

本周无

本周无

• 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$的图上进行。首先肯定不可能是连通块相关算法，所以我们要想非树边的性质，我们的要求是删掉一条树边和一条非树边使得图不连通，单独考虑树的话，只需要随便删掉一条边就不连通了，所以我们只需要保证删掉一条非树边以后不会有其它非树边覆盖我们要选的树边。问题转化成对树边的路径加并且只有一次询问，使用树上差分解决即可。

推荐理由：考察了做题者的问题转化能力，转化后是树上差分的经典题目，细节处理和对答案的统计也需要做题者谨慎

郭衍培：

题目大意：给定n的点的树树，每个点有两个权值h,t。将所有边分成若干个集合，要求每个集合内的边构成一条路径，且路径上点的h不减。每个集合的代价为路径上所有点的t之和。求最小总代价。

数据范围：$n\le 2\times 10^5$,$1\le h,t\le 10^6$

解题思路：可以将树上的边看成有向的，由h较小的指向h较大的。每个点会被计算max{in,out}次，in，out分别表示点的入度和出度。但问题在于两端点h相同的边如何处理。先去掉已经确定方向的边，留下一个森林。对于剩下的每棵树，dp1[i]表示从i节点指向其父亲节点，i节点子树的最小代价，dp2[i]表示从i节点父亲指向i的最小代价。计算一个节点的dp值时，枚举子节点中指向它的个数。将子节点按照dp1-dp2排序，从小到大依次加入。

推荐理由：问题的转化，dp的方法都很巧妙。