中国地质大学（武汉）2024年新生赛（同步赛）

Posted on Edited on In Word count in article: 2.7k Reading time ≈ 9 mins.
  • 神志不清
  • DP 是不会的
  • 数学题也是不会写的

https://ac.nowcoder.com/acm/contest/93515

B 借阅图书

题目描述

图书馆新进了一批特别火的图书，吸引了一大批读者借用。lzt 作为图书管理员，想要维护借书秩序。于是他先把这本书依次标号为，然后找到一个超级大箱子，把这些书按顺序放在箱子里面(序号为的图书在箱子顶部)，之后他打算对这些书进行图书管理，并向读者公布借用规则，规则如下：

  • 开放预约制。若此时读者没有正在借阅的图书，则该读者可以预约天后进行借阅，但图书馆无法保证读者能在天后能借到书。并且，该读者只能等到 d 天之后进行下一次预约。
  • 在每一天的一开始(即在当天进行操作之前)，图书馆会从箱子顶端依次取出图书来试图满足之前预约过当天借阅的读者的需求。越早预约的读者越先被分配到，并且给分配到图书的读者的状态变为"正在借阅"。若在此过程中 lzt 发现箱子里的图书空了，则之后预约在当天的读者将不会分配到图书，这些预约也会作废。
  • 可以随借随取。只要箱子里的图书不空，并且这个读者此时没有预约该天之后的图书，同时也没有正在借阅的图书，则请求立即借阅的读者将立即取得箱子顶部的图书。
  • 读者归还图书后，lzt 会把该图书放到箱子顶端。
  • 每个读者同一时间最多只能借阅一本书。
  • 此外，每个读者都有一个唯一的读者 ID。图书馆需要支持查询特定读者当前借阅的图书编号。
  • 现在，lzt 需要你维护图书馆的借阅过程。

输入描述

第一行包含两个整数，分别表示图书的数量和操作的数量。
接下来 行，每行描述一个操作，操作的类型有四种：

  1. "t RESERVE id d"：表示在第 天读者 预约在当前操作所在的第 天后借书。如果读者 id 已经有未归还的图书，或者之前已经进行过预约，则此次预约无效，忽略该操作。
  2. "t BORROW id"：表示在第 天读者 请求立即借书。
  3. "t RETURN id"：表示在第 天读者 归还所借的图书。如果读者 没有借阅任何图书，则忽略该操作。
  4. "t QUERY id"：表示在第 天查询读者 当前借阅的图书编号。
    注意：
  5. 操作按照时间顺序依次进行。
  6. 多个操作可以发生在同一天。输入中每个操作前会指定其执行的天数。
  7. 天数从开始(但第一天不一定有操作)，且操作按非递减的天数顺序给出。
  8. 每个读者的是一个唯一的正整数。
  9. 是一个整数，表示该操作发生时所在天数。

输出描述

  1. 对于每一个 "RESERVE" 操作，输出一行一个整数。若操作成功，则输出，否则输出 0.
  2. 对于每一个 "BORROW" 操作，输出一行一个整数，表示被借出的图书编号。如果借书请求无效或箱子为空，则输出.
  3. 对于每一个 "RETURN" 操作，输出一行一个整数，表示归还的图书编号。如果归还操作无效（该用户没有正在借阅的书），则> 输出.
  4. 对于每一个 "QUERY" 操作，输出一行一个整数，表示读者当前借阅的图书编号。如果读者未借阅任何图书，则输出.

示例 1

输入

1
2
3
4
5
6
7
8
9
10
11
2 10
1 RESERVE 1 2
2 BORROW 1
2 RESERVE 1 3
2 BORROW 2
2 RESERVE 3 4
4 BORROW 3
5 RETURN 1
5 QUERY 2
6 QUERY 3
6 QUERY 1

输出

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

说明

第 1 天，读者 1 预约第 3 天借书，预约操作有效，输出 1。第 2 天，读者 1 尝试立即借书。由于读者 1 已经预约了第三天的借书操作，所以立即借书的请求无效，输出 0。随后，读者 1 尝试预约借书，但是由于读者 1 此时已经有预约了，因此当前预约无效，输出 0。之后，读者 2 尝试立即借书。此时箱子顶部有书且读者 2 没有预约和正在借阅的书，所以读者 2 成功借走编号为 2 的书，输出 2。第 2 天最后，读者 3 预约第 6 天借书，预约有效。第 3 天一开始，读者 1 拿到了之前所预约的书，编号为 1 。第 4 天，读者 3 尝试立即借书。箱子此时空了。由于没有可供借阅的书，读者 3 的请求无效，输出 0。第 5 天，读者 1 归还了编号为 1 的书，lzt 把这本书放回箱子顶部，输出这本书的编号 1。随后，lzt 查询读者 2 当前借阅的图书编号。读者 2 之前借阅了编号为 2 的书，且尚未归还，输出 2。第 6 天一开始，读者 3 拿到了之前所预约的书，编号为 1。之后，lzt 分别查询读者 3 当前借阅的图书编号，读者 3 输出其书的编号 1.最后查询读者 1 当前借阅的图书编号，由于此时读者 1 没有正在借书，因此输出 0.

Solution

不是哥们这玩意这么简单，百人过？还以为很难没写 qaq

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
#include <bits/stdc++.h>
using namespace std;
struct o {
  int t;
  string op;
  int id;
  int d;
};
struct state {
  int bid = 0;
  bool reserved = false;
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  stack<int> books;
  map<int, queue<int>> reserves;
  map<int, state> readers;
  queue<o> ops;
  int now = 1;
  for (int i = 1; i <= n; ++i) {
    books.push(i);
  }
  while (m--) {
    o tmp;
    cin >> tmp.t >> tmp.op >> tmp.id;
    tmp.d = 0;
    if (tmp.op == "RESERVE") cin >> tmp.d;
    ops.push(tmp);
  }
  while (ops.size()) {
    while (reserves[now].size()) {
      int id = reserves[now].front();
      reserves[now].pop();
      if (books.size()) {
        readers[id].reserved = false;
        readers[id].bid = books.top();
        books.pop();
      } else {
        readers[id].reserved = false;
      }
    }
    while (ops.front().t == now) {
      o op = ops.front();
      ops.pop();
      if (op.op == "RESERVE") {
        if (readers[op.id].bid == 0 && readers[op.id].reserved == false) {
          reserves[op.t + op.d].push(op.id);
          readers[op.id].reserved = true;
          cout << 1 << endl;
        } else {
          cout << 0 << endl;
        }
      } else if (op.op == "BORROW") {
        if (readers[op.id].bid == 0 && readers[op.id].reserved == false) {
          if (books.size()) {
            readers[op.id].bid = books.top();
            books.pop();
            cout << readers[op.id].bid << endl;
          } else {
            cout << 0 << endl;
          }
        } else {
          cout << 0 << endl;
        }
      } else if (op.op == "RETURN") {
        if (readers[op.id].bid != 0) {
          books.push(readers[op.id].bid);
          cout << readers[op.id].bid << endl;
          readers[op.id].bid = 0;
        } else {
          cout << 0 << endl;
        }
      } else if (op.op == "QUERY") {
        cout << readers[op.id].bid << endl;
      }
    }
    ++now;
  }
  return 0;
}

D 低谷(easy)

题目描述

这是本题的简单版本。在这个版本中，的数据范围更小。同时，本题困难版本仅在同步赛中出现，以替代校内赛的交互题
有一个长度为的数组，现在可以对其进行次操作，每次操作过程如下：

  • 对于数组，选定一个下标，令的值减一。
    现定义低谷：
  • 对于数组，若对于下标，使得且，则称为数组> 的一个低谷。
    lzt 想知道次操作后，该数组的低谷最多有多少个。

输入描述

共两行。第一行包含两个整数，分别表示数组长度和操作次数。
第二行包含个整数，表示数组。

输出描述

输出一行一个整数，表示数组的低谷最大个数。

示例 1

输入

1
2
7 3
2 2 3 4 6 2 3

输出

1
3

说明

将数组中第二个数减 1，第四个数减 2，就能得到三个低谷。

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
#include <bits/stdc++.h>
using namespace std;
int a[3005];
int dp[3005][1505];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k, ans = 0;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 1; j <= n / 2; ++j) {
      dp[i][j] = 1e9 + 7;  // 先使i,j的最小操作数为一个很大的值，以便后续处理
    }
  }
  for (int i = 2; i < n; ++i) {  // 从第2个开始，到倒数第二个
    for (int j = 1; j <= i / 2; ++j) {
      // dp[i][j]     到i为止一共j个低谷的最小操作数
      dp[i][j] = min(
          // 如果i不为低谷，那么使到i为止，一共j个低谷的最小操作数为 dp[i-1][j]
          dp[i - 1][j],
          /*
            如果i为低谷，那么使到i为止，一共j个低谷的最小操作数为
              dp[i - 2][j - 1] + max((int)0, a[i] - min(a[i - 1], a[i + 1]) + 1))
                   ^      ^              ^                   ^
          到  上一个低谷 共j-1个低谷     i已经为低谷       变成低谷需要的最小操作数
          */
          dp[i - 2][j - 1] + max(0, a[i] - min(a[i - 1], a[i + 1]) + 1));
    }
  }
  for (int i = 1; i <= n / 2; ++i) {
    if (dp[n - 1][i] <= k) ans = i;
  }
  cout << ans << endl;
  return 0;
}

Reference

  • 熊猫侠 123 提交的代码
  • Bezime 提交的代码

E 伤害最大化

题目描述

现在王者联盟·原神铁道这款游戏出了一个新英雄，有 4 个技能可以释放：

  • 对一名敌人造成点伤害，其中每一个时间刻使用该技能造成的伤害点数都不相同；
  • 积累点怒气值（不造成伤害）；
  • 对一名敌人造成之前积累过的所有怒气值之和的伤害(怒气值不清零)；
  • 接下来一个时间刻所造成的伤害翻倍。即若在第个时间刻释放该技能，第个时间刻释放的技能会对一名敌人造成的伤害翻倍。
    现在有个时间刻，每个时间刻必须需要释放一个技能，并且技能的冷却时间为个时间刻，即：某一个技能若在第个时间刻>释放，则无法在第时间刻释放。在初始时所有技能都未进入冷却状态。lzt 想知道，个时间刻后该英雄能对敌人造成>的最大伤害是多少。

输入描述

  • 第一行输入两个整数，含义同题面所示。
  • 第二行输入个整数，表示若在第个时间刻释放技能对敌人造成的伤害点数。

输出描述

共一行。输出一个整数表示经过个时间刻后该英雄能对敌人造成的最大伤害。

示例 1

输入

1
2
5 9
1 10 7 3 8

输出

1
38

说明

在这 5 个时间刻中，这个英雄分别使用技能 4,技能 1,技能 2,技能 4,技能 3，共造成 38 点伤害。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int d[20];
ll ans;
int n, a;
void dp(int time, ll anger, int pre1, int pre2, ll dr) {
  if (time == n + 1) {
    ans = max(ans, dr);
    return;
  }
  for (int i = 1; i <= 4; ++i) {   // 4个技能
    if (i != pre1 && i != pre2) {  // pre1，pre2是在冷却中的技能
      if (i == 1) {
        if (pre1 == 4)
          dp(time + 1,  // 时间递增
             anger,
             1,                // 1技能冷却
             pre1,             // pre2技能冷却完毕，pre1还差 1-tick
             dr + d[time] * 2  // 双倍伤害
          );
        else
          dp(time + 1, anger, 1, pre1, dr + d[time]);
      } else if (i == 2) {
        dp(time + 1,
           anger + a,  // 怒气值+a
           2,          // 2技能冷却
           pre1, dr);
      } else if (i == 3) {
        if (pre1 == 4)
          dp(time + 1, anger,
             3,              // 3技能冷却
             pre1,           // pre2技能冷却完毕，pre1还差 1-tick
             dr + anger * 2  // 双倍伤害，注意！！这边也要翻倍
          );
        else
          dp(time + 1, anger,
             3,     // 3技能冷却
             pre1,  // pre2技能冷却完毕，pre1还差 1-tick
             dr + anger);

      } else
        dp(time + 1,  // 时间递增
           anger,
           4,     // 4技能冷却
           pre1,  // pre2技能冷却完毕，pre1还差 1-tick
           dr);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> a;
  for (int i = 1; i <= n; i++) cin >> d[i];
  dp(1, 0, 0, 0, 0);
  cout << ans << endl;
  return 0;
}

Reference

  • Bezime 提交的代码

K 冰红茶

题目描述

给定的网格（行列），再给定 k 瓶冰红茶，每瓶冰红茶有它自己的价格，你需要将所有冰红茶放进这的网格中，lzt 会从每一行中都等概率随机拿取一瓶冰红茶（若该行没有冰红茶，则忽略该行），并且支付这瓶冰红茶的钱，cxh 作为老板，想知道应该怎样放置可以使得 lzt 付的钱数期望最大(不要求每一行都必须有冰红茶，同时一个方格最多只能放置一瓶冰红茶)

输入描述

共两行。

  • 第一行输入三个整数，含义如上述题面所示。
  • 第二行输入个整数其中第个整数表示第瓶冰红茶的价格。。

输出描述

输出题意所求行列的网格。
具体地，输出行，其中第 i 行输个整数，每个整数之间用空格隔开。若第行第列不放置冰红茶，则否则，其中表示冰红茶对应的下标，即：第瓶冰红茶放置在第 i$行第j$列的方格中。
若有多种解决方案，输出任意一种即可

示例 1

输入

1
2
2 3 3
1 4 6

输出

1
2
1 2 0
3 0 0

说明

在该样例中，lzt 付的钱期望是 . 可以证明这个期望是所有解决方案中最大的。

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
#include <bits/stdc++.h>
using namespace std;
struct b {
  int idx;
  int p;
};
bool cmp(b& a, b& c) { return a.p < c.p; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m, k, ct;
  int idx;
  cin >> n >> m >> k;
  vector<b> p;
  for (int i = 0; i < k; ++i) {
    b t;
    t.idx = i + 1;
    cin >> t.p;
    p.push_back(t);
  }
  sort(p.begin(), p.end(), cmp);
  idx = 0;
  while (k > n) {  // 剩余冰红茶数量大于行数，当k<=n时，我们可以在余下的每一行都只放一瓶，最大化期望
    ct = min(m, k - (n - 1));
    k -= ct;
    --n;
    for (int j = 0; j < ct; ++j) cout << p[idx++].idx << " ";
    for (int j = 0; j < m - ct; ++j) cout << "0 ";
    cout << endl;
  }
  while (n--) {
    if (k) // 一行放一瓶
      cout << p[idx++].idx << " ", k--;
    else   // 都放完了
      cout << "0 ";
    for (int j = 1; j < m; ++j) cout << "0 ";
    cout << endl;
  }
  return 0;
}

Reference

  • nahida_lalala 提交的代码