USACO历年黄金组真题解析 | 2007年10月

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

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

适合人群：

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

附上汇总贴：USACO历年黄金组真题解析 | 汇总

---

P6200 Super Paintball

【题目来源】

洛谷：[P6200 USACO07OCT] Super Paintball G - 洛谷

【题目描述】

奶牛们最近从玩具商那里，买来了一套仿真版彩弹游戏设备（类似于真人 CS）。Bessie 把她们玩游戏的草坪划分成了 \(N \times N\) 的矩阵（\(1 \leq N \leq 100\)），同时他算出了她的 \(K\) 个对手在草地上的位置（\(1 \leq K \leq 10^5\)），现在你需要帮 Bessie 算些东西。

在这个游戏中，奶牛们用一把枪向八个方向中的任意一个方向射出子弹，这八个方向分别是：正北，正南，正东，正西，东北，东南，西北，西南（东北指北偏东 \(45^\circ\)，东南，西北，西南同理）。

Bessie 想要你算出，有多少个位置可以让她射到所有对手。特别地，Bessie 可以和她的某一个对手站在同一格子，这时候她可以射到和她同一格子的对手。

【输入】

第一行两个整数 \(N, K\)。

接下来 \(K\) 行，每行两个整数 \(R_i, C_i\)，表示第 \(i\) 头奶牛在第 \(R_i\) 行第 \(C_i\) 列。可能有两个奶牛在同一位置上。

【输出】

输出 Bessie 可以选择的格子数目。

【输入样例】

4 3
2 1
2 3
4 1

【输出样例】

5

【解题思路】

【算法标签】

《洛谷 P6200 Super Paintball》 #USACO# #2007#

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, k, a[105][105], ans=0;
int main()
{
    cin >> n >> k;  // 输入n和k
    for (int i=1; i<=k; i++) {  // 输入k个对手位置
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;  // 每个位置标记为1
    }
    for (int i=1; i<=n; i++) {  // 遍历N*N矩阵
        for (int j=1; j<=n; j++) {
            int cnt = 0;
            if (a[i][j]==1) cnt++;  // 如果站在对手的格子上，统计值加1
            for (int k=1; k<=n; k++) {  // 向左扫描
                if (j-k>=1 && a[i][j-k]==1 ) cnt++;
            }
            for (int k=1; k<=n; k++) {  // 向右扫描
                if (j+k<=n && a[i][j+k]==1) cnt++;
            }   
            for (int k=1; k<=n; k++) {  // 向上扫描
                if (i-k>=1 && a[i-k][j]==1) cnt++;
            }
            for (int k=1; k<=n; k++) {  // 向下扫描
                if (i+k<=n && a[i+k][j]==1) cnt++;
            }
            for (int k=1; k<=n; k++) {  // 向左上扫描
                if (i-k>=1 && j-k>=1 && a[i-k][j-k]==1) cnt++;
            }
            for (int k=1; k<=n; k++) {  // 向右下扫描
                if (i+k<=n && j+k<=n && a[i+k][j+k]==1) cnt++;
            }
            for (int k=1; k<=n; k++) {  // 向左下扫描
                if (i+k<=n && j-k>=1 && a[i+k][j-k]==1) cnt++;
            }
            for (int k=1; k<=n; k++) {  // 向右上扫描
                if (i-k>=1 && j+k<=n && a[i-k][j+k]==1) cnt++;
            }
            if (cnt==k) {  // 如果统计值为k，说明所有对手都可以给射到
                ans++;  // 位置数加1
            }
        }
    }
    cout << ans << endl;  // 输出位置数
    return 0;
}

【运行结果】

4 3
2 1
2 3
4 1
5