第十三届蓝桥杯大赛软件赛省赛(C/C++ 大学C组)

省流,十道签到题。 本题总分: 5 5 5 分 【问题描述】 小蓝要把一个字符串中…

省流,十道签到题。

本题总分: 5 5 5

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如, L A N Q I A O \mathrm{LANQIAO} LANQIAO 排列后为 A A I L N O Q \mathrm{AAILNOQ} AAILNOQ

又如, G O O D G O O D S T U D Y D A Y D A Y U P \mathrm{GOODGOODSTUDYDAYDAYUP} GOODGOODSTUDYDAYDAYUP 排列后为 A A D D D D D G G O O O O P S T U U Y Y Y \mathrm{AADDDDDGGOOOOPSTUUYYY} AADDDDDGGOOOOPSTUUYYY

请问对于以下字符串,排列之后字符串是什么?

W H E R E T H E R E I S A W I L L T H E R E I S A W A Y \mathrm{WHERETHEREISAWILLTHEREISAWAY} WHERETHEREISAWILLTHEREISAWAY

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串,在提交答案时只填写这个字符串,填写多余的内容将无法得分。

AAAEEEEEEHHHIIILLRRRSSTTWWWY

指针乱飞就完事了。

本题总分: 5 5 5

【问题描述】

2022 2022 2022 2 2 2 22 22 22 22 22 22: 20 20 20 是一个很有意义的时间,年份为 2022 2022 2022,由 3 3 3 2 2 2 1 1 1 0 0 0 组成,如果将月和日写成 4 4 4 位,为 0222 0222 0222,也是由 3 3 3 2 2 2 1 1 1 0 0 0 组成,如果将时间中的时和分写成 4 4 4 位,还是由 3 3 3 2 2 2 1 1 1 0 0 0 组成。

小蓝对这样的时间很感兴趣,他还找到了其它类似的例子,比如 111 111 111 10 10 10 11 11 11 01 01 01: 11 11 11 2202 2202 2202 2 2 2 22 22 22 22 22 22: 02 02 02 等等。

请问,总共有多少个时间是这种年份写成 4 4 4 位、月日写成 4 4 4 位、时间写成 4 4 4 位后由 3 3 3 个一种数字和 1 1 1 个另一种数字组成。注意 1111 1111 1111 11 11 11 11 11 11 11 11 11: 11 11 11 不算,因为它里面没有两种数字。

【答案提交】

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

212

3 3 3 个相同的个位数中插入 1 1 1 个个位数,显然可以组成 4 4 4 个不同的数字(不一定是 4 4 4 位数),于是我们可以另一个合法的 月日时分 与 4 4 4 个不同的年份组成映射关系,只要统计出合法的 日月时分 个数,将其乘上一个 4 4 4,答案就被计算出来了。

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 10 10 10

【问题描述】

I S O \mathrm{ISO} ISO 国际标准中定义了 A 0 \mathrm A0 A0 纸张的大小为 1189 m m × 841 m m 1189\mathrm{mm} × 841\mathrm{mm} 1189mm×841mm,将 A 0 \mathrm A0 A0 纸沿长边对折后为 A 1 \mathrm A1 A1 纸,大小为 841 m m × 594 m m 841\mathrm{mm} × 594\mathrm{mm} 841mm×594mm,在对折的过程中长度直接取下整(实际裁剪时可能有损耗)。将 A 1 \mathrm A1 A1 纸沿长边对折后为 A 2 \mathrm A2 A2 纸,依此类推。

输入纸张的名称,请输出纸张的大小。

【输入格式】

输入一行包含一个字符串表示纸张的名称,该名称一定是 A 0 \mathrm A0 A0 A 1 \mathrm A1 A1 A 2 \mathrm A2 A2 A 3 \mathrm A3 A3 A 4 \mathrm A4 A4 A 5 \mathrm A5 A5 A 6 \mathrm A6 A6 A 7 \mathrm A7 A7 A 8 \mathrm A8 A8 A 9 \mathrm A9 A9 之一。

【输出格式】

输出两行,每行包含一个整数,依次表示长边和短边的长度。

【样例输入 1】

【样例输出 1】

【样例输入 2】

【样例输出 2】

签到,

格式化输入,行!

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 10 10 10

【问题描述】

给定 n n n 个整数 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots , a_n a1,a2,,an,求它们两两相乘再相加的和,即 S = a 1 ⋅ a 2 + a 1 ⋅ a 3 + ⋯ + a 1 ⋅ a n + a 2 ⋅ a 3 + ⋯ + a n − 2 ⋅ a n − 1 + a n − 2 ⋅ a n + a n − 1 ⋅ a n 。 S = a_1\cdot a_2 + a_1\cdot a_3 + \cdots + a_1\cdot a_n + a_2\cdot a_3 +\cdots + a_{n−2}\cdot a_{n−1} + a_{n−2}\cdot a_n + a_{n−1}\cdot a_n。 S=a1a2+a1a3++a1an+a2a3++an2an1+an2an+an1an

【输入格式】

输入的第一行包含一个整数 n n n

第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_1, a_2,\cdots,a_n a1,a2,,an

【输出格式】

输出一个整数 S S S,表示所求的和。请使用合适的数据类型进行运算。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 1000 , 1 ≤ a i ≤ 100 1 ≤ n ≤ 1000,1 ≤ a_i ≤ 100 1n10001ai100
对于所有评测用例, 1 ≤ n ≤ 200000 , 1 ≤ a i ≤ 1000 1 ≤ n ≤ 200000,1 ≤ a_i ≤ 1000 1n2000001ai1000

公式递推

S S S 中包含 a 1 a_1 a1 的项整理出来,有:

S = a 1 ⋅ ( a 2 + a 3 + ⋯ + a n ) + a 2 ⋅ a 3 + ⋯ + a n − 2 ⋅ a n − 1 + a n − 2 ⋅ a n + a n − 1 ⋅ a n S=a_1\cdot(a_2+a_3+\cdots+a_n)+ a_2\cdot a_3 +\cdots + a_{n−2}\cdot a_{n−1} + a_{n−2}\cdot a_n + a_{n−1}\cdot a_n S=a1(a2+a3++an)+a2a3++an2an1+an2an+an1an

同样的将余项中包含 a 2 a_2 a2 a 3 a_3 a3 ⋯ \cdots a n a_n an 的项整理出来:

S = a 1 ⋅ ( a 2 + a 3 + ⋯ + a n ) + a 2 ⋅ ( a 3 + a 4 + ⋯ + a n ) + ⋯ + a n − 1 ⋅ a n = a 1 ⋅ ∑ i = 2 n a i + a 2 ⋅ ∑ i = 3 n a i + ⋯ + a n − 1 ⋅ ∑ i = n n a i \begin{aligned}S&=a_1\cdot(a_2+a_3+\cdots+a_n)+ a_2\cdot(a_3+a_4+\cdots+a_n)+\cdots+a_{n-1}\cdot a_n\\&=a_1\cdot\sum_{i=2}^na_i+a_2\cdot \sum_{i=3}^na_i+\cdots+a_{n-1}\cdot\sum_{i=n}^{n}a_i\end{aligned} S=a1(a2+a3++an)+a2(a3+a4++an)++an1an=a1i=2nai+a2i=3nai++an1i=nnai

也就 S S S 等于每个元素乘以右边所有元素的和的和,考虑到实现计算的代码量,我们将 S S S 的项重排,重新整理出:

S = a 1 ⋅ ∑ i = 1 0 a i + a 2 ⋅ ∑ i = 1 1 a i + ⋯ + a n ⋅ ∑ i = 1 n − 1 a i S=a_1\cdot\displaystyle\sum_{i=1}^{0}a_i+a_2\cdot \sum_{i=1}^{1}a_i+\cdots+a_{n}\cdot\sum_{i=1}^{n-1}a_i S=a1i=10ai+a2i=11ai++ani=1n1ai

签到 × 2 ×\ 2 × 2

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 15 15 15

【问题描述】

小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。

例如, 2022 2022 2022 排在 409 409 409 前面,因为 2022 2022 2022 的数位之和是 6 6 6,小于 409 409 409 的数位之和 13 13 13

又如, 6 6 6 排在 2022 2022 2022 前面,因为它们的数位之和相同,而 6 6 6 小于 2022 2022 2022

给定正整数 n , m n,m nm,请问对 1 1 1 n n n 采用这种方法排序时,排在第 m m m 个的元素是多少?

【输入格式】

输入第一行包含一个正整数 n n n

第二行包含一个正整数 m m m

【输出格式】

输出一行包含一个整数,表示答案。

【样例输入】

【样例输出】

【样例说明】
1 1 1 13 13 13 的排序为 : 1 , 10 , 2 , 11 , 3 , 12 , 4 , 13 , 5 , 6 , 7 , 8 , 9 :1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9 1,10,2,11,3,12,4,13,5,6,7,8,9。第 5 5 5 个数为 3 3 3

【评测用例规模与约定】

对于 30 % 30\% 30% 的评测用例, 1 ≤ m ≤ n ≤ 300 1 ≤ m ≤ n ≤ 300 1mn300
对于 50 % 50\% 50% 的评测用例, 1 ≤ m ≤ n ≤ 1000 1 ≤ m ≤ n ≤ 1000 1mn1000
对于所有评测用例, 1 ≤ m ≤ n ≤ 1 0 6 1 ≤ m ≤ n ≤ 10^6 1mn106

签到 × 3 ×\ 3 × 3

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 15 15 15

【问题描述】

给定一个长度为 n n n 的数列 A 1 , A 2 , ⋯ , A n A_1, A_2, \cdots , A_n A1,A2,,An 和一个非负整数 x x x,给定 m m m 次查询, 每次询问能否从某个区间 [ l , r ] [l,r] [l,r] 中选择两个数使得他们的异或等于 x x x

【输入格式】

输入的第一行包含三个整数 n , m , x n, m, x n,m,x

第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_1, A_2,\cdots, A_n A1,A2,,An

接下来 m m m 行,每行包含两个整数 l i , r i l_i,r_i li,ri 表示询问区间 [ l i , r i ] [l_i,r_i] [li,ri]

【输出格式】

对于每个询问, 如果该区间内存在两个数的异或为 x x x 则输出 y e s \mathrm{yes} yes, 否则输出 n o \mathrm{no} no

【样例输入】

【样例输出】

【样例说明】
显然整个数列中只有 2 , 3 2, 3 2,3 的异或为 1 1 1

【评测用例规模与约定】

对于 20 % 20\% 20% 的评测用例, 1 ≤ n , m ≤ 100 1 ≤ n, m ≤ 100 1n,m100
对于 40 % 40\% 40% 的评测用例, 1 ≤ n , m ≤ 1000 1 ≤ n, m ≤ 1000 1n,m1000
对于所有评测用例, 1 ≤ n , m ≤ 100000 , 0 ≤ x < 2 20 , 1 ≤ l i ≤ r i ≤ n , 0 ≤ A i < 2 20 1 ≤ n, m ≤ 100000 ,0 ≤ x < 2^{20} ,1 ≤ l_i ≤ r_i ≤ n ,0 ≤ A_i < 2^{20} 1n,m1000000x<2201lirin0Ai<220

动态规划

处理出 f r f_r fr,其意义为 [ f r , r ] [f_r,r] [fr,r] 中存在一对 k k k g g g f r ≤ k ≤ g ≤ r f_r \leq k \leq g \leq r frkgr 使得 A k ⊕ A g = x A_k \oplus A_g =x AkAg=x f r f_r fr 最大,若不存在则令 f r = 0 f_r = 0 fr=0

对于每一次询问 [ l i , r i ] [l_i,r_i] [li,ri],我们只需判断 l i li li f r i f_{r_i} fri 的大小关系就能确定 [ l i , r i ] [l_i,r_i] [li,ri] 之间是否存在两个数,它们的异或等于 x x x

现在考虑转移,对于每一个 r r r,我们判断下标大于 r r r 的元素中是否存在 A r ⊕ x A_r \oplus x Arx,其中最靠 r r r 的是 f r f_r fr 的一个候选值,同时我们还要考虑 [ f r − 1 , r − 1 ] [f_{r-1},r-1] [fr1,r1] 中是否有更优的方案,最终有状态转移方程: f r = max ⁡ { f r − 1 , max ⁡ { i ∣ A i = A r ⊕ x } } f_r=\max\{f_{r-1},\max\{i|A_i=A_r\oplus x\}\} fr=max{fr1,max{iAi=Arx}}

不太对,感觉我在乱压行。

签到 × 4 ×\ 4 × 4

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 20 20 20

【问题描述】

在一个字符串 S S S 中,如果 S i = S i − 1 S_i = S_{i−1} Si=Si1 S i ≠ S i + 1 S_i\neq S_{i+1} Si=Si+1,则称 S i S_i Si S i + 1 S_{i+1} Si+1 为边缘字符。如果 S i ≠ S i − 1 S_i\neq S_{i−1} Si=Si1 S i = S i + 1 S_i = S_{i+1} Si=Si+1,则 S i − 1 S_{i−1} Si1 S i S_i Si 也称为边缘字符。其它的字符都不是边缘字符。

对于一个给定的串 S S S,一次操作可以一次性删除该串中的所有边缘字符 ( ( (操作后可能产生新的边缘字符 ) ) )

请问经过 2 64 2^{64} 264 次操作后,字符串 S S S 变成了怎样的字符串,如果结果为空则输出 E M P T Y \mathrm{EMPTY} EMPTY

【输入格式】

输入一行包含一个字符串 S S S

【输出格式】

输出一行包含一个字符串表示答案,如果结果为空则输出 E M P T Y \mathrm{EMPTY} EMPTY

【样例输入 1】

【样例输出 1】

【样例输入 2】

【样例输出 2】

【评测用例规模与约定】

对于 25 % 25\% 25% 的评测用例, ∣ S ∣ ≤ 1 0 3 |S | ≤ 10^3 S103 ,其中 ∣ S ∣ |S| S 表示 S S S 的长度;
对于 50 % 50\% 50% 的评测用例, ∣ S ∣ ≤ 1 0 4 |S| ≤ 10^4 S104
对于 75 % 75\% 75% 的评测用例, ∣ S ∣ ≤ 1 0 5 |S| ≤ 10^5 S105
对于所有评测用例, ∣ S ∣ ≤ 1 0 6 |S| ≤ 10^6 S106 S S S 中仅含小写字母。

签到 × 5 ×\ 5 × 5

如果我们将连续相同的字符划分在一块同时操作,

考虑最差情况,一、所有字符都相同,那么单次操作次数为 1 1 1,操作完 ∣ S ∣ 2 \frac{|S|}2 2S 次后字符串不再变化;二、字符全部被划分长度为 2 2 2 的连续块,单次操作次数为 ∣ S ∣ 2 \frac{|S|}2 2S,操作完 1 1 1 次后字符串不再变化;

不等式估一下最大值,看似是暴力解,实则复杂度仅为 O ( n ) O(n) O(n)

上例程序实际复杂度在 O ( n 2 ) O(n^2) O(n2),但可以通过 dotcpp 上全部用例,下面用双端链表实现 O ( n ) O(n) O(n) 写法:

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 20 20 20

【问题描述】

给定一个数组 A A A 和一些查询 L i , R i L_i, R_i Li,Ri,求数组中第 L i L_i Li 至第 R i R_i Ri 个元素之和。

小蓝觉得这个问题很无聊,于是他想重新排列一下数组,使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组,所有查询结果的总和最多可以增加多少?

【输入格式】

输入第一行包含一个整数 n n n

第二行包含 n n n 个整数 A 1 , A 2 , ⋯ , A n A_1, A_2,\cdots, A_n A1,A2,,An,相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m m m 表示查询的数目。

接下来 m m m 行,每行包含两个整数 L i 、 R i L_i、R_i LiRi ,相邻两个整数之间用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

【样例输出】

【样例说明】
原来的和为 6 + 14 = 20 6 + 14 = 20 6+14=20,重新排列为 ( 1 , 4 , 5 , 2 , 3 ) (1, 4, 5, 2, 3) (1,4,5,2,3) 后和为 10 + 14 = 24 10 + 14 = 24 10+14=24,增加了 4 4 4

【评测用例规模与约定】

对于 30 % 30\% 30% 的评测用例, n , m ≤ 50 n, m ≤ 50 n,m50
对于 50 % 50\% 50% 的评测用例, n , m ≤ 500 n, m ≤ 500 n,m500
对于 70 % 70\% 70% 的评测用例, n , m ≤ 5000 n, m ≤ 5000 n,m5000
对于所有评测用例, 1 ≤ n , m ≤ 1 0 5 , 1 ≤ A i ≤ 1 0 6 , 1 ≤ L i ≤ R i ≤ 1 0 6 1 ≤ n, m ≤ 10^5,1 ≤ A_i ≤ 10^6,1 ≤ L_i ≤ R_i ≤ 10^6 1n,m1051Ai1061LiRi106

签到 × 6 ×\ 6 × 6

差分统计单点被覆盖的次数,然后把大的元素尽可能往覆盖次数多的点塞就行了。

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 25 25 25

【问题描述】

小蓝最近正在玩一款 R P G \mathrm{RPG} RPG 游戏。他的角色一共有 N N N 个可以加攻击力的技能。其中第 i i i 个技能首次升级可以提升 A i A_i Ai 点攻击力,以后每次升级增加的点数都会减少 B i B_i Bi ⌈ A i B i ⌉ \lceil\frac{A_i}{B_i}\rceil BiAi (上取整) 次之后,再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M M M 次技能,他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?

【输入格式】

输入第一行包含两个整数 N N N M M M

以下 N N N 行每行包含两个整数 A i A_i Ai B i B_i Bi

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 40 % 40\% 40% 的评测用例, 1 ≤ N , M ≤ 1000 1 ≤ N, M ≤ 1000 1N,M1000
对于 60 % 60\% 60% 的评测用例, 1 ≤ N ≤ 1 0 4 , 1 ≤ M ≤ 1 0 7 1 ≤ N ≤ 10^4, 1 ≤ M ≤ 10^7 1N104,1M107
对于所有评测用例, 1 ≤ N ≤ 1 0 5 , 1 ≤ M ≤ 2 × 1 0 9 , 1 ≤ A i , B i ≤ 1 0 6 1 ≤ N ≤ 10^5,1 ≤ M ≤ 2 × 10^9,1 ≤ A_i, B_i ≤ 10^6 1N1051M2×1091Ai,Bi106

签到 × 7 ×\ 7 × 7

i i i 个技能,在升级第 k k k 次时提升的攻击力为 A i − ( k − 1 ) B i A_i -(k – 1)B_i Ai(k1)Bi,呈单调递减,也就是说,将所有可能的提升 A i − k B i A_i -kB_i AikBi 排成一个单调不上升序列,我们只取前 M M M 项是显然合法的。

故我们二分前 M M M 项的最小值,若所有不小于它的增量个数大于 M M M,我们另 r i g h t = m i d right = mid right=mid,否则另 l e f t = m i d + 1 left = mid + 1 left=mid+1,对于计算大于 M M M 的增量个数, A i A_i Ai m i d mid mid 之间可选的升级次数为 ⌈ A i − m i d + 1 B i ⌉ \lceil\frac{A_i-mid+1}{B_i}\rceil BiAimid+1,然后特判一下 ∑ i = 1 n B i \sum_{i=1}^nB_i i=1nBi 不大于 M M M

签到题,没什么好讲的。

时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分: 25 25 25

【问题描述】

给定一个数列 A = ( a 1 , a 2 , ⋯ , a n ) A = (a_1, a_2,\cdots, a_n) A=(a1,a2,,an),给出若干询问,每次询问某个区间 [ l i , r i ] [l_i,r_i] [li,ri] 内恰好出现 k i k_i ki 次的数有多少个。

【输入格式】

输入第一行包含一个整数 n n n 表示数列长度。

第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_1, a_2,\cdots, a_n a1,a2,,an,表示数列中的数。

第三行包含一个整数 m m m 表示询问次数。

接下来 m m m 行描述询问,其中第 i i i 行包含三个整数 l i , r i , k i l_i, r_i, k_i li,ri,ki 表示询问 [ l i , r i ] [l_i,r_i] [li,ri] 区间内有多少数出现了 k i k_i ki 次。

【输出格式】

输出 m m m 行,分别对应每个询问的答案。

【样例输入】

【样例输出】

【评测用例规模与约定】

对于 20 % 20\% 20% 的评测用例, n , m ≤ 500 , 1 ≤ a 1 , a 2 , ⋯ , a n ≤ 1000 n, m ≤ 500, 1 ≤ a_1, a_2,\cdots, a_n ≤ 1000 n,m500,1a1,a2,,an1000
对于 40 % 40\% 40% 的评测用例, n , m ≤ 5000 n, m ≤ 5000 n,m5000
对于所有评测用例, 1 ≤ n , m ≤ 100000 , 1 ≤ a 1 , a 2 , ⋅ ⋅ ⋅ , a n ≤ 100000 , 1 ≤ l i ≤ r i ≤ n , 1 ≤ k i ≤ n 1 ≤ n, m ≤ 100000, 1 ≤ a_1, a_2, · · · , a_n ≤ 100000, 1 ≤ l_i ≤ r_i ≤ n, 1 ≤ k_i ≤ n 1n,m100000,1a1,a2,,an100000,1lirin,1kin

莫队分块

签到 × 8 ×\ 8 × 8

模板题。

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/2733.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部