2020第十一届蓝桥杯国赛CC++b组总结(填空题)

2020第^一届蓝桥杯国赛C/C++b组总结试题A:美丽的2本题总分：5分【问题描述】小蓝特别喜欢2,今年是公元2020年,他特别高兴。他很好奇,在公元1年到公元2020年(包含)中，有多少个年份的数位中包含数字2?解：直接暴力就好，答案：563试题B:扩散本题总分：5分【问题描述】小蓝在一张无限大的特殊画布上作画。这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。小蓝在画布上首先点了一下几个点:(0,0),(2020,11),(11,14),(2000,2000)o只有这几个格子上有黑色，其它位置都是白色的。每过一分钟,黑色就会扩散一点。具体的，如果一个格子里面是黑色，它就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色(如果原来就是黑色，则还是黑色)。请问，经过2020分钟后，画布上有多少个格子是黑色的。解：BFS,把四个起始点放入queue队列中，然后每次出队列一个,把周围的四个格子变为黑色，标记分钟，直到2020停止答案：20312088#include<iostream>#include<cstmig>#include<striiig>#include<vector>#include<cmath>#include<algorithm>#include<stack>#include<queue>#include<iomanip>#defineN100000#defineINF0x3f3f3f3f#define11longlong#defineIsonltvvl丄mid#definerson11«1|15mid+1usingnamespacestd;boola[8000][8000J;intcnt=2020;intdir[4][2>{0,1,0,-1丄0,・l,0};stnictnode{intx,y,step;};queue<node>qu;voidbfs(){a[0+3000][0+3000]=l;a[2020+3000][ll+3000]=l;a[ll+3000][14+3000]=l;a[2000+3000][2000+3000]=1;qu.push(node{0+3000,0+3000,0});qu.push(node{2020+3000,11+3000,0});qu.pusli(node{11+3000,14+3000,0});qu.push(node{2000+3000,2000+3000,0});while(qu.size()){nodetemp=qu.front();qu.pop()；if(temp.step=cnt)continue;for(inti=0;iv4;i++)intxx=temp.x+dir[i][0];intyy=temp.y+dir[i][1];if(!a[xx][yy])a[xx][yy]=l;qu.push(node{xx,yy,temp.step+1});}}}}intmain(){ios::sync_with_stdio(false);cin.tie(O);cout.tie(O);intij；intsum=0;bfs();for(i=0;i<8000;i++)fbr(j=0;j<8000;j4-+)

sum+=a[i][j];}cout«sum«endl;retrnii0;}试题c试题c：阶乘约数本题总分：10分【问题描述】定义阶乘n!二1X2X3X・•・Xn。请问100!（100的阶乘）有多少个约数。解：其实就是把从那些因子中挑出来问你最多能组成多少个数。为了防止23二6的重复计算，我们不能直接挑，所以要先用唯一分解定理分解成素因子乘积的形式如：5!二12345二2331*51;所以现在的情况变成了：2有4种选择（0、1、2、3个），3有2种选择（0、1个），5有2种选择（0、1个）•即每个素因子的选择个数是其幕次+1。所以对于100!的答案就是把2-100的每一个数进行分解，记录下每一个素因子的个数，然后+1乘起来即可答案：39001250856960000#include<iostream>#include<string>#include<cstring>usingnamespacestd;intmain(){inta[101];longlongsum=l;memset(a,0,sizeof(a));fbr(inti=2;i<=100;i++)inttemp=i;for(intj=2;jv=temp;j++){while(temp%j==0){temp=temp/j;叩］卄;}fbr(inti=2;i<=100;i++)if(a[i]!=O)sum=sum*(a[i]+l);}cout«sum«endl;试题D:本质上升序列本题总分：io分【问题描述】小蓝特別喜欢单调递增的事物。在一个字符串中,如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。例如，在字符串lanqiao中,如果取出字符n和q,则nq组成一个单调递增子序列。类似的单调递增子序列还有lnq、i、ano等等。小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到ao,取最后两个字符也可以取到aoo小蓝认为他们并没有本质不同。对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？例如，对于字符串lanqiao,本质不同的递增子序列有21个。它们分别是1、3、11、q、i^o、In、an>lq、aq>nq、ai^lo、ao>no、io、lnq、anq>lno、ano、aio。请问对于以下字符串（共200个小写英文字母，分四行显示）:（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件iiic.txt,内容与下面的文本相同）tocyjkdzcieoiodfpbgcncsijblmiugdnojjddhllnofawllbhfiadgdcdjstemplmiiijihecoapdjjipnqiiligccevdamfinliqijgililifgdcmxvicfauachlifliafpdccfseflcdgjncadfclvfinadvmaaahalmdsikzssoywakgiifjjaihtniptwoulxbaeqkqhfXvl本质不同的递增子序列有多少个？解：我们先考虑如果出现重复的字符串怎么办：比如axxbxxxb,那么有两个ab递增子序列，则对于该ab递增子序列，在其后面延展字母构成新的递增子序列个数我们可以发现肯定是前一个ab的递增子序列的个数要>=第二个的，可以说第二个的答案是第一个是子集。那么我们对于同一种的递增子序列我们只需要记录其最早出现的即可，后续的出现也不需要管了。基于上述所讲，我们可以使用BFS,使用队列，队列内记录字符串以及该递增子序列最后一个字符的位置，对于每次队首的字符串s,其末尾位置设为t,我们只需要从t+1到s.size（）-l位置找到任何比s[t]大的即可插入到队列中去，这个过程进行去重、计数即可。答案：3616159#include<iostream>#include<cstring>#include<striiig>#include<queue>#include<map>usingnamespacestd;map<string5int>mp;intmain(){stringstr;intans=O;cin»str;queue<pair<stiiiigjnt>>qu;fbr(inti=O;i<=str.size()-l;i++)strings=nn;s=s+str[i];if(!mp[s]){mp[s]++;qu.push(make_pair(s,i));ans++;while(qu.size())stringst=qu.front().first;intii=qu.front().second;qu.popO；for(inti=ii+l;i<=sti\size()-l;i++){if(str[i]>str[ii]&&!mp[st+str[i]]){mp[st+str[i]]=l;qu.push(makejpaii(st+str[i],i));ans++;}}}cout«ans«endl;}试题E:玩具蛇本题总分：15分【问题描述】小蓝有一条玩具蛇,一共有16节,上面标着数字1至16。每一节都

是一个正方形的形状。相邻的两节可以成直线或者成90度角。小蓝还有一个4x4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到P共16个字母。小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。ABCD1234EFGII8765I9JioK11L12N0‘P16151413下图给出了两种方案：A13B12c11D10E14F1G?II9T15J4K3L8"16N5°6p7解：同样是