USACO历年青铜组真题解析

USACO历年青铜组真题解析 | 2026年1月

2026-02-02 21:13:31 栏目：最新资讯 14 阅读

欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
希望系统学习C++/Python编程的初学者
想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客

P14974 Chip Exchange

【题目来源】

洛谷：[P14974 USACO26JAN1] Chip Exchange B - 洛谷

【题目描述】

奶牛 Bessie 拥有 $A$ 个 A 型芯片和 $B$ 个 B 型芯片（ $10^9$ ）。她可以按意愿多次执行以下操作：

如果你至少有 $c_B$ 个 B 型芯片，则可以用 $c_B$ 个 B 型芯片交换 $c_A$ 个 A 型芯片（ $c_A,c_Ble 10^9$ ）。

请你确定一个最小的非负整数 $x$ ，使得以下条件成立：在收到 $x$ 个额外的随机芯片后，可以保证 Bessie 最终能够拥有至少 $f_A$ 个 A 型芯片（ $f_Ale 10^9$ ）。

【输入】

第一行包含 $T$ ，表示独立测试用例的数量（ $10^4$ ）。

接下来是 $T$ 个测试用例，每个用例由五个整数 $A$ 、 $B$ 、 $c_A$ 、 $c_B$ 、 $f_A$ 组成。

【输出】

每个测试用例的答案输出在单独的一行。

注意：本题涉及的大整数可能需要使用 64 位整数数据类型（例如，C/C++ 中的 “long long”）。

【输入样例】

2
2 3 1 1 6
2 3 1 1 4

【输出样例】

1
0

【算法标签】

《洛谷 P14974 Chip Exchange》 #数学# #贪心# #分类讨论# #USACO# #2026#

【代码详解】

#include 
using namespace std;

#define int long long  // 将int定义为long long类型，避免大数溢出

int t, a, b, ca, cb, fa;  // t: 测试用例数量，a: 当前资源A数量，b: 当前资源B数量，ca: 每次转换获得的A数量，cb: 每次转换需要的B数量，fa: 目标A资源数量

signed main()  // 使用signed main()替代int main()，因为int被重定义为long long
{
    cin >> t;  // 读入测试用例数量
    
    while (t--)  // 处理每个测试用例
    {
        cin >> a >> b >> ca >> cb >> fa;  // 读入当前资源情况和目标
        
        int ans = 0;  // 初始化答案变量（未使用）
        
        // 先将现有的B资源尽可能转换为A资源
        // 计算可转换的次数：b / cb
        // 每次转换获得ca个A资源
        a += b / cb * ca;
        // 剩余不足一次转换的B资源
        b %= cb;
        
        // 如果转换后A资源已达到或超过目标
        if (a >= fa)
        {
            cout << 0 << endl;  // 无需额外操作
        }
        // 如果每次转换获得的A数量 >= 需要的B数量（转换效率高或相等）
        else if (ca >= cb)
        {
            // 需要额外获得的A资源数量
            int numa = fa - a - 1;
            // 需要额外获得的B资源数量（补足到下一次转换）
            int numb = cb - b;
            // 总成本为两者之和
            cout << numa + numb << endl;
        }
        // 如果每次转换获得的A数量 < 需要的B数量（转换效率低）
        else if (ca < cb)
        {
            // 需要额外获得的A资源数量（取模，表示无法通过完整转换获得的部分）
            int numa = (fa - a - 1) % ca;
            // 计算需要完整转换的次数，并转换为需要的B资源数量
            int numb = ceil(1.0 * (fa - a) / ca) * cb - b;
            // 总成本为两者之和
            cout << numa + numb << endl;
        }
    }
    
    return 0;
}