2023年儿童节信息学程序设计水平调研
| 题目名称 | build | digits | monisai | oreo | people | wjdwzc |
|---|---|---|---|---|---|---|
| 源代码名称 | build.cpp |
digits.cpp |
monisai.cpp |
oreo.cpp |
people.cpp |
wjdwzc.cpp |
| 输入文件名称 | build.in |
digits.in |
monisai.in |
oreo.in |
people.in |
wjdwzc.in |
| 输出文件名称 | build.out |
digits.out |
monisai.out |
oreo.out |
people.out |
wjdwzc.out |
| 题目类型 | 传统 | 传统 | 传统 | 传统 | 传统 | 传统 |
| 时间限制 | \(2s\) | \(1s\) | \(1s\) | \(1s\) | \(1s\) | \(1s\) |
| 空间限制 | \(128MB\) | \(128MB\) | \(128MB\) | \(128MB\) | \(128MB\) | \(128MB\) |
| 测试点数量 | \(20\) | \(20\) | \(20\) | \(20\) | \(20\) | \(20\) |
| 测试点是否等分 | 是 | 是 | 是 | 是 | 是 | 是 |
注意事项：
- 本次调研统一使用C++语言编写源代码。
- 本次调研时长 \(3\) 时。
- 本次调研源代码编译参数统一使用
-O2 -std=c++14。 - 本次调研题目不分先后。
- 本次调研的时间和空间限制均达到标准源代码实际测试时的两倍。欢迎吊打标准源代码。
- 每道题的样例在每道题对应的子文件夹中。输入文件后缀为
.in，输出文件后缀为.ans。 - 您需要建立您的文件夹。您可以按照文件夹
example中的文件夹来建立您的文件夹。 - 本次调研题目很简单，请AK的大佬不要喧哗。
- 祝本次调研顺利！
build
题目背景
一天，Jabb在做摩天楼数独。
题目描述
Jabb要在一条直线上盖楼。最初，每个位置上的楼会有一定的高度。
他可以进行两个操作：
- 将一个区间内所有的楼增加（或减少）一定高度。
- 询问，如果他站在一栋楼的左边，到右边的一栋楼为止，能看见多少栋楼。
形式化描述见输入格式。
输入格式
你需要维护一个非负整数数列 \(a_{1 \sim n}\)。
第一行两个整数 \(N\) 和 \(Q\)，分别是数列长度和操作个数。
第二行 \(N\) 个整数，表示数列的每个数初始的值。
接下来 \(Q\) 行，每行按照以下格式之一输入：
1 x y z，对于 \([x,y]\) 中的每一个整数 \(i\)，将 \(a_i\) 增加 \(z\)。2 x y，询问，对于 \([x,y]\) 中的每一个整数 \(i\)，\(max_{x,x+1,...,i}\) 共有多少种不同的取值。
输出格式
对于每一个询问，输出一行，表示询问的答案。
数据范围
对于所有数据，保证 \(1 \leqslant N,Q \leqslant 10^5\)，\(x,y,z\)是整数，\(1 \leqslant x \leqslant y \leqslant n\)，\(|z| \leqslant 10^9\)。
保证数列的每一个数在任一时刻都不超过 \(10^9\)。
| 测试点编号 | \(N \leqslant\) | \(Q \leqslant\) | 特殊性质 |
|---|---|---|---|
| \(1\) | \(10^5\) | \(10^5\) | 对于所有 2 操作，\(x = y\) |
| \(2\) | \(1000\) | \(1000\) | 无 |
| \(3\) | \(10^5\) | \(10^5\) | 对于所有 2 操作，\(y - x \leqslant 10\) |
| \(4\) | \(10^5\) | \(10^5\) | 没有 1 操作 |
| \(5\) | \(10^5\) | \(10^5\) | 对于所有 1 操作，\(x = y\) |
| \(6\) | \(10^5\) | \(10^5\) | 对于所有 2 操作，\(x = 1\)，\(y = n\) |
| \(7 \sim 20\) | \(10^5\) | \(10^5\) | 无 |
digits
题目背景
Jabb打音游太菜了，所以退游了，开始研究数的性质。
题目描述
你需要求出不小于 \(10\) 且不超过 \(N\) 的满足以下条件的自然数的个数：
- 存在连续两个非零位，满足最小公倍数不小于 \(P\)；
- 任意连续三位中（如果有），最多有 \(S\) 个质数（包括前导零）。
比如在 \(P = 20\)，\(S = 0\) 时，\(159\)，\(267\) 是符合要求的，而 \(149\)，\(123\) 是不符合要求的。
输入格式
本题有多组测试数据。
第一行一个正整数 \(T\)，表示测试数据组数。
接下来 \(T\) 行，每行三个数，分别表示每个测试数据的 \(N\)，\(P\)，\(S\)。
输出格式
一共 \(T\) 行，每行一个非负整数，代表符合要求的数的个数。
样例1解释
要求相当于：这个数的两位的最小公倍数不小于 \(72\)。
只有 \(89\) 和 \(98\) 满足要求。
数据范围
对于所有的数据：\(1 \leqslant T \leqslant 100\)，\(100 \leqslant N < 10^{15}\)，\(1 \leqslant P \leqslant 72\)，\(0 \leqslant S \leqslant 13\)，\(P\)，\(S\)，\(N\) 均为整数。
| 测试点编号 | \(T \leqslant\) | \(N <\) | \(P \leqslant\) | \(S \leqslant\) | 特殊性质 |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(1000\) | \(72\) | \(1\) | 无 |
| \(2 \sim 3\) | \(100\) | \(10000\) | \(72\) | \(2\) | 无 |
| \(4\) | \(1\) | \(10^9\) | \(1\) | \(7\) | 无 |
| \(5\) | \(1\) | \(10^9\) | \(50\) | \(7\) | \(P = 50\) |
| \(6\) | \(1\) | \(10^9\) | \(10\) | \(7\) | \(N\) 共有 \(S + 2\) 位 |
| \(7 \sim 10\) | \(1\) | \(10^9\) | \(72\) | \(7\) | 无 |
| \(11 \sim 12\) | \(100\) | \(10^{15}\) | \(72\) | \(13\) | \(N = 10^{15}-1\) |
| \(13 \sim 20\) | \(100\) | \(10^{15}\) | \(72\) | \(13\) | 无 |
monisai
题目描述
一场模拟赛一共有 \(N\) 道题。
每道题都必须先让小A造数据，再让小B验题。
小A需要花费 \(A_i\) 分钟给第 \(i\) 题造数据，小B需要花费 \(B_i\) 分钟验第 \(i\) 题。
小A和小B同时只能分别处理一道题，可以调换题目顺序，请问一共最少需要多少时间才能处理完所有题？
输入格式
第一行一个整数 \(N\)。
接下来 \(N\) 行，每行两个整数，表示 \(A_i\) 和 \(B_i\)。
输出格式
只有一行，一个整数，代表处理完所有题最少需要的时间。
数据范围
对于所有数据，\(1 \leqslant N \leqslant 1000\)，\(0 \leqslant A_i , B_i \leqslant 10^5\)。
| 测试点编号 | \(N \leqslant\) | 特殊性质 |
|---|---|---|
| \(1\) | \(1000\) | \(B_i = 0\) |
| \(2\) | \(10\) | 无 |
| \(3 \sim 4\) | \(100\) | 无 |
| \(5\) | \(1000\) | \(A_i \geqslant B_i, A_i \geqslant A_{i+1}\) |
| \(6 \sim 20\) | \(1000\) | 无 |
注：特殊性质中的 \(i\) 均为在有意义的范围内的任意 \(i\)。
花絮
终于，在模拟赛出完之后，出题人Jabb承诺之后再也不出超过一千道题的模拟赛，也不会出需要超过十万分钟才能造完数据验完题的难题了。
oreo
题目背景
众所周知，奥利奥有一个很大的家族。
题目描述
现在，Jabb一边吃奥利奥，一边在想一个问题。
定义合法单奥利奥字符串为所有仅由 a 和 l 构成的满足下列条件的字符串：
- 字符串的首位和末位均为
a； - 不存在两个相邻的字符
a。
定义合法奥利奥字符串如下：
- 任意合法单奥利奥字符串都是合法奥利奥字符串；
- 若
A和B都是合法奥利奥字符串，则AyB是合法奥利奥序列。
现在Jabb想要知道一共有多少个长度为 \(N\) 的合法奥利奥序列。
由于数量可能太多，所以要对 \(P\) 取模。
输入格式
共一行，两个正整数，分别表示 \(N\) 和 \(P\)。
输出格式
只有一行，表示长度为 \(N\) 的合法奥利奥字符串的数量对 \(P\) 取模后的值。
样例1说明
共有 \(5\) 个字符串：alala，allla，ayaya，ayala 和 alaya，而 \(5 \bmod 3 = 2\)，因此输出为 \(2\)。
数据范围
对于所有数据，\(1\) \(\leqslant\) \(N\) \(\leqslant\) \(10^{18}\)，\(2\) \(\leqslant\) \(P\) \(\leqslant\) \(10^{9}\)。
| 测试点编号 | \(N \leqslant\) | \(P \leqslant\) |
|---|---|---|
| \(1\) | \(10\) | \(10^9\) |
| \(2 \sim 3\) | \(1000\) | \(10^9\) |
| \(4 \sim 5\) | \(10^6\) | \(10^9\) |
| \(6\) | \(10^{18}\) | \(2\) |
| \(7 \sim 20\) | \(10^{18}\) | \(10^9\) |
people
题目描述
J国实行人民代表大会制度。
J国一共有 \(N\) 个政党，每个政党中有 \(2\) 个代表参与人民代表大会选举。
然而，这些代表里面也存在 \(M\) 对敌人。
人民代表大会组成的要求如下：
-
每个政党在人民代表大会中恰有 \(1\) 个代表；
-
其中不能有一对代表是敌人。
规定第 \(i\) 个政党的两位代表的编号分别为 \(2i-1\) 和 \(2i\)。
请问人民代表大会是否能够成功组成？
输入格式
为了避免“不可以，总司令”或“可以，总司令”获得满分，本题有多组测试数据。
第一行一个整数 \(T\)，表示测试数据组数。
对于每组测试数据，输入格式如下：
第一行两个整数，分别表示 \(N\) 和 \(M\)。
之后 \(N\) 行，每行两个数 \(X\) 和 \(Y\)，表示一对敌人的编号。
输出格式
对于每组测试数据，输出一行。如果人民代表大会可以成功组成，输出 YE5；如果不可以成功组成，输出 N0。
样例1解释
人民代表大会可以由1号、4号和5号代表组成。
数据范围
对于所有测试点，\(1 \leqslant T \leqslant 10\)，\(1 \leqslant N \leqslant 8*10^3\)，\(1 \leqslant M \leqslant 2*10^4\)，\(1 \leqslant X < Y < 2N\)。
| 测试点编号 | \(N \leqslant\) | \(M \leqslant\) |
|---|---|---|
| \(1\) | \(10\) | \(30\) |
| \(2 \sim 5\) | \(100\) | \(1000\) |
| \(6 \sim 20\) | \(8*10^3\) | \(2*10^4\) |
wjdwzc
题目描述
wjd在和wzc玩一个游戏。
给定 \(N\) 堆果子，每堆果子各有一个。wjd和wzc每一次操作可以把两堆果子合并，新堆的果子数量为两个堆的果子之和。
然而，出于某些原因，规定每一个堆的果子数量都不能超过 \(M\)。
众所周知，wjd和wzc都聪明绝顶。
wjd先手，请问谁能赢得游戏？
输入格式
为了避免个人情感的影响，本题多组数据。
第一行为一个整数 \(T\)，表示数据组数。
之后 \(T\) 行，每行两个整数，代表 \(N\) 和 \(M\)。
输出格式
一共 \(T\) 行，每行为 wjd 或 wzc，表示谁能获胜。
数据范围
对于所有数据，\(1 \leqslant T \leqslant 10^5\)，\(1 \leqslant M , N \leqslant 10^9\)。
| 测试点编号 | \(T \leqslant\) | \(N \leqslant\) | \(M \leqslant\) | 特殊性质 |
|---|---|---|---|---|
| \(1\) | \(10^5\) | \(10^9\) | \(10^9\) | \(N \leqslant M\) |
| \(2\) | \(10^5\) | \(10^9\) | \(2\) | 无 |
| \(3\) | \(10\) | \(10\) | \(10\) | 无 |
| \(4\) | \(100\) | \(100\) | \(100\) | 无 |
| \(5\) | \(10^5\) | \(100\) | \(100\) | 无 |
| \(6\) | \(10\) | \(1000\) | \(1000\) | 无 |
| \(7 \sim 20\) | \(10^5\) | \(10^9\) | \(10^9\) | 无 |