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

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

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

适合人群：

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

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

P9944 Comfortable Cows

【题目来源】

洛谷：[P9944 USACO21FEB] Comfortable Cows B - 洛谷

【题目描述】

Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。初始时，草地上是空的。

Farmer John 将会逐一地将 \(N\)（\(1\le N\le 10^5\)）头奶牛加入到草地上。第 \(i\) 头奶牛将会占据方格 \((x_i,y_i)\)，不同于所有已经被其他奶牛占据的方格（\(0\le x_i,y_i\le 1000\)）。

一头奶牛被称为是「舒适的」，如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对 \(1\ldots N\) 中的每一个 \(i\)，输出第 \(i\) 头奶牛加入到草地上之后舒适的奶牛的数量。

【输入】

输入的第一行包含一个整数 \(N\)。以下 \(N\) 行每行包含两个空格分隔的整数，表示一头奶牛所在的方格坐标 \((x,y)\)。输入保证所有方格的坐标是不同的。

【输出】

输出的第 \(i\) 行包含前 \(i\) 头奶牛加入到草地上之后舒适的奶牛的数量。

【输入样例】

【输出样例】

【解题思路】

【算法标签】

《洛谷 P9944 Comfortable Cows》 #USACO# #O2优化# #2021#

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, res=0, cnt=0;
int a[1005][1005];
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
int main()
{
    cin >> n;  // 输入n
    for (int i=1; i<=n; i++) {  // 遍历n头奶牛
        int x, y;  // 定义每头奶牛的坐标x和y
        int cnt1=0, cnt2=0;  // 定义添加前和添加后舒适量的统计
        cin >> x >> y;  // 输入奶头的坐标
        for (int i=x-1; i<=x+1; i++) {  // 遍历这台奶牛周围，计算添加之前的舒适量
            for (int j=y-1; j<=y+1; j++) {
                int ans=0;  // 定义周围奶牛的数量，初始为0
                if (a[i][j]==1) {  // 如果该位置有奶牛
                    for (int k=0; k<4; k++) {  // 则判断周围4个方向是否有奶牛
                        int xx = i + dx[k];
                        int yy = j + dy[k];
                        if (xx<0 || yy<0) continue;
                        if (a[xx][yy]==1) ans++;  // 有的话，ans自增
                    }
                    if (ans==3) cnt1++;  // 如果ans为3，则舒适的奶牛数量加1
                }
            }
        }
        a[x][y] = 1;  // 添加输入的奶牛
        for (int i=x-1; i<=x+1; i++) {  // 再次遍历这台奶牛周围，计算添加之后的舒适量
            for (int j=y-1; j<=y+1; j++) {
                int ans=0;
                if (a[i][j]==1) {
                    for (int k=0; k<4; k++) {
                        int xx = i + dx[k];
                        int yy = j + dy[k];
                        if (xx<0 || yy<0) continue;
                        if (a[xx][yy]==1) ans++;
                    }
                    if (ans==3) cnt2++;  // 如果ans为3，则舒适的奶牛数量加1
                }
            }
        }
        res += cnt2-cnt1;  // 计算前后的变化，并累加到ans中（有时相减会变为负数）
        cout << res << endl;  // 最后打印结果
    }
    return 0;
}

【运行结果】

P9945 Clockwise Fence

【题目来源】

洛谷：[P9945 USACO21FEB] Clockwise Fence B - 洛谷

【题目描述】

围绕 Farmer John 最大的草地的栅栏已经损坏了，如今他终于决定要换一个新的栅栏。

不幸的是，当 Farmer John 在铺设新栅栏时，一只巨大的蜜蜂突然出现，在他的草地上追着他跑，导致最后栅栏被沿着一条相当不规则的路径铺设。栅栏可以用一个字符串表示，每个字符为 N（north，北）、E（east，东）、S（south，南）、W（west，西）之一。每个字符表示一米长的一段栅栏。举例来说，如果字符串为 NESW，这表示栅栏从起点开始向北延伸 \(1\) 米，然后向东延伸 \(1\) 米，然后向南延伸 \(1\) 米，然后向西延伸 \(1\) 米，回到栅栏的起点。

栅栏的结束位置与开始位置相同，而这是栅栏的路径上唯一会被到达多次的位置（从而起始位置是唯一会被再次到达的位置，在栅栏结束之时）。结果，栅栏确实围起了一个草地上连通的区域，尽管这个区域可能形状十分奇特。

Farmer John 想要知道他铺设栅栏的路径是顺时针（当按字符串表示的顺序沿着栅栏的路径行走时被围起的区域位于右侧）还是逆时针（被围起的区域位于左侧）。

【输入】

输入的第一行包含一个整数 \(N\)（\(1\le N\le 20\)）。以下 \(N\) 行每行包含一个长度不小于 \(4\) 且不超过 \(100\) 的字符串，表示一个栅栏的路径。

【输出】

对 \(N\) 条输入的栅栏路径的每一条，输出一行，为 CW（clockwise，顺时针）或 CCW（counterclockwise，逆时针）。

【输入样例】

2
NESW
WSSSEENWNEESSENNNNWWWS

【输出样例】

CW
CCW

【算法标签】

《洛谷 P9945 Clockwise Fence》 #USACO# #O2优化# #2021#

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, ans;
string s;
int d[4][4] = {  // 定义二维数组，E为0，W为1，S为2，N为3，每个单元格的值为方向变化后的角度变化
    {0,0,90,-90},
    {0,0,-90,90},
    {-90,90,0,0},
    {90,-90,0,0}
};
int main()
{
    cin >> n;  // 输入n
    for (int i=1; i<=n; i++) {  // for循环遍历n次询问
        cin >> s;  // 输入字符串s
        s = s + s[0];  // 因为最后要回到原点，所以在字符串最后加上起始字符
        ans = 0;  // 每轮询问角度统计都要归零
        for (int i=0; i<s.length()-1; i++) {  // for循环遍历s.length()-2个字符，因为要比较i与i+1
            int x, y;  // 定义x和y坐标
            if (s[i]=='E') x=0;  // 根据i的字符确定x坐标
            if (s[i]=='W') x=1;
            if (s[i]=='S') x=2;
            if (s[i]=='N') x=3;

            if (s[i+1]=='E') y=0;  // 根据i+1的字符确定y坐标
            if (s[i+1]=='W') y=1;
            if (s[i+1]=='S') y=2;
            if (s[i+1]=='N') y=3;

            if (d[x][y]) ans += d[x][y];  // 当掉转角度不为0时，加上角度的变化。
        }
        if (ans==360) cout << "CW" << endl;  // 当为360度时，说明是顺时针转回来
        else if (ans==-360) cout << "CCW" << endl;  // 当为-360度时，说明是逆时针转回来
    }
  
    return 0;
}

【运行结果】

2
NESW
CW
WSSSEENWNEESSENNNNWWWS
CCW

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

刷新页面返回顶部

guolianggsta

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

P9944 Comfortable Cows

P9945 Clockwise Fence

公告