「NOI2019」序列
题目大意给定两个长度为 $n$ 的正整数序列 $\{a_i\}$与 $\{b_i\}$，序列的下标为 $1, 2, \cdots , n$。现在你需要分别对两个序列各指定恰好$K$ 个下标，要求至少有 $L$ 个下标在两个序列中都被指定，使得这 $2K$ 个下标在序列中对应的元素的总和最大。$n \leq 2\times 10^5,\sum _n \leq 10^6$题解模拟费用流真奇妙首...
题目大意给定两个长度为 $n$ 的正整数序列 $\{a_i\}$与 $\{b_i\}$，序列的下标为 $1, 2, \cdots , n$。现在你需要分别对两个序列各指定恰好$K$ 个下标，要求至少有 $L$ 个下标在两个序列中都被指定，使得这 $2K$ 个下标在序列中对应的元素的总和最大。$n \leq 2\times 10^5,\sum _n \leq 10^6$题解模拟费用流真奇妙首...
题意题目链接给定一个长度为 $n$ 的 $A$ 数组和 $B$ 数组，你有两个集合 $S_1,S_2$ 初始时为空。每次你的操作是选择两对 $(i,j),(p,q)$ 满足 $(i,j) \notin S_1,(p,q) \notin S_2,A_i<B_j,B_p<A_q,\gcd(A_i,B_j) \neq 1,\gcd(A_q,B_p) \neq 1,\gcd(A_q,B_...
题目链接题目大意有一个大小为 $n$ 的全集，每个元素是一个数，有$n$个子集，题目保证任意$k$个子集的并的大小$\geq k$。你需要选出一些子集使得这些子集的并大小等于子集个数，且其并中元素和最小，可以为空集。$n \leq 300$题解这个题有两种做法。做法 1如果不考虑限制条件 权值取反之后就是一个最大权闭合子图模型（选了集合就要选对应的元素）考虑条件 “任意$k$个子集的并的大小...
题目链接首先考虑题目描述代表了哪些限制：对于非树边 $(u,v)$ 它在树上对应了一段路径 要求这个路径上每一条边都不比他大。那么贪心的想：树边只可能减小 非树边只可能增大那么我们用 $j \text{ cover } i$ 表示$i$ 树边在 $j$ 非树边两端点在树上的路径上。用 $d_i$ 表示边的变化量。设 $T$ 表示树边集，$E$ 表示非树边集这个问题看起来是个 LP 问题 不妨...
网络流题目中，如果一种物品有两种状态（选或不选），告诉你每一种状态产生的收益/代价，我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了 $k$ 种，我们就需要用一种新的建图方法。 我们拿两道题目举例：RatingProgressAward*TCO2017 Semifinal 题目链接 如果对于积分做了前缀和之后我们发现题目就是要求在满足限制的条件下最大化区间和。 对于一个...