May Challenge 2020 Div.2 简要题解
因为有的题代码没写 所以统一不给出代码了。感觉题目整体还是很提高组的 就是我 12 天比赛放在 3h 打就死了比赛地址COVID19直接枚举第一个感染的是谁 模拟一下就好了。按照实现情况 $O(n^2)/O(n\log n)$CORUS按照题意贪心模拟一下就好了。TRPLSRT首先把排列拆成若干个轮换，轮换是有顺序的（$i \to p_i$）目标是拆成 $n$ 个轮换。对于每个长度 $>...
因为有的题代码没写 所以统一不给出代码了。感觉题目整体还是很提高组的 就是我 12 天比赛放在 3h 打就死了比赛地址COVID19直接枚举第一个感染的是谁 模拟一下就好了。按照实现情况 $O(n^2)/O(n\log n)$CORUS按照题意贪心模拟一下就好了。TRPLSRT首先把排列拆成若干个轮换，轮换是有顺序的（$i \to p_i$）目标是拆成 $n$ 个轮换。对于每个长度 $>...
昨天打完牛客挑战赛意识模糊忘记 register 了...一看题目发现血亏。250pts题目我们将下标按照 $\bmod k$ 分组 发现每个组之间的交换互不影响。每次交换相当于至少要减少一对顺序对。我们肯定是想每次只减少一个顺序对（这样这一组的答案就是顺序对个数了）。发现我们每次交换相邻两个顺序对就满足条件。所以答案就是每组的顺序对个数加起来。一开始 zz 了想错了 但是感觉 10 min...
题目大意给定两个长度为 $n$ 的正整数序列 $\{a_i\}$与 $\{b_i\}$，序列的下标为 $1, 2, \cdots , n$。现在你需要分别对两个序列各指定恰好$K$ 个下标，要求至少有 $L$ 个下标在两个序列中都被指定，使得这 $2K$ 个下标在序列中对应的元素的总和最大。$n \leq 2\times 10^5,\sum _n \leq 10^6$题解模拟费用流真奇妙首...
题目大意$n$ 个点 $m$ 条边的有向图，每个点有一个初始权值，支持以下操作：删除一条从 $u$ 到 $v$ 的有向边询问 $u$ 所在的强连通分量内权值前 $k$ 大的权值和将一个点的权值 $+w$题解首先如果我们把强连通分量对应到无向图 对无向图做这个东西只需要时间倒流然后搞个权值线段树合并就可以了。这种有向图转无向图的一种经典套路是去二分每个边的两个端点什么时候第一次在一个 SCC ...