0%

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 »

城市游行

给一棵树,点有点权。求两点间的路径上任取两点的距离(定义为点权和)的期望。要支持连边断边,链修改。
$n\le 10^5$

Read more »

「雅礼集训 2017 Day1」字符串

题意:定义 $ f(S,T) $ 为 $ T $ 在 $ S $ 中的出现次数。

给串 $ S $ , $ m $ 个区间 $ [l_i,r_i] $ 和长度 $ k $ ,你要回答 $ Q $ 个询问,每次询问给一个长度为 $ k $ 的串 $ T $ 和上下界 $ a,b $ ,求

$ n,m,k,Q\le 10^5,kQ\le 10^5 $

Read more »