2020年第十一届蓝桥杯A组国赛(C/C++)

A. 合数个数(5 分) 答案:1713 试题 A: 合数个数(5 …

A. 合数个数(5 分)
答案:1713

试题 A: 合数个数(5 分)
【问题描述】

一个数如果除了 1 和自己还有其他约数,则称为一个合数。例如:1, 2, 3不是合数,4, 6 是合数。
请问从 1 到 2020 一共有多少个合数。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

思路:
1~2020共有2020个数,因此我们只要求出素数的个数,结果便是2020-素数个数。


B.含 2 天数(5 分)
答案:1994240

试题 B: 含 2 天数(5 分)
【问题描述】

小蓝特别喜欢 2,今年是公元 2020 年,他特别高兴,因为每天日历上都可以看到 2。
如果日历中只显示年月日,请问从公元 1900 年 1 月 1 日到公元 9999 年 12月 31 日,一共有多少天日历上包含 2。即有多少天中年月日的数位中包含数字2。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

思路:
简单模拟。
只需要枚举1900年1月1号到9999年12月31日的每一天,判断该天的时期是否包含2;若包含,则结果加1.


C.本质上升序列(10 分)
答案:3616159

试题 C: 本质上升序列(10 分)
【问题描述】

小蓝特别喜欢单调递增的事物。
在一个字符串中,如果取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。
例如,在字符串 lanqiao 中,如果取出字符 n 和 q,则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。
小蓝发现,有些子序列虽然位置不同,但是字符序列是一样的,例如取第二个字符和最后一个字符可以取到 ao,取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。
对于一个字符串,小蓝想知道,本质不同的递增子序列有多少个?
例如,对于字符串 lanqiao,本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。
请问对于以下字符串(共 200 个小写英文字母,分四行显示):
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

思路:
线性dp。 我们定义状态f[i]表示以字符s[i]结尾的本质不同的方案数。显然,这样定义状态是没有后效性的,因为f[i]不会涉及到第i个字符之后的字符。那么状态如何转移呢?首先可以发现,第i个字符的状态只会和前i-1个字符有关;因此我们需要枚举前i-1个字符;

  1. 前i-1个字符中有某个字符j和s[i]相同时,那么这里会出现重复的方案;但是由于f[i]是一定已经包含了f[j]的,所以我们为了避免重复,可以令f[j]=0
  2. 前i-1个字符中有某个字符j小于s[i]时,那么f[i]+=f[j]。因为s[i]>s[j],所以可以继承f[j]的所有方案。
  3. 前i-1个字符中有某个字符j大于s[i]时,那么跳过即可。
    最后结果便是f[1]+f[2]+…+f[200]。


D.咫尺天涯(10 分)
答案:

试题 D: 咫尺天涯(10 分)
【问题描述】

皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形,它是从左下角出发,经过一个 3 × 3 的方格中的每一个格子,最终到达右上角的一条曲线。
在这里插入图片描述
设每个格子的边长为 1,在上图中,有的相邻的方格(四相邻)在皮亚诺曲线中也是相邻的,在皮亚诺曲线上的距离是 1,有的相邻的方格在皮亚诺曲线中不相邻,距离大于 1。
例如,正中间方格的上下两格都与它在皮亚诺曲线上相邻,距离为 1,左右两格都与它在皮亚诺曲线上不相邻,距离为 3。
下图给出了皮亚诺曲线的 2 阶情形,它是经过一个3^2× 3 ^2 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。
在这里插入图片描述
下图给出了皮亚诺曲线的 3 阶情形,它是经过一个 3^3 × 3 ^3 的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。
在这里插入图片描述
皮亚诺曲线总是从左下角开始出发,最终到达右上角。
小蓝对于相邻的方格在皮亚诺曲线上的相邻关系很好奇,他想知道相邻的方格在曲线上的距离之和是多少。
例如,对于 1 阶皮亚诺曲线,距离和是 24,有 8 对相邻的方格距离为 1, 2 对相邻的方格距离为 3,2 对相邻的方格距离为 5。
再如,对于 2 阶皮亚诺曲线,距离和是 816。请求出对于 12 阶皮亚诺曲线,距离和是多少。
提示:答案不超过 10^18。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。


E.玩具蛇(15 分)
答案:552

试题 E: 玩具蛇(15 分)
【问题描述】

小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将玩具蛇放进去。
下图给出了两种方案:
在这里插入图片描述
请帮小蓝计算一下,总共有多少种不同的方案。如果两个方案中,存在玩具蛇的某一节放在了盒子的不同格子里,则认为是不同的方案。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

思路:
dfs。 要是能理解题意,就是模板题。由于数字1的位置有16种情况,所以我们需要枚举每一种情况进行dfs()。


F.皮亚诺曲线距离(15 分)
在这里插入图片描述
在这里插入图片描述在这里插入图片描述


G.出租车(20分)
在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述


H.答疑(20分)
在这里插入图片描述在这里插入图片描述

思路:
贪心。 我们要求让每个同学发信息的时刻和最小,我们可以发现一定的规律。首先,每个同学的s[i]+a[i]一定是在最后结果里的;因为每个同学都需要完成进入办公室和问完问题以后才能发信息;然后第2个同学的开始时间便是第一个同学的结束时刻,即s[1]+a[1]+e[1];第3个同学的开始时间便是第2个同学的结束时刻,即s[1]+s[2]+a[1]+a[2]+e[1]+e[2];…;第n个同学的开始时间便是第n-1个同学的结束时刻,即s[1]+s[2]+…+s[n-1]+a[1]+a[2]+…+a[n-1]+e[1]+e[2]+…+e[n-1];我们将每个同学用的所有时间s[i]+a[i]+e[i]记为num[i];那么很显然规律便是num[1]加了n-1次,num[2]加了n-2次,…,num[n-1]加了1次;所以我们只需要把num[1~n]排好序,便可以求出结果。
注意:结果要开long long


I.奇偶覆盖(25分)
在这里插入图片描述
在这里插入图片描述

思路:
暴力骗40分。 一个样例规模,有40%的样例n<=1000;l,r,b,t<=100;显然可以直接暴力;枚举每一个矩形;再遍历该矩形的每一个面积为1的小方格;将其标记值a[i][j]+1;标记值a[i][j]表明第i行第j列的小矩形被覆盖的次数。
时间复杂度:O(n*max(l,r)*max(b,t))


J.蓝跳跳(25分)
在这里插入图片描述在这里插入图片描述

思路:
动态规划+暴力。 我们用数组f[i][j]表示状态:蓝跳跳跳到了位置 i 且已经 j 次连续跳跃距离超过p。 显然这样定义状态以后结果便是f[L][0]+f[L][1]。 既然状态已经有了,那是怎么转移呢?显然由于蓝跳跳一步可以跳距离1~k;所以位置i处的状态与i-k,i-k+1,…,i-1有关 ;显然;我们可以枚举可能跳跃的距离1~k;此时由于跳跃距离可能小于p,也可能大于p;我能需要分类讨论:

  1. 当跳跃距离小于p时;此时f[i][0]+=f[i-j][0]+f[i-j][1]。
  2. 当跳跃距离大于等于p时,此时f[i][1]+=f[i-j][0]。
    注意:每次进行加运算都需要mod20201114以防结果溢出。 由于该dp时间复杂度是O(L*k),所以只能拿30分。。。。


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

作者: HUI

发表评论

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

返回顶部