P4694「PA2013」 Raper


你需要生产 $k$ 张光盘。每张光盘都要经过两道工序:先在 A 工厂进行挤压,再送到 B 工厂涂上反光层。 你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间,每天可以先送一张光盘到 A 工厂(或者不送),然后再送一张已经在 A 工厂加工过的光盘到 B 工厂(或者不送),每家工厂一天只能对一张光盘进行操作,同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。 求生产出 $k$ 张光盘的最小花费。$1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant a_i, b_i \leqslant 10^9$。

P6295 有标号 DAG 计数


对 $n$ 个点有标号的有向无环图进行计数,要求:弱连通图(所有的有向边替换为无向边后的图为连通图)。输出答案对 $998244353$ 取模的结果。$1 \le n \le 10^5$。

[CCC2021 S3] Lunch Concert


https://www.luogu.com.cn/problem/P9025

[CERC2013] Magical GCD


https://www.luogu.com.cn/problem/P7009

[集训队作业2013]城市规划


题目描述题目传送门思路套路题。设 fif_ifi​ 表示由 iii 个点所组成的联通无向图个数,gig_igi​ 表示由 iii 个点组成的无向图个数,不保证联通。由于没有重边与自环, iii 个点最多有 (n2)\binom{n}{2}(2n​) 条边,则有 gi=2(n2)g_i = 2^{\b

[USACO22DEC] Bribing Friends G


题目描述题目传送门思路有显然的三维 dp。设 fi,j,kf_{i,j,k}fi,j,k​ 表示前 iii 个朋友用了 jjj 个哞尼和 kkk 个冰激凌甜筒能得到的最大价值。那么有:fi,j,k=max⁡w>ci,w×xi>k{fi−1,j,k,fi−1,j−ci+w,k−w×xi+p

[PA2021] Od deski do deski


题目描述题目传送门思路计数题,很容易想到 dp。难点在于状态的设计,显然有一维状态是序列长度,有一维表示合法与否,dp 值表示为方案数,记为 fi,0/1f_{i,{0/1}}fi,0/1​。这样是没有办法转移的,因为我们接下来要填什么与之前填的数字有关,考虑加维。发现对于一个合法序列 SSS,假设

[CERC2014]The Imp


题目传送门题目传送门思路Lemma. 按照 viv_ivi​ 升序购买一定最优。Proof. 设先后购买的为 (v1,c1),(v2,c2)(v_1,c_1),(v_2,c_2)(v1​,c1​),(v2​,c2​) 其中 v1≤v2v_1 \le v2v1​≤v2。此时的答案为 min⁡(v1−c

[POI2010]MOS-Bridges


题目描述洛谷传送门LOJ 传送门思路好恶心好恶心的网络瘤题,属于是知道结论就会做但是会写挂的题,佩服出题人脑洞。性质:对于一条欧拉回路,每个点的入度 = 出度首先可以考虑二分答案,二分最小权值 xxx,对于每个 xxx,我们可以建出一张图来,在这张图中,我们把所有不符合条件的边砍掉(变成有向边,记得

[HAOI2016]字符合并


在一场战争中,战场由 $n$ 个岛屿和 $n-1$ 个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为 $1$ 的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他 $k$ 个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。