侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-11-01 / 0 评论 / 0 点赞 / 17 阅读 / 4,268 字 / 正在检测是否收录...

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

1. 消除小球

题目

码题集OJ-消除小球


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

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

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

格式

输入格式:

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

输出格式:

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

样例 1

输入:

5 2
abbab

输出:

b

样例 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-因数


给定一个整数 nn,定义 nn 的一个因子 yykk 次因子,当且仅当存在因子 xx,满足 xk=yx^k = y。注意,这里的 x,yx,y 可以相等。

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

格式

输入格式:

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

输出格式:

在一行中从小到大输出 nn 的所有 kk 次因子。如果只有因子 11 满足要求,则输出 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=xky=x^k,如果存在就把 xkx^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(1m105)m(1 \leq m \leq 10^5),表示小码哥砸了 mm 次键盘。
接着输入 mm 行,每行输入两个整数 l,r(1lr26)l, r(1 \leq l \leq r \leq 26),表示某一次小码哥砸中了键盘区间 [l,r][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-魔方


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

img

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

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

img

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

img

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

格式

输入格式:

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

输出格式:

输出 33 行,每行 33 个字母,表示 nn 次操作后魔方的状态。字母只包含 rgb三种,分别表示红色、绿色和蓝色。

样例 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-传送阵


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

我们用一个长度为 nn 的数组 aa 来表示每个传送门的传送距离。进入第 ii 个传送门时,传送者会被传送到第 i+aii+a_i 个传送门。具体来讲,当 ai<0a_i < 0 时,这个传送门会向前传送 aia_i个单位;当 ai>0a_i > 0 时,这个传送门会向后传送 aia_i 个单位;当 ai=0a_i = 0 时,这个传送门被视为失效传送门(因为你只能待在原地)。

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

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

格式

输入格式:

第一行输入一个整数 n(1n2×105)n (1 \leq n \leq 2 \times 10^5),表示传送门个数。
第二行输入 nn 个整数 a1,a2,,an(ai<n)a_1, a_2, \cdots, a_n (|a_i| < n)aia_i 表示第 ii 个传送门的传送距离。保证给出的传送距离不会传送到 [1,n][1,n] 范围之外。

输出格式:

输出一个仅包含 YN 的长度为 nn 的字符串。第 ii 个字符为 Y 表示第 ii 个传送门为循环传送门,N 表示不是循环传送门。

样例 1

输入:

6
1 -1 1 -1 1 0

输出:

YYYYNN

样例 2

输入:

6
1 -1 -1 1 0 -1

输出:

YYYNNN

解题

方法一:并查集

思路

规定 0 为失效传送门,从 1 开始读入所有传送门,然后使用并查集把相连的传送门合并,合并完后查 1n1\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-特殊排列


一个排列是指一个长度为 nn 的数组 p=[p1,p2,,pn]p = [p_1,p_2,\dots,p_n],其包含 11nn 的整数恰好一次。如 p=[1,5,4,2,3]p = [1,5,4,2,3] 是一个长度为 55 的排列。

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

格式

输入格式:

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

输出格式:

对于每组数组,输出一行 YESNO,表示是否存在这样的排列。

样例 1

输入:

3
6 1 5
8 5 4
6 5 4

复制

输出:

YES
YES
NO

复制

备注

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

解题

方法一:找规律

思路

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

前半段最小值为 aa,后半段最大值为 bb

  1. aa 不能大于 55,如果大于 55 就没有足够的元素给其组成前半段了,所以 a <= n / 2 + 1
  2. aa 等于 55 时,bb 必须小于 aa,如果 b>ab > a 的话也没有足够的元素组成前半段,所以 a == n / 2 + 1 && b < a
  3. bb 不能大于 44,如果大于 44 就没有足够的元素给其组成后半段了,所以 b >= n / 2
  4. bb 等于 44 时,aa 必须大于 bb,如果 a<ba < 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;
}

10. 蛇形矩阵定位

11. 切蛋糕

12. 时间监控器

0

评论区