[CF1213G] Path Queries 发表于 2020-11-05 分类于 OI ， 数据结构 ， 并查集 Valine： 本文字数： 1.8k 阅读时长 ≈ 2 分钟 题目题目链接 题目大意：给出一个 $n$ 个点的树，边有边权。有 $m$ 组询问，每次询问树上所有路径中权值最大的边的权值不超过 $q$ 的路径数量。$1 \le n, m, w, q \le 200000$。 阅读全文 »
[NOIp2010] 关押罪犯 发表于 2020-11-04 分类于 OI ， 数据结构 ， 并查集 Valine： 本文字数： 1.3k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出无向图 $G = (V, E)$，要求将该图删去一些边使得原图被分成两个没有交集的部分，使留下的边的最大值最小。$1 \le |V| \le 20000, 1 \le |E| \le 100000$。 阅读全文 »
[NOIp1996] 挖地雷 发表于 2020-11-04 分类于 OI ， 动态规划 ， DAG 上的 DP Valine： 本文字数： 1.2k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出有向图 $G = (V, E)$，点有点权，求出点权之和最大的一条路。$1 \le |V| \le 20$。 阅读全文 »
[CQOI2007] 涂色 发表于 2020-10-30 分类于 OI ， 动态规划 ， 区间 DP Valine： 本文字数： 1.1k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出长度为 $n$ 的目标字符串，问最少几次能将空字符串涂成目标字符串，每次可以修改连续的一段。$1 \le n \le 50$。 阅读全文 »
[CF1437E] Make It Increasing 发表于 2020-10-30 分类于 OI ， 动态规划 ， 序列 DP Valine： 本文字数： 1.4k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出长度为 $n$ 的序列，每次可以修改任意一个下标不在 $b$ 中的元素，问最少的操作次数使得原序列单调递增，无解输出 $-1$。$1 \le n \le 5 \cdot 10^5, 1 \le a_i \le 10^9$。 阅读全文 »
[CF1436C] Binary Search 发表于 2020-10-25 分类于 OI ， 算法基础 ， 模拟 Valine： 本文字数： 1.1k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出 $x, n, p$，求有多少种长度为 $n$ 的排列满足第 $p$ 个数为 $x$ 且能让二分查找正确运行，结果对 $10^9 + 7$ 取模。下标从 $0$ 开始。$1 \le x \le n \le 1000, 0 \le p \le n - 1$。 阅读全文 »
[CF1433G] Reducing Delivery Cost 发表于 2020-10-24 分类于 OI ， 图论 ， 最短路 Valine： 本文字数： 2.2k 阅读时长 ≈ 2 分钟 题目题目链接 题目大意：给出无向图 $G = (V, E)$ 和 $k$ 组 $a_i, b_i$，每次可以选取图中的任意一条边将边权变为 $0$，最小化 $\sum \operatorname{dis}(a_i, b_i)$。$2 \le |V| \le 1000, |V| - 1 \le |E| \le \min(1000, \dfrac{|V|(|V| - 1)}{2}), 1 \le k, w_i \le 1000$。 阅读全文 »
[CF1433F] Zero Remainder Sum 发表于 2020-10-24 分类于 OI ， 动态规划 ， 记忆化搜索 Valine： 本文字数： 1.2k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出一个大小为 $m \times n$ 的矩阵和整数 $k$，每行可以选取不超过 $\lfloor \dfrac{m}{2} \rfloor$ 个数，并且要求总和是 $k$ 的倍数，求最大的总和。$1 \le n, m, k, a_{i, j} \le 70$。 阅读全文 »
[CF1426D] Non-zero Segments 发表于 2020-10-18 分类于 OI ， 算法基础 ， 贪心 Valine： 本文字数： 1k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给定一个长度为 $n$ 的序列，求最少插入多少数才能将这个序列的任意子段和不为 $0$。$2 \le n \le 200000, -10^9 \le a_i \le 10^9, a_i \neq 0$。 阅读全文 »
[CF1430E] String Reversal 发表于 2020-10-15 分类于 OI ， 算法基础 ， 贪心 Valine： 本文字数： 1.4k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意：给出长度为 $n$ 的字符串，每次可以交换相邻两个字母，问至少要多少次操作能将字符串变为它的逆序。$2 \le n \le 200000$。 阅读全文 »