复习复习

IO祖传快读板子template <typename T> inline void read(T& x) {x=0;T f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();

你需要生产 $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$。

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

题目描述你有个长度为 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 能到达的节点所

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

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

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

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

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