武汉工程大学第七届ACM新生赛（同步赛）

Posted on Edited on In Word count in article: 2.2k Reading time ≈ 7 mins.
  • 康复训练，晚上还有线下赛
  • https://ac.nowcoder.com/acm/contest/95118#question

A 对拍

题目描述

对拍是 赛制，以及 等竞赛中常用的用来检测算法正确性的方法，其基本思路就是用暴力写一个一定正确的程序，然后构造大量随机数据去对比暴力程序与测试程序的输出是否一直从而判断测试程序的正确性。

在 上有这样一道算法题，输入描述如下：
第一行输入一个整数 ，表示测试用例的数量
每个测试用例的第一行包含 个整数 ，表示数组大小和数组上界
每个测试用例的第二行包含 个整数

东方无卿与水敛对该题进行对拍，分别写了 个随机数据生成文件，用以模拟输入。但他们两人数据生成的逻辑有所不同： 东方无卿：
先从 中随机取一个数
对于 组测试样例，每一组：
: 从 中随机取两个数 和
: 从 中随机取 个数，并以升序排列作为数组

水敛：
先从 中随机取一个数
对于 组测试样例，每一组：
: 从 中随机取一个数
: 从 中随机取 个数，并以升序排列作为数组 ， 然后在 中随机取一个数
现在你会拿到一份已经生成好的随机数据，而且很幸运的是这份数据满足： ，那么请你判断这份随机数据更有可能出自谁的对拍文件。

输入描述

第一行一个整数 ，表示随机数据中的测试样例数。
对于每一组测试样例：
第一行两个整数 ，表示数组 的长度和上界。
第二行 个整数 ，表示数组 。
(输入数据均由以上两种随机数据生成文件中的一种随机生成)

输出描述

输出一行表示结果。
若更有可能出自东方无卿的对拍文件，则输出“”。
反之，则输出“”。
（输出的字符串不带引号！）

示例

示例 1

输入
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
21
49 36
0 1 1 1 2 3 5 6 7 8 8 8 8 11 11 12 12 12 13 14 15 18 19 22 23 23 24 24 24 24 25 28 28 28 28 29 29 29 32 32 32 33 34 34 34 35 36 36 36
13 28
0 1 1 3 5 6 14 17 17 24 25 26 28
12 35
4 6 6 8 9 16 21 26 29 32 33 35
44 44
1 1 3 4 5 6 6 6 7 7 10 10 10 12 12 14 16 21 21 21 21 22 23 24 26 26 27 27 28 28 28 29 30 33 36 36 37 37 38 38 39 41 42 44
19 33
2 2 3 4 8 13 13 14 16 17 18 18 20 21 22 23 25 29 29
13 11
0 1 2 2 2 6 8 8 8 10 10 10 11
11 27
0 0 2 2 6 8 11 14 17 18 20
25 31
1 3 3 3 4 6 6 8 9 11 12 13 13 15 16 18 18 19 20 21 21 24 25 26 30
17 35
6 8 12 13 14 14 16 17 19 22 25 29 30 30 31 33 34
47 39
1 2 6 6 6 7 7 7 7 9 10 11 13 13 15 15 15 15 15 17 17 18 18 21 21 22 22 22 22 22 25 26 26 26 27 28 30 32 33 33 35 36 36 37 37 38 39
45 32
0 1 2 3 3 3 4 5 6 7 8 8 8 9 9 9 9 10 11 11 12 12 13 16 16 17 20 20 21 23 23 24 24 25 25 26 27 27 27 27 28 30 30 30 31
26 45
3 3 4 5 6 12 17 24 24 25 25 26 29 29 30 32 32 33 35 37 40 41 42 43 44 44
48 41
0 0 0 1 2 4 4 5 5 6 8 9 10 11 11 14 16 16 17 19 20 21 21 24 25 25 26 29 29 29 29 30 30 30 31 32 33 34 34 34 35 36 36 37 38 40 40 41
14 28
5 5 6 9 13 15 16 17 18 19 20 22 22 25
31 24
1 3 3 3 4 4 5 5 5 6 6 7 8 9 10 12 12 13 13 13 14 14 14 16 16 18 19 19 19 21 23
40 14
0 0 1 2 2 2 3 3 3 3 4 4 4 5 5 5 6 6 8 9 9 10 10 10 10 11 11 11 12 12 12 12 12 12 12 12 13 14 14 14
43 26
1 4 5 5 5 5 6 6 7 8 8 9 9 9 10 10 10 10 11 14 15 16 16 16 17 17 18 18 18 20 21 23 23 24 24 24 24 24 24 24 25 26 26
34 10
1 1 1 1 2 2 2 2 2 3 4 4 5 5 5 6 6 6 6 6 7 7 7 8 8 9 9 9 9 10 10 10 10 10
29 13
0 0 0 0 4 4 4 4 4 5 5 5 7 7 7 8 8 8 9 10 11 11 11 11 12 12 13 13 13
44 18
0 0 0 0 1 1 3 3 4 4 4 5 5 6 6 6 6 6 8 8 10 10 10 11 12 13 13 14 14 14 15 15 15 15 15 16 16 17 17 17 17 17 18 18
19 27
0 0 2 2 3 3 4 8 9 10 13 16 17 19 19 21 21 23 25
输出
1
DongfangWuqing

示例 2

输入
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
24
27 50
1 3 4 9 11 12 14 16 25 26 27 27 28 31 32 34 35 35 40 41 43 45 45 46 46 48 49
47 50
0 0 1 1 1 1 2 2 3 6 11 13 13 14 15 18 19 19 20 20 22 23 28 29 29 32 33 36 38 39 39 39 40 40 42 42 43 45 45 47 47 47 47 47 48 50 50
10 50
1 13 13 13 19 20 24 30 47 49
14 44
0 4 6 18 22 26 26 29 33 33 33 37 39 44
47 49
0 0 0 0 1 1 1 3 5 6 7 7 8 8 9 9 10 11 12 13 15 17 18 18 21 21 21 22 26 28 30 31 31 32 34 35 40 41 41 42 42 43 44 47 48 48 49
33 50
0 1 1 4 5 5 5 6 12 12 13 13 13 14 14 17 18 20 21 21 22 26 26 29 29 29 31 36 39 41 41 47 50
34 49
1 1 3 4 5 5 7 9 10 10 13 13 19 21 22 24 25 27 27 29 30 31 33 34 36 37 39 40 41 41 41 45 47 49
20 50
0 3 7 7 10 14 15 16 17 26 29 30 30 34 35 44 44 45 49 50
50 50
0 0 1 1 2 3 5 6 7 7 7 7 7 7 7 9 9 11 11 15 16 17 18 19 20 24 24 26 27 27 28 28 34 35 36 37 37 37 37 39 39 41 43 43 45 46 47 48 48 50
27 50
2 4 6 8 10 12 13 14 18 20 26 27 28 30 31 32 33 33 35 37 37 38 44 44 45 47 49
42 49
0 0 1 3 3 5 5 8 8 10 11 11 13 15 16 17 17 19 20 20 22 22 27 27 29 30 31 32 33 35 36 36 36 37 38 38 38 39 46 46 49 49
49 50
0 0 0 1 2 3 3 3 6 6 7 12 15 17 17 19 19 19 20 20 21 23 23 25 27 27 27 28 28 28 28 29 30 30 30 31 33 34 38 40 42 44 45 45 45 48 49 50 50
14 49
1 2 5 8 8 10 22 27 28 30 34 38 40 49
28 49
0 4 5 5 6 10 11 12 12 16 17 17 19 19 20 20 21 22 27 29 29 30 31 34 41 42 43 45
23 50
0 5 6 11 12 14 16 16 17 21 21 25 26 27 31 31 32 39 42 43 45 45 48
27 50
0 4 5 8 8 12 14 16 18 19 20 22 25 25 26 29 32 33 33 35 36 36 38 39 41 44 47
26 50
1 3 4 5 7 10 11 11 12 12 15 16 18 25 26 28 31 34 36 37 41 42 45 46 47 50
33 50
0 2 3 4 5 5 8 8 9 10 14 15 16 17 17 19 21 24 26 27 31 32 33 33 34 35 39 39 39 42 43 44 47
43 50
0 2 2 3 4 5 9 9 9 12 12 15 15 16 16 17 19 22 25 25 26 28 29 30 30 32 34 36 37 37 38 39 40 41 42 43 44 44 44 47 47 47 48
35 50
0 1 2 6 6 7 7 10 10 10 11 13 15 18 18 19 20 20 21 22 30 30 31 31 33 33 35 36 38 38 40 43 43 48 50
18 49
3 3 8 10 11 12 15 17 19 20 24 26 27 36 38 43 45 49
40 49
3 3 4 4 5 5 14 15 17 19 20 20 22 23 23 24 24 26 27 28 30 31 32 33 33 36 37 37 39 43 43 44 44 44 45 45 46 46 47 48
42 50
0 0 0 0 3 4 5 7 8 11 11 12 13 14 14 15 15 15 15 17 18 22 23 23 24 28 28 31 31 36 36 38 39 42 42 42 43 45 49 49 49 50
22 50
1 3 9 10 11 15 18 22 23 23 24 24 26 28 33 39 39 40 43 47 48 50
输出
1
ShuiLian

Solution

感觉是考虑生成数据的概率问题，我直接判断生成 50 的概率也能过

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
int ct = 0;
void solve() {
  int n, m, x;
  cin >> n >> m;
  if (m == 50) ct++;
  while (n--) {
    cin >> x;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  int c = t;
  while (c--) {
    solve();
  }
  if (ct < (t / 2))
    cout << "DongfangWuqing" << endl;
  else
    cout << "ShuiLian" << endl;
  return 0;
}

E 小白不想当小脑治安官

题目描述

最近网易第五人格新出了一个娱乐模式，名为 “模仿者游戏”，这个一款类似于太空狼人杀的大型真人线上交友游戏，小白在玩了几把此模式后也是成功上瘾。看到很多人每天十四个小时都在玩模仿者，这里真的很想劝大家一句，其实模仿者也就那样，清醒一点吧，别总是沉迷其中，生活还得继续 ，，没其他信息了，过。

在 “模仿者游戏” 中有三个阵营，分别为侦探团（好人）、神秘客（中立）以及模仿者（狼人），在侦探团中有一位重要角色名为 ”治安官“ ，他的技能是只要他还存活就可以一直刀人，如果刀到侦探团阵营的人，那么自己也会一起去世，如果刀到神秘客阵营或者模仿者阵营的话，则只有被刀的那个人会去世，所以说治安官会容易出现 ”小脑“ 的情况，即刀到了侦探团的队友，从而被队友赛后问候。

现在我们将这个游戏的规则简化一下，当且仅当所有神秘客和模仿者阵营的玩家都死亡后，侦探团阵营才能胜利，现在小白进行了一局 "模仿者游戏"，这局游戏侦探团阵营有 个人，神秘客阵营有 个人，模仿者阵营有 个人，并且小白拿到了 ”治安官“ 这个角色，我们假设这局游戏所有的操作只有以下一种：

  • 如果此时小白目前没死，且当前一共有 个人，则小白在除他之外的 个人中等概率的选取一个人出刀，如果出刀后场上只剩下侦探团阵营的角色的话游戏结束，侦探团胜利。如果此时小白死亡，游戏结束，侦探团失败。

如果游戏没有结束，将一直循环这一种操作，直到游戏结束。由于小白不想当小脑治安官，所以他想知道如果游戏这样进行下去，侦探团胜利的概率是多少，你能帮帮他吗？

输入描述

第一行输入一个整数 表示有 组数据。
接下来 行输入三个整数 ，保证小白是侦探团阵营 个人中的一个。

输出描述

输出 行，每行输处这个分数的分子和分母，以空格隔开，要求以最简形式输出。（即如果你算出的答案是 ，应该输出 ）

示例

示例

输入
1
2
3
2
2 1 1
1 1 1
输出
1
2
1 3
1 1

说明：

对于第一个样例，侦探团获胜的概率为 ，当且仅当小白能出两刀，并且这两刀都没有误伤侦探团的队友的时候侦探团才能获得胜利。
对于第二个样例，小白出两刀一定不会误伤队友（因为他根本没有队友），所以侦探团一定会获胜。

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

void solve() {
  int n, m, k, t;
  cin >> n >> m >> k;
  t = m + k;
  int a = 1, b = 1;
  while (t != 0) {
    a *= t;
    b *= (n + t - 1);
    --t;
  }
  int z = gcd(a, b);
  cout << a / z << " " << b / z << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

I 好数组

题目描述

小白认为如果一个数组里面的所有元素都相等，那么这个数组就可以被称之为一个好数组。现在小白获得了一个长度为 的数组 和一个正整数 ，他可以对这个数组执行任意次下面的操作：

  • 选择数组中的任意一个数，使这个数加上

他想知道他能不能通过这种操作将这个数组变成一个好数组，请你帮助他解决一下这个问题。

输入描述

第一行输入两个整数 和
第二行输入 个数

输出描述

如果该数组不能被变成一个好数组，输出 “” ，否则输出 “” 。

示例

示例 1

输入
1
2
4 2
2 4 6 8
输出
1
YES

说明：

对第一个元素使用三次操作，第二个元素使用两次操作，第三个元素使用一次操作即可。

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
using namespace std;
void solve() {
  int n, ai, p;
  cin >> n >> p;
  vector<int> a;
  while (--n) {
    cin >> ai;
    a.pb(ai);
  }
  sort(a.begin(), a.end(), greater<int>());
  for (auto i = a.begin() + 1; i != a.end(); ++i) {
    if ((*i - a[0]) % p != 0) {
      cout << "NO" << endl;
      return;
    }
  }
  cout << "YES" << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}

L 最大与最小

题目描述

梅森数是一类形如 的数字，其中的素数被称为梅森素数。人类目前已经发现了 52 个梅森素数，其中最大的是 2024 年发现的 ，这同时也是已知最大的素数。 最小的素数毫无疑问是 2，现在，给你几个梅森素数，请你输出最小的素数在模这个梅森素数意义下的逆元。当然，由于这个数本身也可能很大，你只需要输出其模 后的值。 （模即取余操作，比如 C++中的%运算符， 模 意义下的逆元指满足 的整数 ，可以记作 ）

输入描述

第一行一个整数 ，表示有 组测试数据。
接下来 行，每行一个整数 ，表示这组测试的数据是 ，保证这是一个素数，。

输出描述

输出 行，每行一个数字，即

示例

示例 1

输入
1
2
3
2
2
3
输出
1
2
2
4

说明：

，而
，而

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
#include <bits/stdc++.h>
#define mod 998244353
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
ll qpow(ll base, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) res = (res * base) % mod;
    base = (base * base) % mod;
    n >>= 1;
  }
  return res;
}
void solve() {
  int x;
  cin >> x;
  cout << qpow(2, x - 1) << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}