E - 可乐
题目大意 有 n 箱可乐，第 i 箱上标着正整数 a_i 。选择一个非负整数"聪明值" x 后，若 (a_i \oplus x) \le k 就能喝到第 i 箱可乐。求通过选择合适的 x 最多能喝到的可乐箱数。 1 \le n, k, a_i \le 10^6 。 思路分析 问题等价于： 找一个 x ，使满足 a_i …
算法竞赛题解
个人算法竞赛题解博客
D - 图形
题目大意 给定两个无向简单图 F 和 G ，顶点数均为 n 。每次操作可在 F 中删除一条边，或在 F 中无边的一对点间添加一条边。求使 F 满足" 任意 u, v 在 F 中连通当且仅当在 G 中连通 "所需的最小操作数。 t 组数据， \sum n, m_1, m_2 \le 2 \times 10^5 。 思路分…
C - 食物链
题目大意 给定 n 个物种和 m 条能量流动关系（有向边 a_i \to b_i ，能量从 a_i 流向 b_i ），求食物网的 食物链条数 。食物链是从入度为 0 的物种出发、到出度为 0 的物种结束的路径，单独一种孤立生物不算一条食物链。 1 \le n \le 10^5 ， 0 \le m \le 2 \time…
B - 最大生成树
题目大意 有一个 n 个点的完全图，点编号 1 \sim n ，点 (i, j) 之间的边权为 i - j 。求该图最大生成树的边权总和，对 998244353 取模。 2 \le n \le 10^{18} ，且 n 为偶数。 思路分析 完全图的边权只取决于两个端点的距离，直觉上应选"尽量长的边"。用 Kruskal…
A - 最大异或对
题目大意 给定 N 个整数 A_1, A_2, \dots, A_N ，从中选出两个数进行异或（xor）运算，求能得到的结果最大值。其中 1 \le N \le 10^4 ， 1 \le A_i \le 2^{31} 。 思路分析 这是 01 字典树（Trie）的经典应用。 核心思想 ：异或运算的每一位相互独立，要让两…
4288 逃离塔科夫 题解
4288 逃离塔科夫 题解 题目链接 ：http://39.106.228.241/problem.php?id=4288 题目大意 在诺文斯克战乱区，你有 N 个物资点（编号 1\sim N ）和 M 条单向暗道。从出生点 S 出发，目标是抵达撤离点 E 。 - 每个物资点 i 的战利品价值为 v_i ， 首次 踏入…
示例：A + B 问题（洛谷 P1001）
题目大意 给定两个整数 a 和 b ，求它们的和。 思路分析 直接相加即可，时间复杂度 O(1) ，空间复杂度 O(1) 。 推导过程 求和公式： \sum_{i=1}^{n} i = \frac{n(n+1)}{2} 当 n = 10 时， S = 55 。这个公式可以用于优化前缀和类问题。 参考代码 复杂度对比 方…