USACO历年青铜组真题解析 | 2019年2月

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

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

适合人群：

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

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

P1693 Sleepy Cow Herding

【题目来源】

洛谷：[P1693 USACO19FEB] Sleepy Cow Herding B - 洛谷 (luogu.com.cn)

【题目描述】

Farmer John的三头获奖奶牛Bessie、Elsie和Mildred，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。

农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这3头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据三个相邻的位置（例如，位置\(6\)、\(7\)、\(8\)）。

不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

【输入】

输入包含一行，包括三个空格分隔的整数，为Bessie、Elsie和Mildred的位置。每个位置均为一个范围\(1\dots 10^9\)内的整数。

【输出】

输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。

【输入样例】

4 7 9

【输出样例】

1
2

【解题思路】

【算法标签】

《洛谷 P1693 Sleepy Cow Herding》 #USACO# #O2优化# #2019#

【代码详解】

#include <bits/stdc++.h>
using namespace std;

int a[5];           // 存储三个奶牛的位置
int minn = 0;       // 最小移动次数
int maxn = 0;       // 最大移动次数

// 文件输入输出流（注释掉的代码）
// ifstream filein("herding.in");
// ofstream fileout("herding.out");

int main()
{
    // 输入三个奶牛的位置
    for (int i = 1; i <= 3; i++)
    {
        // cin >> a[i];
        // filein >> a[i];
        cin >> a[i];
    }
  
    // 对三个位置进行排序（从小到大）
    sort(a + 1, a + 3 + 1);
  
    // 情况1：三个奶牛已经连续相邻（间隔都为1）
    if (a[2] - a[1] == 1 && a[3] - a[2] == 1)
    {
        // 无需移动
        cout << 0 << endl << 0 << endl;
    }
    // 情况2：两个间隔分别为2和1（如：1,3,4 或 1,2,4）
    else if ((a[2] - a[1] == 2 && a[3] - a[2] == 1) || (a[2] - a[1] == 1 && a[3] - a[2] == 2))
    {
        // 只需要移动一次即可使三个奶牛连续
        cout << 1 << endl << 1 << endl;
    }
    // 情况3：两个间隔都为2（如：1,3,5）
    else if (a[2] - a[1] == 2 && a[3] - a[2] == 2)
    {
        // 只需要移动一次即可使三个奶牛连续
        cout << 1 << endl << 1 << endl;
    }
    // 情况4：一个间隔大于2，另一个间隔为1（如：1,4,5 或 1,2,5）
    else if ((a[2] - a[1] > 2 && a[3] - a[2] == 1) || (a[2] - a[1] == 1 && a[3] - a[2] > 2))
    {
        minn = 2;  // 最小需要移动2次
        maxn = max(a[2] - a[1] - 1, a[3] - a[2] - 1);  // 最大移动次数为较大间隔减1
        cout << minn << endl << maxn << endl;
    }
    // 情况5：一个间隔大于2，另一个间隔为2（如：1,4,6 或 1,3,6）
    else if ((a[2] - a[1] > 2 && a[3] - a[2] == 2) || (a[2] - a[1] == 2 && a[3] - a[2] > 2))
    {
        minn = 1;  // 最小需要移动1次
        maxn = max(a[2] - a[1] - 1, a[3] - a[2] - 1);  // 最大移动次数为较大间隔减1
        cout << minn << endl << maxn << endl;
    }
    // 情况6：两个间隔都大于2（如：1,5,10）
    else if (a[2] - a[1] > 2 && a[3] - a[2] > 2)
    {
        minn = 2;  // 最小需要移动2次
        maxn = max(a[2] - a[1] - 1, a[3] - a[2] - 1);  // 最大移动次数为较大间隔减1
        cout << minn << endl << maxn << endl;
    }
  
    return 0;
}

【运行结果】

4 7 9
1
2

P1694 The Great Revegetation

【题目来源】

洛谷：[P1694 USACO19FEB] The Great Revegetation B - 洛谷

【题目描述】

长时间的干旱使得 Farmer John 的 \(N\) 块草地上牧草匮乏。随着雨季即将到来，现在应当是重新种植的时候了。

在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。他的 \(M\) 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以有两种草可供选择。Farmer John 知道没有一块草地受到多于 \(3\) 头奶牛的喜爱。

请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。

【输入】

输入的第一行包含 \(2 \leq N \leq 100\) 和 \(1 \leq M \leq 150\)。以下 \(M\) 行，每行包含两个范围为 \(1 \dots N\) 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。

【输出】

输出一个 \(N\) 位数，每一位均为 \(1\ldots 4\) 之一，表示每一块草地上所种的草的种类。第一位对应草地 \(1\) 的草的种类，第二位对应草地 \(2\)，以此类推。如果有多种可行的解，只需输出所有解中最小的 \(N\) 位数。

【输入样例】

【输出样例】

【解题思路】

【算法标签】

《洛谷 P1694 The Great Revegetation》 #贪心# #USACO# #O2优化# #2019#

【代码详解】

// 尝试用过贪心算法，后发现只有3个测试点通过，其余均超时
#include <bits/stdc++.h>
using namespace std;
int a1[105][105], G[105];
int n, m;
// ifstream filein("revegetate.in");
// ofstream fileout("revegetate.out");
int main()
{
    cin >> n >> m;  // 输入n和m

    for (int i=1; i<=m; i++) {  // 遍历m条边
        int a, b;
        cin >> a >> b;  // 输入边的端点
        a1[a][b] = 1;  // 因为是无向图，所以边的两个方向均置为1
        a1[b][a] = 1;
    }
    for (int i=1; i<=n; i++) {  // 遍历n个顶点
        int k;  // 定义颜色（没放到循环中是因为后面要通过G[i]来赋值）
        for (k=1; k<=4; k++) {  // 遍历4个颜色
            bool ok=true;  // 定义ok，用于判断边的两个端点颜色是否冲突
            for (int j=1; j<=n; j++) {  // 再遍历n个顶点
                if (a1[i][j]==1 && G[j]==k) {  // 如果i和j是一条边上的两个顶点，且j这个点的颜色为k（即已经有颜色了）
                    ok =false;  // 修改ok为false
                }
            }
            if (ok) break;  // 没有一条边上的两个顶点颜色冲突，则退出循环，即颜色留在当前k上
        }
        G[i] = k;  // 将这个k赋值给G[i]
    }
    for (int i=1; i<=n; i++) {  // 遍历n个顶点
        cout << G[i];  // 将每个顶点的颜色打印出来，中间不空格
    }
    cout << endl;
    return 0;
}

【运行结果】

posted @ 2026-02-05 11:06 热爱编程的通信人阅读(2) 评论(0) 收藏举报

刷新页面返回顶部

guolianggsta

USACO历年青铜组真题解析 | 2019年2月

P1693 Sleepy Cow Herding

P1694 The Great Revegetation

公告