0%

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. $ 可能形式化之后反而不太清楚了,可以去看看原题面。

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

Read more »

AGC002 F Leftmost Ball

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

$n,k\le 2000$

Read more »

ARC106 E Medals

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

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

感谢hehezhou 的指导。

Read more »

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$

Read more »

LOJ 6289 花朵

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

你看那,陌上花

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

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

Read more »

浅析伪多项式复杂度的基于带势的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$相关,其仍是伪多项式复杂度算法。

Read more »