USACO 25OPEN SILVER1+2

C0mp1ler

防吞

C0mp1ler

第一题

C0mp1ler

USACO 25OPEN SILVER1

算法与知识点

1. 位运算与二进制：左移一般等效于 * 2；异或的性质

2. 贪心：直接优先保证 popcount 异或为 K 且和最小，先不考虑数列之和

思路

l 理解题目

题目要求构造一个非负整数序列，使得：

所有元素和为 M；

每个数二进制中1的数量 (popcount) 按位异或的结果为 K；

元素个数 N 不超过100。

直接暴力搜索很难，因为 M 和 K 会很大

l 贪心：构造满足 popcount 异或为 K 的最小和序列

利用 (1<<(1<<bit))−1 构造每个元素，使该元素的 popcount 恰为2**bit ，且数值最小。

例：k=5=0b101

a = [1, 15]

这样构造的序列满足 popcount 异或等于 K，且和尽可能小，方便后续调整。

l 调整使得和=M

构造的序列 a 和 M 可能不等：difference = M - sum(a)。

分类讨论：

l 当差值为负，说明无法构造；

l 当差值为零，直接返回；

l 当差值为正，则要补充一组数 b，要求：

n 它们的 popcount 异或为0（不影响原来的异或结果）；

n 它们的和为差值。

n 通过实验，得到：两个相等数字的 popcount 异或为0。（二进制每位均相等）

n 差值为偶数时，用两个相等数字平分差值即可。

n 差值为奇数时，通过增加 1 和 2（popcount 都是1，异或为0），并加两个相等的数字，保证总和和异或满足。

C0mp1ler

第二题

C0mp1ler

USACO 25OPEN SILVER2

算法与知识点

1. 图论基础：

邻接表：储存每个节点接了谁的字典

度：每个节点接了几个

将识别码视作图中的顶点，边代表两识别码和为A或B的可配对关系。求最大匹配数（最大独立边集）。

2. 贪心思想：始终只匹配“度为1”的顶点对应的边，减少冲突，确保匹配数最大。

3. 数据结构：使用字典（哈希表）存储节点及其数量，邻接表存储图结构，集合维护邻居关系，快速查找与更新。

4. 复杂度优化：利用度为1顶点的特性循环消边，避免全图复杂匹配算法，时间复杂度约 O(NlogN) 。

思路

l 尝试暴力

（略）

失败

l 理解题目

给定N组（识别码，数量），每个识别码唯一，但数量可多。

两个奶牛可配对当且仅当它们的识别码和为A或B。

求最多能组成多少个无交集的配对。

l 转化为图模型

每个唯一识别码为一个图节点，节点权重为奶牛数量。

若两节点识别码和为A或B，则设为有边。

配对即在图中选边，边两端节点共同消耗对应奶牛数量（每只奶牛只在一个交流当中）

l 瞪眼法

图中每个节点最多连接两个配对目标，A或B

l 贪心匹配策略

只处理度为1的节点（链的端点）：

对于度为1的节点，尝试最大配对数（取较小奶牛数）。

消耗配对数量后删除这条边，同时更新邻居的度数。

若邻居度变为1，加入待处理列表。

重复此过程直到没有度为1的节点。

理论证明该策略能消除所有边（包括环），达到最大匹配数。

当某节点的两识别码和满足A或B且相等时，可在该节点内部自配对。配对数为该节点奶牛数除以2。

所有能匹配的奶牛对数之和，即最大可并行通信的对数。

C0mp1ler