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 …
🏆 ACM暑期第五次周赛
Contest3056 · ACM算法攻关部暑期第五次周赛，共 5 题：最大异或对 / 最大生成树 / 食物链 / 图形 / 可乐
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）的经典应用。 核心思想 ：异或运算的每一位相互独立，要让两…