[SP1716] GSS3 - Can you answer these queries III 发表于 2021-02-26 分类于 OI , 数据结构 , 线段树 Valine: 本文字数: 2.2k 阅读时长 ≈ 2 分钟 题目题目链接 题目大意: 给出 $n$ 个数 $\{a_n\}$. $m$ 次操作, 每次操作将 $a_x$ 改为 $y$ 或查询 $[x, y]$ 中最大子段和. $1 \le n, m \le 50000$. 阅读全文 »
[SP1043] GSS1 - Can you answer these queries I 发表于 2021-02-26 分类于 OI , 数据结构 , 线段树 Valine: 本文字数: 2k 阅读时长 ≈ 2 分钟 题目题目链接 题目大意: $m$ 次询问, 每次询问 $[l, r]$ 中的最大子段和. $1 \le n \le 50000$. 阅读全文 »
[ABC147D] Xor Sum 4 发表于 2021-02-24 分类于 OI , 数学 , 位运算 Valine: 本文字数: 1k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意: 求 $\sum \limits_{i = 1}^{n - 1} \sum \limits_{j = i + 1}^{n} (a_i \text{ xor } a_j)$. $2 \le n \le 3 \times 10^5, 0 \le a_i < 2^{60}$. 结果对 $10^9 + 7$ 取模. 阅读全文 »
[TJOI2009] 猜数字 发表于 2021-02-24 分类于 OI , 数学 , 数论 , 中国剩余定理 Valine: 本文字数: 1.3k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意: 分别给出 $k$ 个数 $\{a_k\}, \{b_k\}$. 求最小的自然数 $n$ 满足 $\forall i \in [1, k], b_i | (n - a_i)$. $1 \le k \le 10, |a_i| \le 10^9, 1 \le b_i \le 6 \times 10^3, \prod b_i \le 10^{18}, b_i$ 两两互质. 阅读全文 »
[CF1479B] Painting the Array 发表于 2021-02-19 分类于 OI , 基础算法 , 贪心 Valine: 本文字数: 2.5k 阅读时长 ≈ 2 分钟 题目题目链接 题目链接 题目大意: 给定序列 $\{a_n\}$, 对这个序列的每个元素都将其按相对顺序添加到 $a^0$ 或 $a^1$ 数组中. 求出两个新数组在合并连续相同的数后长度和的最大值和最小值. $1 \le n \le 10^5$. 阅读全文 »
[CF1479A] Searching Local Minimum 发表于 2021-02-19 分类于 OI , 算法基础 , 二分 , 非传统题 , 交互题 Valine: 本文字数: 1.2k 阅读时长 ≈ 1 分钟 题目题目链接 现有一个长度为 $n$ 的排列 $\{a_n\}$. 你可以进行向交互库进行最多 $100$ 次询问, 每次返回 $a_i$ 的值. 要求找出一个 $i$ 使得 $a_i < \min \{a_{i - 1}, a_{i + 1}\}$. $a_0 = a_{n + 1} = +\infty$. $1 \le n \le 10^5$. 阅读全文 »
[Celeste-B] Golden Feather 发表于 2021-02-18 分类于 OI , 数学 , 最大公约数 Valine: 本文字数: 755 阅读时长 ≈ 1 分钟 题目题目链接 题目大意: 定义 $i$ 点权值为 $a_i = (i + 1)^2 - 1$, $i, j$ 间的边权为 $\gcd(a_i, a_j)$, 求 $n$ 个点 MST 的边权和. $1 \le n \le 10^{18}$. 阅读全文 »
[APIO2009] 抢掠计划 发表于 2021-02-18 分类于 OI , 图论 , 强连通分量 Valine: 本文字数: 2.3k 阅读时长 ≈ 2 分钟 题目题目链接 题目大意: 给出一个 $n$ 个点, $m$ 条边的图, 点有点权, 求一条从 $S$ 出发在一个特殊点结束的路径使得路径上点权和最大. $1 \le n, m \le 5 \times 10^5$. 阅读全文 »
[洛谷 P1516] 青蛙的约会 发表于 2021-02-18 分类于 OI , 数学 , 数论 , 最大公约数 Valine: 本文字数: 1.1k 阅读时长 ≈ 1 分钟 题目题目链接 题目大意: 长度为 $L$ 的环上有两个点, 坐标为 $A: x, B: y$, 其中 $A$ 点每秒可以向正方向走 $m$ 单位长度, $B$ 点每秒可以向正方向走 $n$ 单位长度, 问经过几秒 $A$ 和 $B$ 会处于同一点. 无解输出 Impossible. $0 < x, y, m, n \le 2 \times 10^9, 0 < L \le 2.1 \times 10^9$. 阅读全文 »