HNOI2019 退役记

GXZlegend:不要想着day2能够翻盘,因为你永远不知道盘是什么样子

hnoi组委会真实事屑

线性递推小结

问题

给定$n,k,f_0\dots f_{k-1},a_1\dots a_{k}$,定义$f_n=\sum_{i=1}^k f_{n-i}a_i$,求$f_n$。

CF1229E

题意

给定一张n+n的二分图,每条边有$p_{i,j}$的概率出现,求存在完美匹配的概率。

$n\le 7,15s$

Subtask: $n\le 6,7s$

CF1229D

题面

给定$n$个长度为$k$的置换,对于每个子段,求出通过使用零次或多次这些置换可以从初始排列$(1,2,\dots,k)$得到的不同排列个数。

$n\le 2\cdot 10^5,k\le 5$

CometOJ Round #11 E

题意

有n个敌人,m种攻击,第i种攻击会攻击$a_i$次,每次攻击会对敌人总共造成$1\dots b_i$点伤害,

最后每个敌人都至少要受到1点伤害,求不同攻击方案数。

两种方案不同当且仅当某次攻击的总伤害不同或某个敌人受到的伤害不同。

$n\cdot m\le 100000$

CometOJ Round #11 F

题意

给定一张n点m边的图,每条边$(u,v)$有$\frac{1}{3}$的概率$u$指向$v$,有$\frac{1}{3}$的概率从$v$指向$u$,还有$\frac{1}{3}$的概率消失,求这张图是DAG的概率。

$n\le 20,4s$

子集卷积

子集卷积是这样的问题:

$$f_S=\sum_{T\subset S} g_Th_{S-T}$$

给定$g,h$求$f$。

9-17考试 数星星

题意

给定一棵树,点带权,m个点对(m条路径),q次询问区间路径并的点权和。

$n,m,q\le 10^5$

上午模拟赛考了这个trick,然后我不会,学会了来写一波博客。

考虑一类求最短区间的问题,满足单调性(可以two-pointers),插入很快,但是删除很慢,不过可以快速的判断两段的信息合并能否满足条件。

这时普通的尺取法就没法用了。

怎么解决呢?

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×