老 K 的博客

题意

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

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

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

\(n\cdot m\le 100000\)

题意

给定一张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\)。

题意

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

\(n,m,q\le 10^5\)

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

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

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

怎么解决呢？

link

link

为啥\(O(n+m)\)只出到5000啊？

link

link

link