Luogu P7046 「MCOI-03」诗韵

给一个串 $ T $ ，和一个大小为 $ m $ 的子串集合 $ \{T[l_i,r_i]|1\le i\le m\} $ ,记为 $ S $ .和一个定值 $ K $ .

定义 $ \text{CS}(A) $ 表示 $ A $ 中所有串的CS（公共后缀）的集合。

求 $ |{\bigcup_{A\subset S,|A|>K}}\ \text{CS(A)}| $ 和 $ \max_{A\subset S,|A|>K}\max(\text{CS(A)}) $ .

$ |T|\le 5\times 10^5,m\le 5\times 10^5,0\le K\le m. $ 可能形式化之后反而不太清楚了，可以去看看原题面。

这里介绍一种重工业做法。

CSP2019 Day2 题解

CSP2019 Day1 题解

等我，等我。

AGC002 F Leftmost Ball

有$n$种不同颜色的球，每种球有$k$个。求将这些球排成一排，每种颜色的最左侧的球染成白色后得到的不同的排列数量,模$10^9+7$。

$n,k\le 2000$

ARC106 E Medals

有$n$个职工，第$i$个（从第一天开始）连续工作$a_i$天,然后连续休息$a_i$天，并重复该过程。每天，你可以给至多一名来工作的职工发至多一个奖章。求至少要多少天后，所有员工都有至少$k$个奖章。

$n\le 18,k,a_i\le 10^5$

感谢hehezhou 的指导。

LOJ 2092 「ZJOI2016」大森林

题意：有$n$棵树，初始都只有点1，每棵树有一个“生长节点”，初始也为1.

有三种操作：

1. $[l,r]$中所有树的生长节点下面都长一个点，编号为1操作次数+1.
2. $[l,r]$中所有树的生长节点都变为$x$ （不影响没有点$x$的树）
3. 询问树$x$上$u,v$的距离，保证树$x$存在点$u,v$.

$n\le 10^5,Q\le 2\times 10^5$

LOJ 6289 花朵

好久没有这样独自写一道有意思的题了～

你看那，陌上花

题意：给一棵$n$个点的树，有点权$a_i$。定义一个独立集的权值为点权的乘积，求所有大小为$m$的独立集的权值之和模998244353。

$n,m\le 8\times 10^4,0\le a_i<998244353$

CSP2020联考 Day4

这场质量挺好。

概率期望学习

为了ZJOI2020不要死的太难看，恶补概率期望。

浅析伪多项式复杂度的基于带势的Dijkstra算法的费用流

1.introduction

常见的费用流解法为用SPFA/Bellman_Ford 算法求解最小费用增广路，然后沿着该增广路增广，重复该过程直至增广路不存在。其复杂度为$\Omega(mf),O(nmf)$（其中$f$为流量，下同）

随机数据下其表现良好，但在网格图等特殊图中效率较低。如「NOIP2020联考Day2 撤离」中，该算法难以得到超过80分。

此外，学术界已有$O(m^2\log m\log f)$的弱多项式复杂度费用流解法。但其在流量较小时表现不佳。

本文将介绍伪多项式复杂度的基于带势的Dijkstra算法的费用流，其复杂度上为$O(m\log m *f)$ 。由于与$f$相关，其仍是伪多项式复杂度算法。