USACO2025年1月份月赛结束！这次1月的USACO题目难度，不得不说比12月的那次提升了许多。
在为期4天的比赛中，共有11565名不同的用户登录。共有9450名参与者提交了至少一个解决方案，来自100多个不同的国家。4276名参与者来自美国，还有来自中国、加拿大、韩国、罗马尼亚、马来西亚、印度和新加坡的高水平参与者。
目前，USACO美国计算机奥林匹克1月第二场月赛已放榜 ！恭喜顺利通关的同学们~
一月赛晋级分数线：
晋级白银组分数线：700分或以上晋级黄金组分数线：700分或以上
晋级白金组分数线：700分或以上
2025年USACO计算机竞赛1月赛题已帮大家整理好啦！让我们一起来了解一下吧
USACO
USACO 2025 JANUARY CONTEST
BRONZE（铜级）
第一题
题目描述:
假设有两个 N×N（1≤N≤1000）的数组，其中第一个数组的元素值未知，第二个数组是第一个数组按照一定规则变化后得到的。将这两个数组叠加后，得到一个新的 N×N 数组，新数组中每个位置有三种状态：W、G、B 。
W 状态：表示该位置叠加后无数据。
G 状态：表示叠加后，可能两个数组其中一个在该位置有数据。
B 状态：表示叠加后，两个数组在该位置均有数据。
需注意，第二个数组的数据范围没有超出第一个数组，即第一个数组包含了所有的数据，没有新数据进入第二个数组的数据范围。
数组从第一个变化到第二个时，遵循以下规则：在第一个数组中，每个位置上的数据只有两种变化可能，要么直接消失，要么向右移动 A 距离，并向下移动 B 距离 ，之后两个数组进行叠加。
现在已知 N×N 大小的叠加数组，以及移动距离 A 和 B ，需要求解第一个数组中最小存在数据的个数。
题解：
该问题可分类讨论：
特殊情况：A = 0 且 B = 0：此时数据未发生移动，只需依据规则 1 进行分析。由于要求的是最小数据个数cnt，而G状态是由第一个数组的数据消失形成，B状态不会改变，所以只需统计状态为W的个数，那么第一个数组的最小数据个数即为N*N - cnt。按照此思路编写代码，能够通过 3 个数据点的测试。
一般情况：A ≠ 0 或 B ≠ 0：这种情况下，需要综合规则 1 和规则 2 进行分类讨论：叠加数组位置为W：因为目标是求最小数据个数，所以可将此位置视为无数据存在，即第一个数组在对应位置的数据为 0（第一个数组是时间先序列数组）。
叠加数组位置为G：将第二个数组中G数据位置记为(pre_x, pre_y)，它是(x, y)减去移动距离(A, B)之后得到的。分析如下：若pre_x或pre_y为负值，或者第一个数组中(pre_x, pre_y)位置的数据为 0，这表明叠加数组中G位置的数据来源于第一个数组，那么在第一个数组的(x, y)位置设置为 1。
否则，说明叠加数组中G位置的数据是由第二个数组自身产生的。
叠加数组位置为B：这意味着数组 1 和数组 2 在此位置均有数据。检查(pre_x, pre_y)的状态：若pre_x <= 0或者pre_y <= 0，由于题目说明没有新数据进入第二个数组范围，所以数组 1 的数据不可能从外部进入，此时可直接结束程序并输出 - 1。
若pre_x > 0且pre_y > 0，表明第一个数组和第二个数组在(pre_x, pre_y)位置都有数据，那么将第一个数组的(pre_x, pre_y)设置为 1。最后，统计第一个数组中值为 1 的元素个数，即为所求答案。
第二题
题目描述:
问数字序列中本质不同的 ABB 子序列有多少个。
题目解析:
倒序遍历。对每一个 ABB,我们可以直接统计当前可行的 B8的数量，这样每到一个新的数字就可以得到这个数字可以跟的后缀数量(值得注意的是要将自己排除掉)。最后统计一遍每个数对应的和就是答案。
第三题
题目描述:
给定两个整数序列，可以进行一次[l,r]的翻转操作，问对于C=0,...,n，写”,有多少个区间[l,r]使得翻转后的序列中恰好有C 个数与原序列相同。
题目解析：
首先我们可以发现一点，对于一.个区间翻转[l,r]，它的匹配数一定是由[l+1,r-1]的匹配数加上自己两个端点得到的(即端点和内部无关)，这样我们就可以得到一个 O(n²)预处理所有区间翻转后的匹配数。
然后是不属于翻转区间的内容，可以发现它一定是一个前缀+后缀，一轮预处理即可。
最后直接统计答案并输出。
USACO
USACO 2025 JANUARY CONTEST
SILVER（银级）
第一题
题目描述:
- 有N头牛排成一列，每头牛有一个物种编号a[i]
- 兽医要求第i个位置必须是物种b[i]的牛才会检查
- 可以选择一个区间[l,r]，将这个区间内的牛反转顺序
- 求所有可能的区间反转操作中，能被检查的牛的总数
第二题
题目描述:
输入数据的第一行包含一个整数 T，且 1≤T≤10，T 代表测试用例的数量。
每个测试用例的第一行包含两个整数 N 和 M：
N 表示数组长度，其取值范围是 1≤N≤2×10⁵。
M 为目标除数，取值范围是 1≤M≤10⁹。
每个测试用例的第二行包含 N 个整数 a₁,a₂,⋯,aₙ，其中每个整数 aᵢ满足 0≤aᵢ≤10⁹ 。
所有测试用例中 N 的总和不会超过 5×10⁵。
第三题
题目描述:
Bessie 拥有一个 N×N 的加法表（1≤N≤1000），该加法表中第 r 行第 c 列的数字等于 r + c。以 N = 3 为例，其对应的加法表如下所示：
2 3 4
3 4 5
4 5 6
Elsie 对这张加法表进行了一系列操作，操作类型共分为以下三种：
行交换操作：交换表格中的任意两行。
列交换操作：交换表格中的任意两列。
数值替换操作：选择表格中两个不同的数 a 和 b，然后将表格中所有的 a 替换为 b，同时将所有的 b 替换为 a。
Elsie 执行这些操作时遵循特定顺序：首先执行若干次（次数可以是 0 次）行交换操作，接着执行若干次列交换操作，最后执行若干次数值替换操作。
现在，需要帮助 Bessie 恢复加法表在完成所有行交换和列交换操作，但尚未进行任何数值替换操作时的状态。若存在多个可能的恢复结果，需输出字典序最小的那一个。
USACO
USACO 2025 JANUARY CONTEST
SILVER（金级）
第一题
第二题
第三题
【竞赛报名/项目咨询+微信：mollywei007】
