Summary for 2024-10-08

Special - 2024国庆思维训练特别赛

浪费了国庆几天时间，不会做的还是不会做，不得不说 $\mathbf{PUAA}$ 的出题有水平，新人中也不缺乏高手。

22 for 7 days

本文如果侵害了你的版权，请及时联系删除，谢谢。

A 石头 剪刀 布

题目描述

有三个玩家 A、B、C 玩剪刀石头布游戏。游戏规则如下：

• 每位玩家出拳只能是“剪刀”、“石头”或“布”中的一个。
• 如果三位玩家出拳都不相同或都相同，则没有玩家获胜。
• 如果场上只出了 “剪刀” 和 “石头” ，则出“石头”的玩家获胜。
• 如果场上只出了 “剪刀” 和 “布” ，则出“剪刀”的玩家获胜。
• 如果场上只出了 “布” 和 “石头” ，则出“布”的玩家获胜。
• 每局的获胜玩家均获得 1 分

你作为游戏裁判，需要编写一个程序来确定每位玩家 m 轮游戏后的得分情况。

输入

共 m+1 行。

第一行，一个正整数 m，表示 m 轮游戏。保证 $1≤m≤100$

接下来 m 行，每行三个空格隔开的整数 a 、b 、c ，分别表示玩家 A、B、C 的出拳。保证 $a,b,c∈0,1,2$ 分别表示剪刀、石头、布。

输出

共 1 行，共三个非负整数，分别表示玩家 A、B、C 的得分。

输入样例

2
0 0 0
1 0 0

输出样例

1 0 0

THINK

模拟即可

B 验证身份证号

时间限制：1000ms 内存限制：65536kb

通过率：1072/1217 (88.09%) 正确率：1072/3600 (29.78%)

题目介绍

中华人民共和国公民的身份证号码由 18 位数字或 X 组成，其中最后一位可能是 X。

身份证号码的前 66 位表示行政区划代码，第 7 位到第 14 位表示出生日期，第 15 位到第 17 位表示顺序码，第 18 位表示校验码。

现给定若干个身份证号，请检验身份证号是否合法。如果合法，输出 YES，否则输出 NO。

保证前 17 位数字合法，因此你只需要检验第 18 位校验码是否合法即可。

校验码的计算方法如下：

• 将前面的身份证号码 17 位数分别乘以不同的系数。从第 1 位到第 17 位的系数分别为$7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2$。
• 将这 17 位数字和系数相乘的结果相加。
• 用加出来的和除以 11，看余数是多少。
• 余数只可能有 $0,1,2,3,4,5,6,7,8,9,10$ 这 11 个数字。其分别对应的最后一位身份证的号码为 $1,0,X,9,8,7,6,5,4,3,2$ 。(即余数 0 对应 1 ，余数 1 对应 0 ，余数 2 对应 $X$ …)

输入格式

共 n+1 行。

第一行一个正整数 n ，保证 $1≤n≤50$ 。

接下来 n 行，每一行为一个身份证号。（若最后一位为 $X$，则为大写字母 X）

输出格式

输出 n 行。

每行表示身份证号码是否合法。如果合法，输出 YES，否则输出 NO。

输入样例

2
371311200312247819
130631197601191234

输出样例

YES
NO

Hint

在计算系数相乘结果之和时，除了直接写出表达式以外，我们也可以采用 “数组+循环” 的方式。

假设需要计算 $3×5+9×7+4×93×5+9×7+4×9$

我们可以直接写 sum = 3*5+9*7+4*9;

同时，我们也可以写成

int a[3] = {3,9,4};
int b[3] = {5,7,9};
int sum = 0;
for (int i = 0; i < 3; ++i) 
{
   sum += (a[i] * b[i]);
}

看似代码量变大了，但如果需要计算 17 个系数相乘结果之和时，“数组+循环”的方法或许会更便捷且不易出错。

C nbnhhsh？

时间限制：1000ms 内存限制：65536kb

通过率：876/973 (90.03%) 正确率：876/2450 (35.76%)

题目描述

qjsywcyycxsjzj。

看得懂吗？看不懂就对了。上面这句话的意思是，“奇迹是一位C语言程序设计助教”。

由于语言能力本当苦手，奇迹对汉语拼音首字母缩写理解不能。为了训练，他想通过英文句子缩写入手，你能帮他编写一个程序，自动生成缩写吗？

输入

一行一个字符串$s$，由若干英文单词、空格、标点符号组成。

输出

对于每组数据，输出一行，缩写后的句子。若单词中出现了单引号，认为是一个单词。

缩写规则：连续的英文字母或单引号认为是一个单词，输出该单词的第一个字母，区分大小写（特别地，数据保证一个单词不会以单引号开头）；其他标点符号原样输出；空格省去。

输入样例1

Man, What can I say? Mamba out!

输出样例1

M,WcIs?Mo!

输入样例2

BanG Dream! It's MyGO!!!

输出样例2

BD!IM!!!

Not hint

本题的题目全拼为“能不能好好说话”

THINK

空格分词，处理首尾字符

D tux 的飞行编队安排 (Hard Version)

时间限制：1000ms 内存限制：65536kb

通过率：739/797 (92.72%) 正确率：739/1247 (59.26%)

题目描述

今年是国庆 75 周年，tux 想安排一场飞行表演来庆祝国庆。为了让表演更加壮观，参与表演的飞机数量要尽可能多，但是 tux 最多只能使用 $n$ 架飞机（可以使用小于等于 $n$ 架）。编队必须严格排列成如下格式的 “75” 形状（星号代表飞机）：

****    ****
   *    *
   *    *
  *     ****
  *        *
 *         *
 *      ****

图形解释：设图形中 “7” 和 “5” 的横向宽度为 $k$（$k≥3$，图中为 4），则 “7” 的纵向高度为 $2k−1$，“7” 的竖线略有倾斜，斜率为 2 。“5” 共有三条横线，相邻的横线之间有 $k−2$ 行。“7” 和 “5” 之间用 $k$ 个空格隔开，“7” 左侧没有空格，上方没有空行。

输入

一个数，表示 tux 最多能使用 $n$ 架飞机，$18≤n≤4000$.

输出

若干行字符，表示在使用不超过 $n$ 架飞机的条件下可以形成的最大编队安排。飞机用星号*表示。

输入样例1

42

输出样例1

******      ******
     *      *
     *      *
    *       *
    *       *
   *        ******
   *             *
  *              *
  *              *
 *               *
 *          ******

样例解释1

$k=6$，全部 $42$ 架飞机均参与表演。

输入样例2

25

输出样例2

***   ***
  *   *
  *   ***
 *      *
 *    ***

样例解释2

排成 $k=3$ 的编队至少需要 $18$ 架飞机，排成 $k=4$ 的编队至少需要 $26$ 架飞机。现有 $25$ 架飞机，最多只够满足 $k=3$ 的编队。

Hint

试着用 $k$ 表示编队飞机的数目，寻找 $n$ 和 $k$ 的关系。

THINK

诚如Hint，用k表示编队飞机的数目，寻找n和k的关系。多用几个if就行了。

E 拾贝

时间限制：1000ms 内存限制：65536kb

通过率：803/916 (87.66%) 正确率：803/2797 (28.71%)

题目描述

ZetaZeta 突然穿越到了原始社会！他发现，那里的人们以收集贝壳为荣，收集贝壳数量多的人可以称王。他们当中有 $n$ 个人收集的贝壳较多，但不尽相同，于是他们决定，这 $n$ 个人首先排好出场顺序，第一天让第一个出场的人称王，之后的 $n−1$ 天，按顺序出一个人与前一天的王比较贝壳的数量，如果那个人贝壳的数量大于前一天的王的贝壳数量，则取而代之。ZetaZeta 想知道，第 $k$ 天谁在称王。

输入

第一行 22 个整数$n,t$ ，表示总人数和询问次数。$(1≤n≤2×105，1≤t≤2×105)$

第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个出场的人收集到的贝壳的数量 $a_i$ 。$(1≤i≤n,1≤a_i≤109)$

接下来 $t$ 行，每行 1 个整数 $k$ ，询问：在第 $k$ 天是第几个出场的人在称王。$(1≤k≤n)$

输出

输出 $t$ 行，每行 $1$ 个整数，表示第几个出场的人在称王。

输入样例

10 9
11 12 12 12 7 6 23 128 1 7
1
2
3
4
5
6
7
8
9

输出样例

1
2
2
2
2
2
7
8
8

Hint

仔细观察给的样例，有没有想到什么呢~

THINK

前 $k$ 天最大值

F 生日悖论

时间限制：1000ms 内存限制：65536kb

通过率：949/986 (96.25%) 正确率：949/1738 (54.60%)

题目描述

一个班级有 $n$ 人。请问，班级所有人的生日都互不相同的概率为多少？

一年有 $365$ 天（不考虑闰年），假设每个人的生日互相独立且在这 $365$ 天里等概率分布的。

输入

第一行一个正整数 $t$ 代表数据组数，$1≤t≤365$

接下来 $t$ 行，每行一个正整数 $n$，$1≤n≤365$

输出

对于每组数据，输出一行一个浮点数，代表班级所有人的生日都互不相同的概率，保留 $6$ 位小数输出。

输入样例

5
10
30
90
1
365

输出样例

0.883052
0.293684
0.000006
1.000000
0.000000

G 奇迹！下雪啦！

时间限制：1000ms 内存限制：65536kb

通过率：337/381 (88.45%) 正确率：337/637 (52.90%)

题目描述

奇迹出生在遥远的南方！在来北方上学之前，奇迹从来没见过雪，第一次看到下雪的时候，他想体验一下滚雪球。首先在手上捏一个小小的核心，然后在地上越滚越大。每秒钟雪球都会向前（顺时针）滚 $1/4$ 圈，奇迹想知道第 $x$ 秒钟雪球有多大？

输入

1行1个正整数 $x$，保证 $x≤100$.

输出

一个 $⌊1+x2⌋×⌊1+x−12⌋$ 阶的矩阵，代表第 $x$ 秒钟雪球的样子。

输入样例

5

输出样例

4 3 3
4 1 2
5 5 5

样例解释

在第一秒钟，雪球的样子是
1
第2至5秒，雪球的样子分别是
1
2

2 1
3 3

3 2
3 1
4 4

4 3 3
4 1 2
5 5 5

THINK

不知道是否能降低时间复杂度。这里提供的思路是先构造一个二维数组，然后模拟逆向过程，一圈一圈往回打表，逐渐收缩到核心。最后输出。时间复杂度为 $O(n^2)$.空间复杂度 $O(n^2)$
模拟过程让我想到了矢量绘图