第十二届蓝桥杯 2021年省赛真题 (C/C++ 大学C组) 第二场

本题总分: 5 5 5 分 问题描述 I E E E 754 \mathrm{IEEE}\ 75…

本题总分: 5 5 5

问题描述

I E E E 754 \mathrm{IEEE}\ 754 IEEE 754 规定一个双精度浮点数由 1 1 1 位符号位、 11 11 11 位阶和 52 52 52 位尾数组成(以上位数都表示二进制位数)。
请问,按此规定一个双精度浮点数占用几个字节?

答案提交

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

8

有点无力吐槽。

本题总分: 5 5 5

问题描述

C / C \mathrm{C/C} C/C++ / J a v a / P y t h o n \mathrm{/Java/Python} /Java/Python 等语言中,使用 % \% % 表示求余,请问 2021 % 20 2021\%20 2021%20 的值是多少?

答案提交

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

1

试图把我激怒。

本题总分: 10 10 10

问题描述

一个正整数的双阶乘,表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。 n n n 的双阶乘用 n ! ! n!! n!! 表示。
例如:
3 ! ! = 3 × 1 = 3 3!! = 3 × 1 = 3 3!!=3×1=3
8 ! ! = 8 × 6 × 4 × 2 = 384 8!! = 8 × 6 × 4 × 2 = 384 8!!=8×6×4×2=384
11 ! ! = 11 × 9 × 7 × 5 × 3 × 1 = 10395 11!! = 11 × 9 × 7 × 5 × 3 × 1 = 10395 11!!=11×9×7×5×3×1=10395
请问, 2021 ! ! 2021!! 2021!! 的最后 5 5 5 位(这里指十进制位)是多少?
注意: 2021 ! ! = 2021 × 2019 × ⋅ ⋅ ⋅ × 5 × 3 × 1 2021!! = 2021 × 2019 × · · · × 5 × 3 × 1 2021!!=2021×2019××5×3×1
提示:建议使用计算机编程解决问题。

答案提交

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

59375

简单的离谱。

本题总分: 10 10 10

问题描述

如果一个点 ( x , y ) (x, y) (x,y) 的两维坐标都是整数,即 x ∈ Z x ∈ Z xZ y ∈ Z y ∈ Z yZ,则称这个点为一个格点。
如果一个点 ( x , y ) (x, y) (x,y) 的两维坐标都是正数,即 x > 0 x > 0 x>0 y > 0 y > 0 y>0,则称这个点在第一象限。
请问在第一象限的格点中,有多少个点 ( x , y ) (x, y) (x,y) 的两维坐标乘积不超过 2021 2021 2021,即 x ⋅ y ≤ 2021 x · y ≤ 2021 xy2021
提示:建议使用计算机编程解决问题。

答案提交

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

15698

朴素解法

倍数法

诚然,朴素的去枚举二元组 ( x , y ) (x,y) (x,y),可以在一个理想的时间内计算出答案。

但我希望每个人在编程时,还是尽可能的考虑当数据再大若干个量级时,我们所选取的策略是否还是良性的。

比如这道题朴素枚举的复杂度在 O ( n 2 ) O(n^2) O(n2),而我们只要稍加思索就能发现,这道题与统计不大于 2021 2021 2021 的自然数中的每个数的因数个数等价。

因为对于任意不同的自然数 n = x × y n = x × y n=x×y,生成其的二元组 ( x , y ) (x,y) (x,y) 互相独立,于是问题等价于上述命题。

这时我们选用倍数法去统计因数个数之和,即可在 O ( n log ⁡ n ) O(n \log n) O(nlogn) 的复杂度下计算出答案,这是因为不大于 n n n 的自然数的因数个数之和约等于 n log ⁡ n n \log n nlogn 个,而倍数法对于每个因数只统计一次。

本题总分: 15 15 15

问题描述

3 3 3 分解成两个正整数的和,有两种分解方法,分别是 3 = 1 + 2 3 = 1 + 2 3=1+2 3 = 2 + 1 3 = 2 + 1 3=2+1。注意顺序不同算不同的方法。
5 5 5 分解成三个正整数的和,有 6 6 6 种分解方法,它们是 1 + 1 + 3 = 1 + 2 + 2 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 2 + 1 = 3 + 1 + 1 1+1+3 = 1+2+2 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 2 + 1 = 3 + 1 + 1 1+1+3=1+2+2=1+3+1=2+1+2=2+2+1=3+1+1
请问,将 2021 2021 2021 分解成五个正整数的和,有多少种分解方法?

答案提交

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

691677274345

归纳法

对于 n n n n ∈ Z + n \in \mathbb{Z^+} nZ+,设 n n n 划分 n ′ n' n 个的方案数为 f n , n ′ f_{n,n'} fn,n

划分为 1 1 1 个正整数的方案为一,即 n n n

划分为 2 2 2 个正整数的方案,有 n − 1 n – 1 n1 种,即 { n − k , k } \{n-k,k\} {nk,k} k ∈ Z + k \in \mathbb{Z^+} kZ+ n ≥ 2 n \geq 2 n2

划分为 3 3 3 个正整数的方案,有 ( n − 1 ) ( n − 2 ) 2 \cfrac{(n-1)(n-2)}{2} 2(n1)(n2) 种,即 ∑ i = 2 n − 1 ( f i , 2 × f n − i , 1 ) = ∑ i = 2 n − 1 ( i − 1 ) \displaystyle\sum_{i = 2}^{n-1} (f_{i,2} ×f_{n-i,1}) = \displaystyle\sum_{i = 2}^{n-1} (i – 1) i=2n1(fi,2×fni,1)=i=2n1(i1) n ≥ 3 n \geq 3 n3

划分为 5 5 5 个正整数的方案,有 ∑ i = 3 n − 2 ( f i , 3 × f n − i , 2 ) = ∑ i = 3 n − 2 ( i − 1 ) ( i − 2 ) ( n − i − 1 ) 2 = n 2 ∑ i = 3 n − 2 { ( i − 1 ) ( i − 2 ) } − 1 2 ∑ i = 3 n − 2 { ( i 2 − 1 ) ( i − 2 ) } = n 2 ( ( n − 3 ) ( n − 4 ) ( 2 n − 7 ) 6 + ( n + 1 ) ( n − 4 ) 2 − 2 ( n − 4 ) ) − 1 2 ( ( ( n − 2 ) ( n − 3 ) 2 ) 2 + ( n − 1 ) ( n − 2 ) ( 2 n − 3 ) 6 − ( 2 n − 1 ) ( n − 4 ) − 6 ) \displaystyle\sum_{i = 3}^{n-2} (f_{i,3} ×f_{n-i,2}) = \displaystyle\sum_{i=3}^{n-2} \cfrac{(i-1)(i-2)(n-i-1)}{2} = \frac n2\displaystyle\sum_{i=3}^{n-2}\{(i-1)(i-2)\} – \frac12\displaystyle\sum_{i=3}^{n-2}\{(i^2-1)(i-2)\} = \frac n2\left(\cfrac{(n-3)(n-4)(2n-7)}{6} + \cfrac{(n+1)(n-4)}{2} – 2(n-4)\right) – \frac 12\left((\cfrac{(n-2)(n-3)}2)^2+\cfrac{(n-1)(n-2)(2n-3)}{6}-(2n – 1)(n-4)-6\right) i=3n2(fi,3×fni,2)=i=3n22(i1)(i2)(ni1)=2ni=3n2{(i1)(i2)}21i=3n2{(i21)(i2)}=2n(6(n3)(n4)(2n7)+2(n+1)(n4)2(n4))21((2(n2)(n3))2+6(n1)(n2)(2n3)(2n1)(n4)6) n ≥ 5 n \geq 5 n5

其实是等于 C 2020 4 C_{2020}^{4} C20204 的,但整理太费事了。

而且整理通项公式也容易出错,

我的建议是直接暴力累加。

数理分析

如果将 n n n 看做 n n n 1 1 1 累加的结果,即 2021 = 1 + 1 + ⋯ + 1 ⏟ 2021 2021 = \begin{matrix} \underbrace{ 1+1+\cdots+1 } \\ 2021\end{matrix} 2021= 1+1++12021,将每个 + + + 视作一个间隙,则间隙共有 2020 2020 2020 个,对于每一种划分,我们都可以表示成任选四个间隙,然后先对间隙外的 1 1 1 求和,

比如:

15 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = ( 1 + 1 + 1 + 1 + 1 ) + ( 1 + 1 + 1 + 1 ) + ( 1 + 1 + 1 ) + ( 1 + 1 ) + 1 = 5 + 4 + 3 + 2 + 1 \begin{aligned} 15&=1+1+1+1+1{\color{red}\:+\:}1+1+1+1{\color{red}\:+\:}1+1+1{\color{red}\:+\:}1+1{\color{red}\:+\:}1\\ &=(1+1+1+1+1){\color{red}+}(1+1+1+1){\color{red}+}(1+1+1){\color{red}+}(1+1){\color{red}+}1\\ &= 5 + 4 + 3 + 2 + 1 \end{aligned} 15=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=(1+1+1+1+1)+(1+1+1+1)+(1+1+1)+(1+1)+1=5+4+3+2+1

n = 2021 n = 2021 n=2021 时,这样的划分有 C 2021 − 1 4 C_{2021-1}^4 C202114 个,

不能说跟概率毫不相干,

所以标题起了这个。

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

问题描述

小蓝对 3 3 3 的倍数很感兴趣。现在他手头有三个不同的数 a , b , c a, b, c a,b,c,他想知道,这三个数中是不是有两个数的和是 3 3 3 的倍数。
例如,当 a = 3 , b = 4 , c = 6 a = 3, b = 4, c = 6 a=3,b=4,c=6 时,可以找到 a a a c c c 的和是 3 3 3 的倍数。
例如,当 a = 3 , b = 4 , c = 7 a = 3, b = 4, c = 7 a=3,b=4,c=7 时,没办法找到两个数的和是 3 3 3 的倍数。

输入格式

输入三行,每行一个整数,分别表示 a , b , c a, b, c a,b,c

输出格式

如果可以找到两个数的和是 3 3 3 的倍数,输出 y e s yes yes,否则输出 n o no no

测试样例1

测试样例2

评测用例规模与约定

对于所有评测用例, 1 ≤ a ≤ b ≤ c ≤ 100 1 ≤ a ≤ b ≤ c ≤ 100 1abc100

两数整数之和为 3 3 3 的倍数,只存在两数皆为 3 3 3 的倍数,和两数除 3 3 3 分别余 2 2 2 1 1 1 这两种情况。

能把代码写的薛微优雅一点。

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

问题描述

今年是 2021 2021 2021 年, 2021 2021 2021 这个数字非常特殊,它的千位和十位相等,个位比百位大 1 1 1,我们称满足这样条件的年份为特殊年份。
输入 5 5 5 个年份,请计算这里面有多少个特殊年份。

输入格式

输入 5 5 5 行,每行一个 4 4 4 位十进制数(数值范围为 1000 1000 1000 9999 9999 9999),表示一个年份。

输出格式

输出一个整数,表示输入的 5 5 5 个年份中有多少个特殊年份。

测试样例1

题出的都是些什么玩意,

算法掺了点 B C D \mathrm{BCD} BCD码。

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

问题描述

小蓝发现,对于一个正整数 n n n 和一个小于 n n n 的正整数 v v v,将 v v v 平方后对 n n n 取余可能小于 n n n 的一半,也可能大于等于 n n n 的一半。
请问,在 1 1 1 n − 1 n − 1 n1 中,有多少个数平方后除以 n n n 的余数小于 n n n 的一半。
例如,当 n = 4 n = 4 n=4 时, 1 , 2 , 3 1, 2, 3 1,2,3 的平方除以 4 4 4 的余数都小于 4 4 4 的一半。
又如,当 n = 5 n = 5 n=5 时, 1 , 4 1, 4 1,4 的平方除以 5 5 5 的余数都是 1 1 1,小于 5 5 5 的一半。而 2 , 3 2, 3 2,3 的平方除以 5 5 5 的余数都是 4 4 4,大于等于 5 5 5 的一半。

输入格式

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

输出格式

输出一个整数,表示满足条件的数的数量。

测试样例1

评测用例规模与约定

对于所有评测用例, 1 ≤ n ≤ 10000 1 ≤ n ≤ 10000 1n10000

写了个 ∑ i = 1 n − 1 ⌊ 2 ( i 2 − n ⌊ i 2 n ⌋ ) n ⌋ \displaystyle\sum_{i=1}^{n-1}\left\lfloor\cfrac{2(i^2 – n\lfloor\frac {i^{_2}}n\rfloor)}n\right\rfloor i=1n1n2(i2nni2) 研究半天,毛都没研究出来。

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

问题描述

一个整数 a a a 是一个完全平方数,是指它是某一个整数的平方,即存在一个整数 b b b,使得 a = b 2 a = b^{2} a=b2
给定一个正整数 n n n,请找到最小的正整数 x x x,使得它们的乘积是一个完全平方数。

输入格式

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

输出格式

输出找到的最小的正整数 x x x

测试样例1

测试样例2

评测用例规模与约定

对于 30 30 30% 的评测用例, 1 ≤ n ≤ 1000 1 ≤ n ≤ 1000 1n1000,答案不超过 1000 1000 1000
对于 60 60 60% 的评测用例, 1 ≤ n ≤ 1 0 8 1 ≤ n ≤ 10^{8} 1n108,答案不超过 1 0 8 10^{8} 108
对于所有评测用例, 1 ≤ n ≤ 1 0 12 1 ≤ n ≤ 10^{12} 1n1012,答案不超过 1 0 12 10^{12} 1012

每届必考的算术基本定理。

a = b 2 = ∏ p i 2 k i a = b^2 = \prod p^{2k_{i}}_{i} a=b2=pi2ki n x = ∏ p i k n i + k x i nx = \prod p^{k_{n_{i}} +k_{x_{i}}}_{i} nx=pikni+kxi

x = ∏ p i k x i x = \prod p^{k_{x_{i}}}_{i} x=pikxi,满足 2 ∣ ( k n i + k x i ) 2 \mid (k_{n_{i}} +k_{x_{i}}) 2(kni+kxi),且 x i x_i xi 最小即可。

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

问题描述

n n n 台计算机,第 i i i 台计算机的运算能力为 v i v_{i} vi
有一系列的任务被指派到各个计算机上,第 i i i 个任务在 a i a_{i} ai 时刻分配,指定计算机编号为 b i b_{i} bi ,耗时为 c i c_{i} ci 且算力消耗为 d i d_{i} di 。如果此任务成功分配,将立刻开始运行,期间持续占用 b i b_{i} bi 号计算机 d i d_{i} di 的算力,持续 c i c_{i} ci 秒。
对于每次任务分配,如果计算机剩余的运算能力不足则输出 − 1 −1 1,并取消这次分配,否则输出分配完这个任务后这台计算机的剩余运算能力。

输入格式

输入的第一行包含两个整数 n , m n, m n,m,分别表示计算机数目和要分配的任务数。
第二行包含 n n n 个整数 v 1 , v 2 , ⋅ ⋅ ⋅ v n v_{1}, v_{2}, · · · v_{n} v1,v2,vn,分别表示每个计算机的运算能力。
接下来 m m m 行每行 4 4 4 个整数 a i , b i , c i , d i a_{i}, b_{i}, c_{i}, d_{i} ai,bi,ci,di,意义如上所述。数据保证 a i a_{i} ai 严格递增,即 a i < a i + 1 a_{i} < a_{i+1} ai<ai+1

输出格式

输出 m m m 行,每行包含一个数,对应每次任务分配的结果。

测试样例1

评测用例规模与约定

对于 20 20 20% 的评测用例, n , m ≤ 200 n, m ≤ 200 n,m200
对于 40 40 40% 的评测用例, n , m ≤ 2000 n, m ≤ 2000 n,m2000
对于所有评测用例, 1 ≤ n , m ≤ 200000 1 ≤ n, m ≤ 200000 1n,m200000 1 ≤ a i , c i , d i , v i ≤ 1 0 9 1 ≤ a_{i}, c_{i}, d_{i}, v_{i} ≤ 10^{9} 1ai,ci,di,vi109 1 ≤ b i ≤ n 1 ≤ b_{i} ≤ n 1bin

优先列队模拟,

一个小时干完十道题,麻了。

不想出题可以外包,真的。

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

作者: HUI

发表评论

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

返回顶部