Skip to content

第 1 次竞赛

A. 小蓝鲸洗牌

题目背景

大数学家小蓝鲸最近迷上了卡牌游戏。在一次偶然的机会中，小蓝鲸发现了一种特殊的洗牌方式——循环洗牌。小蓝鲸非常兴奋，想要深入研究这个有趣的洗牌技巧。

题目描述

小蓝鲸有一副特殊的卡牌，这些卡牌排成一个循环链表的形式。初始时，循环链表中只有一张编号为 \(1\) 的卡牌，小蓝鲸的指针指向这张卡牌。

小蓝鲸可以进行以下三种操作：

  1. 插入操作 I x：在当前指针位置的后面插入一张编号为 \(x\) 的新卡牌，插入后指针仍指向原来的卡牌。
  2. 移动操作 M k：将指针移动 \(k\) 步。如果 \(k > 0\)，则向前移动；如果 \(k < 0\)，则向后移动；如果 \(k = 0\)，则指针不动。
  3. 输出操作 O m：从当前指针位置开始，向后依次输出接下来的 \(m\) 张卡牌的编号。

请你模拟小蓝鲸的洗牌过程，并按要求输出结果。

输入

第一行包含一个整数 \(n\)，表示操作的总数。

接下来 \(n\) 行，每行包含一个操作：

  • I x：插入编号为 \(x\) 的卡牌
  • M k：移动指针 \(k\) 步
  • O m：输出 \(m\) 张卡牌的编号

输出

对于每个输出操作 O m，输出一行，包含 \(m\) 个整数，表示从当前位置开始顺时针方向的 \(m\) 张卡牌的编号，用空格分隔。

样例输入 #1

1
2
3
4
5
6
7
8
7
I 2
I 3
M 1
I 4
M -1
O 4
M 2

样例输出 #1

1
1 3 4 2
样例解释 #1

初始状态：循环链表为 [1]，指针指向编号为 1 的卡牌。

  1. I 2：在位置 1 后面插入 2，链表变为 [1, 2]，指针仍指向 1。
  2. I 3：在位置 1 后面插入 3，链表变为 [1, 3, 2]，指针仍指向 1。
  3. M 1：指针向前移动 1 步，指向 3。
  4. I 4：在位置 3 后面插入 4，链表变为 [1, 3, 4, 2]，指针仍指向 3。
  5. M -1：指针向后移动 1 步，指向 1。
  6. O 4：从 1 开始输出 4 张卡牌：1, 3, 4, 2。

样例输入 #2

1
2
3
4
5
6
5
I 5
I 10
M 2
O 3
M -3

样例输出 #2

1
5 1 10
样例解释 #2

初始状态：循环链表为 [1]，指针指向编号为 1 的卡牌。

  1. I 5：在位置 1 后面插入 5，链表变为 [1, 5]，指针仍指向 1。
  2. I 10：在位置 1 后面插入 10，链表变为 [1, 10, 5]，指针仍指向 1。
  3. M 2：指针向前移动 2 步，指向 5。
  4. O 3：从 5 开始输出 3 张卡牌：5, 1, 10。

样例输入 #3

1
2
3
4
5
4
M 0
O 1
I 100
O 2

样例输出 #3

1
2
1
1 100
样例解释 #3

初始状态：循环链表为 [1]，指针指向编号为 1 的卡牌。

  1. M 0：指针不移动，仍指向 1。
  2. O 1：输出 1 张卡牌：1。
  3. I 100：在位置 1 后面插入 100，链表变为 [1, 100]，指针仍指向 1。
  4. O 2：从 1 开始输出 2 张卡牌：1, 100。

数据范围

  • 对于前 50% 的数据，\(1 \le n \le 10^3\)，\(1 \le x \le 10^3\)，\(\Sigma|k| \le 10^3\)，\(1 \le \Sigma m \le 10^3\)
  • 对于 100% 的数据，\(1 \le n \le 10^6\)，\(1 \le x \le 10^6\)，\(\Sigma|k| \le 10^3\)，\(1 \le \Sigma m \le 10^3\)

提示

  • 至少有一个输出操作
  • \(m\) 和 \(k\) 可能超过当前循环链表中卡牌的总数
  • 使用 cin >> op 或 scanf(" %c", &op) 读取操作字符（注意 %c 前的空格）
  • 直接使用 scanf("%c", &op) 或 getchar() 可能会读入空白字符（如换行符、空格），导致程序错误

时间限制：1s

空间限制：256MB

Solution

双向循环链表的实现，只需要实现基础构建和插入

Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int value;
    Node *left;
    Node *right;
};

void insertNode(int x, Node *p) {
    Node* node = new Node;
    node->value = x;
    node->left = p;
    node->right = p->right;
    p->right->left = node;
    p->right = node;
}

void solve(){
    int n; cin >> n;

    int len = 1;
    Node* head = new Node{1, nullptr, nullptr};
    head->left = head;
    head->right = head;

    Node* cur = head;
    while (n--){
        char op; cin >> op;
        switch(op){
            case 'I':
                int x; cin >> x;
                insertNode(x, cur);
                len++;
                break;
            case 'M':
                int k; cin >> k;
                if(len == 1) break;
                k %= len;
                if (k > 0){
                    while (k--) cur = cur->right;
                }
                else {
                    k = -k;
                    while (k--) cur = cur->left;
                }
                break;
            case 'O':{
                int m; cin >> m;
                Node* tmp = cur;
                m %= len;
                if(m == 0) m = len;
                for(int i = 0; i < m; i++){
                    cout << tmp->value << " ";
                    tmp = tmp->right;
                } cout << "\n";
                break;
            }
            default:
                break;
        }
    }
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; 
    // cin >> t;            // multi testcases
    t = 1;              // single testcase

    while (t--){
        solve();
    }
    return 0;
}

B. 小蓝鲸比大小

题目描述

小蓝鲸对数组中的数据大小产生了浓厚的兴趣，他希望为数组中的 每一个元素 找出对应的 下一个更大的元素。为了达成这个目标，他将数组的首尾连接，转化为一个循环数组，并规定如果不存在下一个更大的数字，就输出 -1。

现在，请你来帮助小蓝鲸想想如何才能实现这一目标吧！（提示：单调栈）

输入格式

第一行输入一个整数 \(n\)，表示数组的长度。

第二行输入 \(n\) 个整数，分别代表数组每一位的数值。

输出格式

输出一行，分别对应每个元素的下一个更大元素的值。

样例数据

样例1

输入

1
2
3
1 2 1

输出

1
2 -1 2
样例解释 #1

第一个 1 的下一个更大的数是 2；

数字 2 找不到下一个更大的数；

第二个 1 的下一个最大的数经过循环搜索也是 2。

样例2

输入

1
2
5
1 2 3 4 3

输出

1
2 3 4 -1 4

数据规模与约定

$ 1 \leq n \leq 2 \times 10^6 $

$ -10^3 \leq num \leq 10^3 $

时间限制：\(1 \text{s}\)

空间限制：\(64 \text{MB}\)

Solution

单调栈模板再就业

注意数组是循环的，所以一轮遍历下来没退栈的需要再扫一遍

Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;


void solve(){
    int n; cin >> n;
    vi a(n), ans(n, -1);
    for(int &x : a) cin >> x;
    stack<int> st;

    // 第一轮，纯粹的单调栈
    for(int i = 0; i < n; i++){
        while (!st.empty() && a[i] > a[st.top()]) {
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }

    // 第二轮，针对循环数组，进行栈上剩余元素的清理
    for(int i = 0; i < n; i++){
        while (!st.empty() && a[i] > a[st.top()]) {
            ans[st.top()] = a[i];
            st.pop();
        }
        // 和第一轮唯一的区别就是不会再入栈了
    }

    for(int &x : ans) cout << x << " ";

}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t; 
    // cin >> t;            // multi testcases
    t = 1;              // single testcase

    while (t--){
        solve();
    }
    return 0;
}

C. 小蓝鲸还排队

题目背景

这天，小蓝鲸来银行办理业务。他发现银行总共有两类服务窗口，一类是对私窗口，用来处理普通客户的业务；一类是对公或外币窗口（这里统称为特殊窗口），用来处理特殊客户的业务。对私窗口只能办理普通业务，特殊窗口可以办理普通和特殊业务，但正常情况下不会对普通客户开放。

每个客户（包括特殊客户）办理业务时长都为 \(1\) 个周期，客户只会在周期的开始到来。

在某个周期中，银行办理业务的规则如下：

1、根据当前普通用户的总人数确定可办理普通业务的窗口数。记对私窗口数为 \(a\)，特殊窗口数为 \(b\)，银行首先考虑只使用 \(a\) 个对私窗口来办理普通业务，如果此时 \(a\) 个窗口平均排队人数大于 \(7\) 人，则逐步征用特殊窗口来办理普通业务，直到办理普通业务的各窗口平均排队人数（不包含特殊客户）小于等于 \(7\) 人或所有特殊窗口均已被征用。

2、当有特殊客户到来时，特殊窗口要优先服务特殊客户。具体的规则为：若当前有闲置的未被征用的特殊窗口，那么特殊客户优先到该窗口办理业务；若没有，那么特殊客户便“插队”到其中一个被征用的特殊窗口办理业务。特殊客户之间是平级关系，不能互相插队；注意，特殊客户只能在特殊窗口办理业务。

3、银行的服务顺序按照先来先服务原则，普通客户按到来的先后顺序编号并按此顺序依次办理业务。

4、银行只在前 \(n\) 个周期内允许新客户到来，在 \(n\) 个周期后，银行只办理仍在排队的客户的业务，不再接收新客户。

请问，各个普通客户要等待多长时间？（即排队等待的周期数）

输入格式

  • 第一行包含三个整数 \(n,\;a\) 和 \(b\)，分别表示银行接收新客户的周期数、对私窗口数量与特殊窗口的数量。
  • 第二行包含 \(n\) 个整数，由空格隔开，表示每个周期到来的普通客户人数。
  • 第三行包含 \(n\) 个整数，由空格隔开，表示每个周期到来的特殊客户人数。

输出格式

  • \(m\) 个整数，由空格隔开， \(m\) 为普通客户总数量，表示各个普通客户要等待的周期数，按到来的先后顺序排列。

测试样例

样例 1

Input

1
2
3
3 1 1
2 7 3
1 1 0

Output

1
0 1 1 1 2 2 3 4 5 5 6 7
样例解释 #1
  • 在第一周期，特殊客户直接在空闲的特殊窗口办理业务，1号普通客户在对私窗口办理业务，等待周期数为0，2号普通客户开始排队；
  • 在第二周期，由于只有一个对私窗口，此时该窗口排队人数为1+7=8 超过七人，要临时征用特殊窗口，但此时有一位特殊客户优先办理业务，所以仍只有一位普通客户办理了业务——即为第一周期到来的2号普通用户，等待周期数为1；
  • 在第三周期，普通客户人数为7+3=10 超过七人，要临时征用特殊窗口，此时没有特殊客户，第二周期到来的3号和4号普通客户办理了业务，等待周期数均为1；
  • 在第四周期，普通客户人数为8 超过七人，要临时征用特殊窗口，此时没有特殊客户，第二周期到来的5号和6号普通客户办理了业务，等待周期数为2；
  • 在第五周期，普通客户人数为6 小于七人，停止使用临时征用的特殊窗口，只使用一个对私窗口来办理普通业务，第二周期到来的7号普通客户办理了业务，等待周期数为3；
  • 以此类推......

样例 2

Input

1
2
3
4 2 1
2 5 13 6
1 2 2 1

Output

1
0 0 0 0 1 1 2 1 2 2 3 3 4 4 5 5 6 6 7 7 7 7 8 8 9 9

数据范围

\(1 \leq n \leq 10^4\)

\(1 \leq a \leq 20，\quad 1 \leq b \leq 5\)

\(0 \leq N_i \leq 100\), \(N_i\) 为第 \(i\) 周期的开始到来的普通客户人数

\(0 \leq M_i \leq 10\), \(M_i\) 为第 \(i\) 周期的开始到来的特殊客户人数

Solution

根据四个规则直接进行模拟，非常纯粹，读题和写代码都挺难受的

一种比较直观的方案就是准备普通窗口和特殊窗口两个队列进行每个周期的模拟，由于题目不需要维护特殊客户的排队情况，因此特殊窗口的队列可以简化为一个 int 变量储存

Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

// #define int long long

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;

void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    vi normal(n), vip(n);
    for (int &x : normal) cin >> x;
    for (int &x : vip) cin >> x;

    int vipcnt = 0; // 当前的 vip 客户数量（用数替代了队列）
    deque<int> que; // 普通客户队列

    // 模拟每个周期
    for (int round = 0; !(round >= n && que.empty() ); round++)
    {
        // 前 n 个周期会有新的客户，进行更新
        if (round < n){
            // 普通客户插入队列
            for (int j = 0; j < normal[round]; j++)
            {
                que.push_back(round);
            }
            // vip 客户直接累加
            vipcnt += vip[round];
        }

        // 计算本轮实际用于办理普通业务的窗口数，考虑特殊窗口征用
        int real_a = a;
        while ((b - (real_a - a) > vipcnt) && que.size() > 7 * (real_a) )
            real_a++;

        // 所有普通客户都能在本轮办理
        if (que.size() <= real_a)
        {
            int cnt = 0;
            while (!que.empty())                // 只有这里不一样
            {
                cout << round - que.front()  << " ";
                que.pop_front();
                cnt++;
            }
        }
        // 只有一部分普通客户可以在本轮办理
        else
        {
            int cnt = 0;
            for (int p = 0; p < real_a; p++)    // 只有这里不一样
            {
                cout << round - que.front()  << " ";
                que.pop_front();
                cnt++;
            }
        }

        // 减去本轮 vip 客户的完成办理的人数
        vipcnt -= b;
        if (vipcnt < 0) vipcnt = 0;
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    // cin >> t;            // multi testcases
    t = 1; // single testcase

    while (t--)
    {
        solve();
    }
    return 0;
}