“码蹄杯” 全国职业院校程序设计大赛（决赛）

1. 消除小球

题目

小码哥最近在玩一个叫消除小球的游戏，这个游戏在一个一端封闭的垂直管道上进行。初始管道中没有任何小球。当游戏开始后，每回合系统会随机生成几种颜色，玩家需要从这几种颜色中选择一种，随后被选中颜色的小球会从管道顶部进入，并落到管道中原先小球的顶部（若管道为空，则落到管道的底部）。

和大部分消除类游戏一样，在这个游戏中，若存在连续的 $k$ 个相同颜色的小球，则他们会被消除。根据游戏难度， $k$ 在游戏开始前就会被设置，且在整场游戏中不会改变。

现在小码哥告诉你游戏难度参数 $k$ ，以及他在每回合选择的小球的颜色，希望你能够告诉他游戏结束时管道中剩余小球的状态。

格式

输入格式：

第一行输入两个整数 $n$ 、 $k (1 \leq n \leq 10^5, 2 \leq k \leq 100)$ ，分别表示进行的游戏总回合数和游戏难度参数。
接下来一行输入一个长度为 $n$ 的仅包含小写字母的字符串 $s$ ，其中第 $i$ 个字符 $s_i$ 表示第 $i$ 回合小码哥选择的颜色。不同字母代表不同的颜色。

输出格式：

输出一个字符串 $t$ ，其中第 $i$ 个字符表示管道中自底向上第 $i$ 个小球的颜色。若最后管道为空，则输出 >_<。

样例 1

输入：

5 2
abbab

输出：

样例 2

输入：

6 3
aabbba

输出：

>_<

解题

方法一：模拟

思路

根据题目模拟，先建一个空串(s)，每次读入一个字符(ch)，然后查找前 k-1 个字符，如果都与 ch 相等的话就把这些字符删除，否则把 ch 加入字符串，全部读取、操作完成后输出 s 即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
char s[N];
int n, k;

int main() {
    scanf("%d%d", &n, &k);
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    int i = 0;
    while (n--) {
        char ch;
        scanf("%c", &ch);
        s[i++] = ch;
        if (i < k) continue;
        for (int j = i - 2; j >= i - k; --j) {
            if (s[j] != ch) goto out;
        }
        i = i - k;
        out:;
    }
    if (i) {
        for (int j = 0; j < i; ++j) printf("%c", s[j]);
    }
    else printf(">_<\n");

    return 0;
}

2. 因数

题目

码题集OJ-因数

给定一个整数 $n$ ，定义 $n$ 的一个因子 $y$ 为 $k$ 次因子，当且仅当存在因子 $x$ ，满足 $x^k = y$ 。注意，这里的 $x,y$ 可以相等。

现在知道了数字 $n,k$ ，请你输出 $n$ 的所有 $k$ 次因子。由于因子 $1$ 比较特殊，它是任何数字的任意 $k$ 次因子。所以对于输入的整数 $n$ ，当只有因子 $1$ 满足要求时请输出 onlyone。

格式

输入格式：

一行输入两个数 $n,k(1 \leq n \leq 2000, 1 \leq k \leq 10)$ 。

输出格式：

在一行中从小到大输出 $n$ 的所有 $k$ 次因子。如果只有因子 $1$ 满足要求，则输出 onlyone。

样例 1

输入：

12 1

输出：

1 2 3 4 6 12

样例 2

输入：

81 2

输出：

1 9 81

样例 3

输入：

13 2

输出：

onlyone

解题

方法一：暴力枚举

思路

把 n 的所有因素枚举出来放入集合(factors)中去重，然后遍历集合，把遍历到的因子当作 x，查找 factors 中是否存在 $y=x^k$ ，如果存在就把 $x^k$ 加入结果数组。完成后按题目要求输出结果数组。

代码

#include <bits/stdc++.h>

using namespace std;

int n, k;

int main() {
    scanf("%d%d", &n, &k);
    set<int> factors;
    for (int x = 1; x <= n; ++x) {
        if (!(n % x)) factors.insert(x);
    }
    vector<int> ans;
    for (int x : factors) {
        if (factors.find(pow(x, k)) != factors.end()) {
            ans.push_back(pow(x, k));
        }
    }
    if (ans.size() == 1) printf("onlyone\n");
    else {
        for (int& x : ans) printf("%d ", x);
    }

    return 0;
}

3. 迷宫

4. 砸键盘

题目

码题集OJ-砸键盘

某一天，小码哥的电脑又死机了。

但好消息是，这次没开游戏。坏消息是，这次在赶ddl并且写了3h没有保存。

于是，小码哥已经不想向小码妹求助了，他怒气冲冲地开始砸起了键盘。

小码妹一边看着小码哥现在潇洒的砸键盘的样子，一边想着之后他哭天喊地赶ddl的样子，不由叹气。

这时候小码妹突然想起一个问题，假如小码哥的键盘是26个键位，且连成了一条直线，并且每次小码哥砸键盘的时候恰好都是砸一段连续的键位。

小码妹想知道，当小码哥砸了m次键盘后停止砸键盘时，每个键位被砸了几次？

格式

输入格式：

第一行输入26个小写字母，表示小码哥的键盘的键位排布。保证键盘包含了所有小写字母。
第二行输入一个整数 $m(1 \leq m \leq 10^5)$ ，表示小码哥砸了 $m$ 次键盘。
接着输入 $m$ 行，每行输入两个整数 $l, r(1 \leq l \leq r \leq 26)$ ，表示某一次小码哥砸中了键盘区间 $[l,r]$ 内的字母。

输出格式：

一行输出26个空格分隔的整数，从左到右依次为字母a被砸中的次数，字母b被砸中的次数……直到字母z被砸中的次数。

样例 1

输入：

abcdefghijklmnopqrstuvwxyz
3
1 26
1 10
19 23

输出：

2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 1

样例 2

输入：

aymrnptzhklcbuxfdvjsgqweio
2
2 9
18 21

输出：

0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1

解题

方法一：差分哈希表

思路

先维护一个哈希表(mp)（数组代替）映射键位顺序，然后建一个差分数组(diffs)，把所有区间操作在差分数组上完成（「差分数组基础」）后求前缀和就得到了原数组，最后遍历原数组根据映射的顺序输出每个键的计数即可。

代码

#include <bits/stdc++.h>

using namespace std;

string s;
int m;
int diffs[27], mp[26];

int main() {
    getline(cin, s);
    scanf("%d", &m);
    for (int i = 0; i < 26; ++i) mp[s[i] - 'a'] = i;
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        ++diffs[l - 1];
        --diffs[r];
    }
    for (int i = 1; i < 26; ++i) diffs[i] += diffs[i - 1];
    for (int i = 0; i < 26; ++i) printf("%d ", diffs[mp[i]]);

    return 0;
}

5. 魔方

题目

码题集OJ-魔方

小码哥最近在玩魔方。和平常的三维魔方不同，小码哥的魔方是一个由 $9$ 个格子组成的 $3 \times 3$ 的二维魔方。每个格子的颜色为红、绿、蓝三种颜色中的一种。

初始魔方的第一行为红色，第二行为绿色，第三行为蓝色。魔方的每个操作都由编号加字母组成的字符串表示。其中字母只会从 L、R、U、D 中选择，表示移动方向。编号从 $1,2,3$ 中选择，其具体代表行还是列依据移动方向进行判断。当执行一次操作后，选择的那行（列）会在那个方向上进行一步循环位移操作。

如在初始状态下进行了一次 3U 操作后，魔方的状态如下图所示：

再进行一步 2L 操作后，魔方的状态如下图所示：

现在给定一系列操作，请你计算一下若从初始状态开始依次执行这些操作，最后魔方会达到怎样的状态。

格式

输入格式：

第一行输入一个整数 $n(1 \leq n \leq 10^3)$ ，表示操作次数。
接下来输入 $n$ 行，每行输入一个由编号加字母组成的操作。

输出格式：

输出 $3$ 行，每行 $3$ 个字母，表示 $n$ 次操作后魔方的状态。字母只包含 r、g、b三种，分别表示红色、绿色和蓝色。

样例 1

输入：

3
3U
2L
1D

输出：

brg
rbg
gbr

解题

方法一：模拟

思路

模拟所有魔方操作然后输出魔方即可，见代码。

代码

#include <bits/stdc++.h>

using namespace std;

char cube[3][3] = {{'r', 'r', 'r'},
                 {'g', 'g', 'g'},
                 {'b', 'b', 'b'}};

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int num;
        char ope;
        scanf("%d%c", &num, &ope);
        --num;
        char tmp;
        switch (ope) {
            case 'L':
                tmp = cube[num][0];
                cube[num][0] = cube[num][1];
                cube[num][1] = cube[num][2];
                cube[num][2] = tmp;
                break;
            case 'R':
                tmp = cube[num][2];
                cube[num][2] = cube[num][1];
                cube[num][1] = cube[num][0];
                cube[num][0] = tmp;
                break;
            case 'U':
                tmp = cube[0][num];
                cube[0][num] = cube[1][num];
                cube[1][num] = cube[2][num];
                cube[2][num] = tmp;
                break;
            case 'D':
                tmp = cube[2][num];
                cube[2][num] = cube[1][num];
                cube[1][num] = cube[0][num];
                cube[0][num] = tmp;
                break;
        }
    }
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) printf("%c", cube[i][j]);
        puts("");
    }

    return 0;
}

6. 吃蛋糕

7. 传送阵

题目

码题集OJ-传送阵

在泰拉大陆的某个角落，坐落着 $n$ 个传送门。这 $n$ 个传送门排列方式非常特别，它们排布在一条直线上，相邻传送门的间隔相等，且每个传送门都能够向某个方向传送一定的距离。

我们用一个长度为 $n$ 的数组 $a$ 来表示每个传送门的传送距离。进入第 $i$ 个传送门时，传送者会被传送到第 $i+a_i$ 个传送门。具体来讲，当 $a_i < 0$ 时，这个传送门会向前传送 $a_i$ 个单位；当 $a_i > 0$ 时，这个传送门会向后传送 $a_i$ 个单位；当 $a_i = 0$ 时，这个传送门被视为失效传送门（因为你只能待在原地）。

小码哥作为泰拉大陆的旅行者，进入传送门时会格外小心，因为稍不注意就会陷入传送循环。一个传送门被视为是循环的，当且仅当从该传送门出发，经过无限次传送仍然到达不了某个失效传送门而结束循环。

现在小码哥告诉你这 $n$ 个传送门的传送距离，希望你能够帮助他判断哪些传送门是循环的，哪些不是循环的。

格式

输入格式：

第一行输入一个整数 $n (1 \leq n \leq 2 \times 10^5)$ ，表示传送门个数。
第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n (|a_i| < n)$ 。 $a_i$ 表示第 $i$ 个传送门的传送距离。保证给出的传送距离不会传送到 $[1,n]$ 范围之外。

输出格式：

输出一个仅包含 Y 或 N 的长度为 $n$ 的字符串。第 $i$ 个字符为 Y 表示第 $i$ 个传送门为循环传送门，N 表示不是循环传送门。

样例 1

输入：

6
1 -1 1 -1 1 0

输出：

YYYYNN

样例 2

输入：

6
1 -1 -1 1 0 -1

输出：

YYYNNN

解题

方法一：并查集

思路

规定 0 为失效传送门，从 1 开始读入所有传送门，然后使用并查集把相连的传送门合并，合并完后查 $1\sim n$ 号门与 0 号门是否连接，如果连接说明该门不是循环传送门输出 'N'，否则输出 'Y'。

代码

#include <iostream>

using namespace std;

const int N = 2e5 + 10;
int roots[N];
int n;

int find(int x) {
    return x == roots[x] ? x : (roots[x] = find(roots[x]));
}

void join(int p, int q) {
    roots[find(p)] = find(q);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) roots[i] = i;
    for (int i = 1; i <= n; ++i) {
        int offset;
        scanf("%d", &offset);
        
        if (offset == 0) join(i, 0);
        else join(i, i + offset);
    }
    for (int i = 1; i <= n; ++i) printf(find(i) ? "Y" : "N");

    return 0;
}

8. 剪刀石头布

9. 特殊排列

题目

码题集OJ-特殊排列

一个排列是指一个长度为 $n$ 的数组 $p = [p_1,p_2,\dots,p_n]$ ，其包含 $1$ 到 $n$ 的整数恰好一次。如 $p = [1,5,4,2,3]$ 是一个长度为 $5$ 的排列。

给你 $3$ 个整数 $n,a,b$ ，其中 $n$ 是一个偶数。请你找到一个长度为 $n$ 的排列，满足排列前半部分所有元素的最小值为 $a$ ，后半部分所有元素的最大值为 $b$ 。如果你能找到这样的一个排列，则输出 YES，否则输出 NO。

格式

输入格式：

第一行输入一个整数 $T (1 \leq T \leq 1000)$ ，代表数组组数。接下来 $T$ 行每行描述一组数据。
对于每组数据，输入三个整数 $n,a,b (2 \leq n \leq 1000, 1 \leq a,b \leq n, a \neq b)$ ，保证输入的 $n$ 为偶数。

输出格式：

对于每组数组，输出一行 YES 或 NO，表示是否存在这样的排列。

样例 1

输入：

复制

输出：

YES
YES
NO

复制

备注

对于第一组数据，可以找到排列 $p = [1,2,6,4,5,3]$ ，满足前半部分最小值为 $1$ ，后半部分最大值为 $5$ 。
对于第二组数据，可以找到排列 $p = [5,6,7,8,1,2,3,4]$ 。

解题

方法一：找规律

思路

举例，对于序列 $[1, 2, 3, 4, 5, 6, 7, 8]$ $(n=8)$ ：

前半段最小值为 $a$ ，后半段最大值为 $b$ 。

$a$ 不能大于 $5$ ，如果大于 $5$ 就没有足够的元素给其组成前半段了，所以 a <= n / 2 + 1。
当 $a$ 等于 $5$ 时， $b$ 必须小于 $a$ ，如果 $b > a$ 的话也没有足够的元素组成前半段，所以 a == n / 2 + 1 && b < a
$b$ 不能大于 $4$ ，如果大于 $4$ 就没有足够的元素给其组成后半段了，所以 b >= n / 2。
当 $b$ 等于 $4$ 时， $a$ 必须大于 $b$ ，如果 $a < b$ 的话也没有足够的元素组成后半段，所以 b == n / 2 && a > b。

代码

#include <bits/stdc++.h>

using namespace std;

int t;

int main() {
    scanf("%d", &t);
    while (t--) {
        int n, a, b;
        scanf("%d%d%d", &n, &a, &b);
        int half = n / 2;
        if ((a < half + 1 || (a == half + 1 && b < a)) &&
            (b > half || (b == half && a > b))) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

【竞赛解题(部分)】“码蹄杯” 全国职业院校程序设计大赛（决赛）

“码蹄杯” 全国职业院校程序设计大赛（决赛）

1. 消除小球

题目

解题

方法一：模拟

思路

代码

2. 因数

题目

解题

方法一：暴力枚举

思路

代码

3. 迷宫

4. 砸键盘

题目

解题

方法一：差分 哈希表

思路

代码

5. 魔方

题目

解题

方法一：模拟

思路

代码

6. 吃蛋糕

7. 传送阵

题目

解题

方法一：并查集

思路

代码

8. 剪刀石头布

9. 特殊排列

题目

样例 1

备注

解题

方法一：找规律

思路

代码

10. 蛇形矩阵定位

11. 切蛋糕

12. 时间监控器

评论区

方法一：差分哈希表