USACO 2026一月赛铜组真题解析现已发布。本文将深入剖析三道题目，详解解题思路与关键代码，助你透彻理解赛题精髓。
题目解析
第一题
题目名称：CHIP EXCHANGE
1
题目描述
Bessie the cow has in her possession A chips of type A and B chips of type B (0 <= A, B <= 10^9).
She can perform the following operation as many times as she likes:
If you have at least cB chips of type B, exchange cB chips of type B for cA chips of type A(1 <= cA, cB <= 10^9).
Determine the minimum non-negative integer x such that the following holds:
after receiving x additional random chips, it is guaranteed that Bessie can end up with at least fA chips of type A (0 <= fA <= 10^9).
INPUT FORMAT(input arrives from the terminal / stdin):
The first line contains T, the number of independent test cases (1 <= T <= 10^4).
Then follow T tests, each consisting of five integers A, B, cA, cB, fA.
OUTPUT FORMAT(print output to the terminal / stdout):
Output the answer for each test on a separate line.
Note:The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
SAMPLE INPUT:
2
2 3 1 1 6
2 3 1 1 4
SAMPLE OUTPUT:
1
0
SAMPLE INPUT:
5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 1000000000
SAMPLE OUTPUT:
9
8
7
0
1000000000000000000
For the first test, Bessie initially starts with no chips.
If she receives any 9 additional chips, she can perform the operation to end up with at least 5 chips of type A.
For example, if she receives 2 chips of type A and 7 chips of type B, she can perform the operation twice to end up with 6 >= 5 chips of type A.
However, if she only receive 8 chips of type B, she can only end up with 4 <= 5 chips of type A.
For the fourth test, she already has enough chips of type A from the start.
SCORING:
Input 3: cA = cB = 1
Inputs 4-5: x ≤ 10 for all cases
Inputs 6-7: cA=2, cB=3
Inputs 8-12: No additional constraints.
2
题意重述
初始有 A 个 A 型筹码、B 个 B 型筹码。允许无限次操作：
只要当前 B 型筹码 ≥ cB，就能用cB 个 B 换 cA 个 A。
现在“额外收到 x 个随机筹码”，随机意味着：这 x 个筹码里有多少个是 A、多少个是 B，你无法控制（等价于对手/最坏情况分配）。
要求最小的非负整数 x，使得：无论这 x 个筹码怎么分配(A/B比例如何)，你都一定能通过若干次兑换，最终让 A 型筹码数量 ≥ fA。
3
解题思路
1.用一个变量把“最坏情况分配”参数化
2.（核心化简）
为什么“最坏情况”不需要枚举 b=0..x
2.1观察 floor 分段常数 ⇒ h(b) 分段线性
2.2 这些“端点 b”是等差数列 ⇒ 最小值只需看两端
3.为什么可以二分 x（单调性）
4.算法步骤（可直接照抄）
4
代码参考
参考 C++（使用 __int128 防溢出）
向上滑动阅览
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
i128 finalA(i128 A, i128 B, i128 cA, i128 cB, i128 x, i128 b) {
i128 q = (B + b) / cB;
return A + (x - b) + cA * q;
}
bool ok(int64 A, int64 B, int64 cA, int64 cB, int64 fA, int64 x_ll) {
i128 A0 = (i128)A, B0 = (i128)B, CA = (i128)cA, CB = (i128)cB, X = (i128)x_ll;
i128 best = finalA(A0, B0, CA, CB, X, X);
int64 Bmod = (cB == 0 ? 0 : (B % cB)); // cB>=1 always, but keep safe style
int64 first = ( ( (cB - 1) - Bmod ) % cB + cB ) % cB; // normalized to [0, cB-1]
if ((i128)first <= X) {
best = min(best, finalA(A0, B0, CA, CB, X, (i128)first));
i128 kmax = (X - (i128)first) / CB;
i128 last = (i128)first + kmax * CB;
best = min(best, finalA(A0, B0, CA, CB, X, last));
}
return best >= (i128)fA;
}
int main() {
int T;
cin >> T;
while (T--) {
int64 A, B, cA, cB, fA;
cin >> A >> B >> cA >> cB >> fA;
if (A >= fA) {
cout << 0 << "n";
continue;
}
int64 lo = 0, hi = (int64)1e18;
while (lo < hi) {
int64 mid = lo + (hi - lo) / 2;
if (ok(A, B, cA, cB, fA, mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "n";
}
return 0;
}
第二题
题目名称：COW SPLITS
1
题目描述
Bessie is given a positive integer N and a string S of length 3N which is generated by concatenating N strings of length 3,
each of which is a cyclic shift of "COW". In other words, each string will be "COW", "OWC", or "WCO".
String X is a square string if and only if there exists a string Y such that X=Y+Y, where + represents string concatenation.
For example, "COWCOW" and "CC" are examples of square strings but "COWO" and "OC" are not.
In a single operation, Bessie can remove any subsequence T from S where T is a square string.
A subsequence of a string is a string which can be obtained by removing several (possibly zero) characters from the original string.
Your job is to help Bessie determine whether it is possible to transform S into an empty string.
Additionally, if it is possible, then you must provide a way to do so.
Bessie is also given a parameter k which is either 0 or 1. Let M be the number of operations in your construction.
If k=0, then M must equal the minimum possible number of operations.
If k=1, then M can be up to one plus the minimum possible number of operations.
INPUT FORMAT(input arrives from the terminal / stdin):
The first line contains T, the number of independent test cases (1 <= T <= 10^4) and k (0 <= k <= 1).
The first line of each test case has N (1 <= N <= 10^5).
The second line of each test case has S.
The sum of N across all test cases will not exceed 10^5.
OUTPUT FORMAT(print output to the terminal / stdout):
For each test case, output either one or two lines using the following procedure.
If it is impossible to transform S into an empty string, print −1 on a single line.
Otherwise, on the first line print M -- the number of operations in your construction.
On the second line, print 3N space-separated integers.
The ith integer x indicates that the ith letter of S was deleted as part of the xth subsequence (1 <= x <= M).
SAMPLE INPUT:
2
2 3 1 1 6
2 3 1 1 4
SAMPLE OUTPUT:
1
0
SAMPLE INPUT:
3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
SAMPLE OUTPUT:
-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1
For the last test, the optimal number of operations is two, so any valid construction with either M=2 or M=3 would be accepted.
For M=3, here is a possible construction:
1. In the first operation, remove the last twelve characters. Now we're left with COWCOW.
2. In the second operation, remove the subsequence WW. Now we're left with COCO.
3. In the last operation, remove all remaining characters.
SAMPLE INPUT:
3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC
SAMPLE OUTPUT:
-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2
SCORING:
Inputs 3-4: T <= 10, N <= 6, k=0
Inputs 5-6: k=1
Inputs 7-14: k=0
2
题意重述
初始给定长度为 3N 的字符串 S，由 N 个长度为 3 的子串拼接而成，每个子串都是“COW”的循环移位（即“COW”“OWC”“WCO”三者之一）。允许执行若干次操作：
每次操作可从 S 中移除一个平方子序列（平方子序列指能拆分为两个完全相同子串拼接的序列，如“COWCOW”“CC”，且子序列可通过删除原串若干字符得到，不要求连续）。
要求判断能否通过若干次操作将 S 完全清空；若可以，需给出具体操作方案，且需满足：若参数 k=0，操作次数 M 必须是最小可能值；若 k=1，M 最多可比最小可能值大 1。
最终输出：若不可清空输出 -1；若可清空，先输出操作次数 M，再输出 3N 个整数，第 i 个整数表示 S 的第 i 个字符属于第几次操作移除的子序列。
3
解题思路
1.长度
2.如何判定
3.为什么能保证情况2和3一定对？
4
代码参考
向上滑动阅览
#include <bits/stdc++.h>
using namespace std;
int shift_id(const string& blk) {
if (blk == "COW") return 0;
if (blk == "OWC") return 1;
return 2; // blk == "WCO"
}
int main() {
int T, k;
cin >> T >> k; // k is not needed because our output is optimal anyway
while (T--) {
int N;
string S;
cin >> N >> S;
if (N % 2 == 1) {
cout << -1 << "n";
continue;
}
int total = 3 * N;
int L = total / 2; // 3N/2
int H = N / 2; // number of blocks per half
string A = S.substr(0, L);
string B = S.substr(L, L);
if (A == B) {
cout << 1 << "n";
for (int i = 0; i < total; i++) {
cout << 1 << (i + 1 == total ? 'n' : ' ');
}
continue;
}
vector<int> ans(total, 1);
for (int i = 0; i < H; i++) {
string blkA = S.substr(3 * i, 3);
string blkB = S.substr(3 * (i + H), 3);
int sa = shift_id(blkA);
int sb = shift_id(blkB);
int d = (sb - sa + 3) % 3;
int baseA = 3 * i;
int baseB = 3 * (i + H);
if (d == 1) {
// A: [2,1,1], B: [1,1,2]
ans[baseA + 0] = 2;
ans[baseB + 2] = 2;
} else if (d == 2) {
// A: [1,1,2], B: [2,1,1]
ans[baseA + 2] = 2;
ans[baseB + 0] = 2;
}
// d == 0: all ones already
}
cout << 2 << "n";
for (int i = 0; i < total; i++) {
cout << ans[i] << (i + 1 == total ? 'n' : ' ');
}
}
return 0;
}
第三题
题目名称：PHOTOSHOOT
1
题目描述
Farmer John is looking at his cows in a magical field and wants to take pictures of subsets of his cows.
The field can be seen as a N×N grid (1 <= N <= 500), with a single stationary cow at each location.
Farmer John's camera is capable of taking a picture of any K×K square that is part of the field (1 <= K <= min(N,25)).
At all times, each cow has a beauty value between 0 and 10^6.
The attractiveness index of a picture is the sum of the beauty values of the cows contained in the picture.
The beauty value for every cow starts out as 0, so the attractiveness index of any picture in the beginning is 0.
At Q times (1 <= Q <= 3 * 10^4), the beauty of a single cow will increase by a positive integer due to eating the magical grass that is planted on Farmer John's field.
Farmer John wants to know the maximum attractiveness index of a picture he can take after each of the Q updates.
INPUT FORMAT(input arrives from the terminal / stdin):
The first line contains integers N and K.
The following line contains an integer Q.
Each of the following Q lines contains three integers: r, c, and v, which are the row, column, and new beauty value,respectively (1 <= r, c <= N, 1 <= v <= 10^6).
It is guaranteed that the new beauty value is greater than the beauty value at that location before.
OUTPUT FORMAT(print output to the terminal / stdout):
Output Q lines, corresponding to the maximum attractiveness index of a picture after each update.
SAMPLE INPUT:
4 2
3
2 2 11
3 4 3
3 1 100
SAMPLE OUTPUT:
11
11
111
After the first update, a picture with the maximum attractiveness index is the picture with upper left corner (2,2) and lower right corner (3,3), which has an attractiveness index of 11+0+0+0=11.
The second update does not affect the maximum attractiveness index.
After the third update, the picture with the maximum attractiveness index changes to the picture with upper left corner (2,1) and lower right corner (3,2), which has an attractiveness index of 0+11+100+0=111.
SAMPLE INPUT:
3 1
3
2 2 3
2 2 5
2 2 7
SAMPLE OUTPUT:
3
5
7
There is only one cow with a positive beauty value, so the maximum attractiveness index will always include that cow.
SCORING:
Inputs 3-6: N <= 50, Q <= 100
Inputs 7-10: N <= 50
Inputs 11-18: No additional constraints.
2
题意重述
题目要求在一个 的网格中，不断更新某个格子的分值，并实时求出全图中所有 区域的最大分值总和。发生 次事件，每次它的美丽值会增加（变成一个新的值 ）。题目保证新值一定比旧值大。
如果我们每次更新后都去遍历所有的 区域，每次更新后：枚举所有 K×K 的窗口，计算它们的总和，取最大值：
计算量是：这绝对会超时。
3
解题思路
1.关键点
2.如何更新
4
代码参考
向上滑动阅览
import sys
def main():
input = sys.stdin.readline
N, K = map(int, input().split())
Q = int(input())
# 0-based indexing
grid = [[0] * N for _ in range(N)]
# 窗口数量
M = N - K + 1
# 窗口和，使用一维列表存储以提升访问速度
window = [0] * (M * M)
# 全局最大值
max_sum = 0
# 存储输出结果，最后一次性输出
results = []
for _ in range(Q):
x, y, e = map(int, input().split())
# 转换为0-based
x -= 1
y -= 1
delta = e - grid[x][y]
grid[x][y] = e
# 计算包含点(x,y)的窗口的左上角坐标范围
# 左上角(i,j)满足: i <= x <= i+K-1 且 j <= y <= j+K-1
# 所以 i 的范围: max(0, x-K+1) <= i <= min(x, M-1)
i_start = max(0, x - K + 1)
i_end = min(x, M - 1)
j_start = max(0, y - K + 1)
j_end = min(y, M - 1)
# 更新所有受影响的窗口
local_max = max_sum
# 遍历所有受影响的窗口
for i in range(i_start, i_end + 1):
# 行i的起始索引
base = i * M
for j in range(j_start, j_end + 1):
# 窗口在一维数组中的索引
idx = base + j
window[idx] += delta
if window[idx] > local_max:
local_max = window[idx]
max_sum = local_max
results.append(str(max_sum))
sys.stdout.write("n".join(results))
if __name__ == "__main__":
main()
