YbtOJ #582. 「网络流」大收藏家
题目链接:YbtOJ #582 小 C 是在收藏界颇负盛名的大收藏家。 这天,他带着他的藏品去参加收藏家大会,与大家交换藏品。 共有 $n$ 名收藏家参加了这次大会,每个人都带了一种与众不同的藏品来,其中第 $i$ 个收藏家带了 $a_i$ 个自己类型的藏品。 因为小 C 很强,所以他是第 $1$ 个收藏家。大会上会依次进行 $m$ 次交换活动,每…
YbtOJ #581. 「网络流」图上旅行
题目链接:YbtOJ #581 小 C 来到了 F 国,小 C 想好好地参观 F 国。F 国可以看一个有 $n$ 个点 $m$ 条边的有向无环图,小 C 刚开始站在 $1$ 号点。 假设现在小 C 站在 $x$ 号点: 点 $x$ 没有出边,结束旅游。点 $x$ 有 条出边,小 C 等概率地选一条边走过去。 小 J 是小 C 的好朋友,小 J 可以…
YbtOJ #735. 「动态树」毒瘤染色
题目链接:YbtOJ #735 对于一个无向图,若图中的每条边 至多处于一个无向环中,则称这个图为一个 毒瘤图。 小 A 有一个图 $G$,初始包含 $n$ 个点,没有边。显然它是一个毒瘤图。 接下来小 A 会进行 $q$ 次操作,每次操作给出两个正整数 $x,y$,要求判断往 $G$ 中加入 $(x,y)$ 后该图是否仍然是毒瘤图,若是则加入这条…
UOJ #671. 【UNR #5】诡异操作
题目链接:UOJ #671 给定一个长度为 $n$ 的序列 $a_{1\sim n}$,有 $q$ 个操作: 1 l r v,将区间 $[l,r]$ 每个元素 $\lfloor \frac {a_i} v \rfloor $,这里保证 $v_i\ge 1$。2 l r v,将区间 $[l,r]$ 每个元素 $a_i \& v$。3 l r,…
CF1129D Isolation
题目链接:CF1129D 给定一个长度为 $n$ 的序列 $a_{1\sim n}$,把它分割成若干段,使得每段出现过恰好一次的元素个数 $\leq k$,求方案数对 $998244353$ 取模的结果。 $1\leq k\leq n \leq 10^5,1\leq a_i\leq n$。 Solution 1 朴素 DP 不妨设 $f_i$ 表示…
二项式系数 Binomial Coefficients
1.1 基本恒等式 Basic Identities 1.1.1 定义 Definition $\binom nk$ 表示二项式系数,其中 $n$ 称作上指标 (upper index),而称 $k$ 为下指标 (lower index)。 $$\binom rk=\begin{cases}\frac{r^{\underline{k}}}{k!} …
POJ List
为了不再被虐,我力争学会… 助你早日成为信息学奥赛斗士  GitHubyzxoi/POJ  
CF377D Developing Game
题目链接 有 $n$ 个工人,第 $i$ 个工人的能力是 $v_i$,他只与能力在 $l_i$ ​到 $r_i$ 之间的人在一起工作,问最多能选出多少人一起工作并输出方案。 Sol 如果我们选了一个集合 $\mathcal{S}$ 合法,则必有: $$\max_{i\in \mathcal{S}}l_i\le \min_{i\in \mathcal…