置顶CSP 复习


复习复习

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$。

CF1588F Jumping Through the Array


题目描述你有个长度为 nnn 的数组 aaa 和一个长度为 nnn 的排列 ppp,对于每一个 iii 有一有向边 (i,pi)(i,p_i)(i,pi​)。有如下三种操作:1 l r 询问 ∑i=lrai\sum_{i=l}^r a_i∑i=lr​ai​。2 v x 将所有 vvv 能到达的节点所

CF81E Pairs


题目描述给定一颗黑白内向基环树,你要对其进行匹配,让匹配数最多的同时最大化异色匹配。并且给出一种方案。1≤n≤1051 \le n \le 10^51≤n≤105。思路暴力考虑流。对于一颗普通的树,进行黑白染色变成二分图,跑网络流即可得到最大匹配。如果是异色匹配费用流即可。对于这道题,不妨直接断开环

CF1307F Cow and Vacation


有一颗 $n$ 个节点树,其中有 $k$ 个点是关键点。现在有 $m$ 次询问,每次询问是否存在一条 $u \to v$ 的路径(不一定是简单路径),使得路径上任意两个关键点并且 $u,v$ 和路径上与其最近的关键点的距离小于等于 $k$。 $n,m,k \le 2\times10^5$。

LOJ535 「LibreOJ Round #6」花火


[$\mathcal{Link}$](https://loj.ac/p/535)

CF1707E Replae


https://codeforces.com/problemset/problem/1707/E

[ARC127E] Priority Queue


题目描述题目传送门思路正着做比较困难,反着来。假设 {a}\{a\}{a} 是我们最后剩下来的集合。可以发现一个结论:aaa 是一个单调上升序列肯定不劣。这样我们可以从头开始加入数字。每一此 2 操作实际上可以与其之前的 1 操作抵消。所以我们无需考虑二操作。由于我们可以证明 aaa 单调升。可以设

[CCC2021 S3] Lunch Concert


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