语法周赛round16

T1 公园门票

本题考查数学题，题意就是有 $x$ 个成人 $y$ 个儿童，求花费多少钱购买门票。

• 成人票 $60$ 元。
• 儿童票 $40$ 元。
• 一大一小 $90$ 元。

可以看出一大一小优于单独购买成人和儿童。

主要考察 if 语句的使用。

• 当 $x>y$，可以优先购买一大一小的票，剩下的再单独购买。总花费为：

\[ \text{花费} = 90 \cdot y + 60 \cdot (x - y) \]

• 当 $x \leq y$，可以优先购买一大一小的票，剩下的再单独购买。总花费为：

\[ \text{花费} = 90 \cdot x + 40 \cdot (y - x) \]

---

T2 口算练习

本题考查 floor 函数的使用，题目给定两个数字 $x,y$。求出 $\lfloor \frac{x}{y} \rfloor$ 的值。

注意实现时要转化为 double 类型进行除法运算，避免整数除法。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, y;
    cin >> x >> y;
    cout << floor(x * 1.0 / y); // 注意要转换为 double 类型
    return 0;
}

---

T3 课程QQ群

本题考查简单循环，输入 $n$ 个数字，求有多少个数字等于给定的数字 $k$，可以通过 for 结合 if 语句完成。

int n, k;
cin >> n >> k;
int count = 0;
for (int i = 1; i <= n; i++)
{
    int x;
    cin >> x;
    if (x == k)
    {
        count++;
    }
}

---

T4 集卡

题目大意：判断输入的 $n$ 个数字内是否有 $0$，如果有则输出 yes，否则输出 no。

可以通过打标记的思想实现。

• 初始化一个标记变量 bool ok = 0。
• 遍历输入的数字，如果有一个数字是 $0$，就将 ok 设为 1。
• 最后判断 ok 的值，如果是 1，则输出 yes，否则输出 no。

注意本题是多组数据。

int t;
cin >> t;
while (t--)
{
    int n;
    cin >> n;
    bool ok = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x == 0)
        {
            ok = 1; // 有一个数字是 0
        }
    }
    if (ok)
    {
        cout << "yes" << endl;
    }
    else
    {
        cout << "no" << endl;
    }
}

---

T5 排排队

本题考察数组的遍历。

• 将输入的数字存储到数组内。
  • 使用 int a[10005] 存储。
  • 因为题目 $n\leq 10^4$，所以数组大小设置为 $10005$。
  • 因为题目 $a_i\leq 10^9$，所以使用 int 类型即可。
• 然后遍历数组，若 a[i] 是奇数就输出 a[i]。
• 再一次遍历数组，若 a[i] 是偶数就输出 a[i]。

for (int i = 1; i <= n; i++) {
    if (a[i] % 2 == 1) {
        cout << a[i] << " ";
    }
}

cout << endl;

for (int i = 1; i <= n; i++) {
    if (a[i] % 2 == 0) {
        cout << a[i] << " ";
    }
}

---

T6 山峰

这道题是要我们将一个 $n$ 行 $m$ 列的二维数组的数值进行 $T$ 次交换，然后找出所有比四个方向都高的根站(山峰)的坐标，并返回山峰的数量和各自坐标。

思路

• 先用二维数组 int a[1005][1005] 存储初始海报数据
• 执行 $T$ 次交换：swap(a[x1][y1], a[x2][y2])
• 遍历全地图，查看每一块地的上下左右，如果都比它小，则是山峰
• 把山峰的坐标保存起来

具体实现中使用了方向数组和 vector<pair<int, int>> 两个技巧实现。

方向数组是什么？

方向数组就是把坐标的变化量存起来，这样通过变化量访问到周围的格子。

例如本题需要访问一个格子的上下左右四个相邻的位置。

假如中间位置是 $(x,y)$，则上方为 $(x-1,y)$，下方为 $(x+1,y)$，左方为 $(x,y-1)$，右方为 $(x,y+1)$。

• 行方向的变化量分别为：-1, 1, 0, 0
• 列方向的变化量分别为：0, 0, -1, 1

这个时候创建两个数组储存这两个变化量。

• int dx[4] = {-1, 1, 0, 0};
• int dy[4] = {0, 0, -1, 1};

那么访问 $(x,y)$ 的上方位置就是 (x-1,y)，即 (x+dx[0],y+dy[0])。

通过循环遍历即可求出其余位置。

for (int i = 0; i < 4; i++)
{
    int nx = x + dx[i], ny = y + dy[i];

}

• vector学习

代码

int a[N][N];
// 方向数组
int dx[4] = {-1, 1, 0, 0}; 
int dy[4] = {0, 0, -1, 1}; 

int main() {

    int T;
    cin >> T;
    while (T--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        swap(a[x1][y1], a[x2][y2]);
    }

    vector<pair<int, int>> ans;

    // 遍历所有地方
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            bool ok =1;
            for (int d = 0; d < 4; ++d) {
                int ni = i + dx[d];
                int nj = j + dy[d];
                // 首先确保相邻位置还在矩阵内
                if (ni >= 1 && ni <= n && nj >= 1 && nj <= m) {
                    // 若相邻格子高度大于等于中间的，则不是山峰。
                    if (a[ni][nj] >= a[i][j]) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) {
                ans.push_back({i, j});
            }
        }
    }

    cout << ans.size() << endl;
    for (auto p : ans) {
        cout << p.first << " " << p.second << endl;
    }

}

---

T7 广告

这道题要求我们计算字符串 S 里，子串 luogu 出现了多少次，即查找 S 中有多少次 luogu这个字串。

子串是按顺序且持续的字符，不能跳过任何一个位置。

思路

• 用 C++ 输入字符串 S
• 用一个循环遍历 S，查看是否有字符串 "luogu"
• 可以用 string 字符串的 substr 方法条件判断
  • substr函数学习
• 每次找到，计数器加一

代码

int count = 0;
string target = "luogu";
// i, i+1, i+2, i+3, i+4 这五个字符分别等于 luogu
// 每个位置开始寻找 5 个字符是否是 "luogu"
for (int i = 0; i + 4 < s.size(); ++i) {
    if (s.substr(i, 5) == target) {
        count++;
    }
}

---

T8 零食售卖点

我们要做的是：

• 先把所有售卖点位置按照数轴上排好顺序
• 然后看下相邻两个点之间的距离最大是多少

思路

• 先输入 $k$ 和位置 $a[0] \sim a[k-1]$
• 将数组 $a$ 进行排序，使其按照小到大
• 遍历相邻点，每次算 $a[i+1] - a[i]$，记录最大的值

代码

#include <bitts/stdc++.h>
using namespace std;
int a[5005];
int main() {
    int k;
    cin >> k;

    for (int i = 0; i < k; ++i) {
        cin >> a[i];
    }

    // 将数组排序
    sort(a, a + k); // 将 a[0] ~ a[k-1] 按照升序排序

    int ans = 0;
    for (int i = 0; i < k - 1; ++i) {
        int dist = a[i+1] - a[i];
        if (dist > ans) {
            ans = dist;
        }
    }

    cout << ans;
    return 0;
}

说明

• 这里使用 C++ 标准库的 sort 函数，可将数组的指定区间排序
• sort(a, a + k) 表示排序 $a[0]$ 到 $a[k-1]$

sort 函数的复杂度是 $O(n\log n)$，其中 $n$ 是数组的长度。

函数的语法规则：sort(首元素地址， 末尾元素地址)。

int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
    cin >> a[i];
}
sort(a + 1, a + n + 1); // 排序 a[1] 到 a[n]

注意

• 数组下标从 0 开始，所以如果要排序 $a[0]$ 到 $a[n-1]$，则需要使用 sort(a, a + n)。
• 如果是从 1 开始的数组，则需要使用 sort(a + 1, a + n + 1)。

默认从小到大排序，如果想使用从大到小排序，可以传入第三个参数 greater<int>()。尖括号内的 int 取决于数组元素的类型。不是一成不变。

例如：sort(a, a + n, greater<int>())。sort(a + 1, a + n + 1, greater<int>())。