试题 A: 美丽的 2
本题总分：5 分
【问题描述】
小蓝特别喜欢 2，今年是公元 2020 年，他特别高兴。
他很好奇，在公元 1 年到公元 2020 年（包含）中，有多少个年份的数位中包含数字 2？
题解
签到题
答案：563
#include <stdio.h>
#include <stdlib.h>
int check(int x)
{
while(x!=0)
{
if(x%10==2)
return 1;
x/=10;
}
return 0;
}
int main()
{
int ans=0;
for(int i=1;i<=2020;i++)
{
if(check(i))
ans++;
}
printf("%d",ans);
return 0;
}
试题 B: 扩散
本题总分：5 分
【问题描述】
小蓝在一张无限大的特殊画布上作画。
这张画布可以看成一个方格图，每个格子可以用一个二维的整数坐标表示。
小蓝在画布上首先点了一下几个点：(0, 0), (2020, 11), (11, 14), (2000, 2000)。
只有这几个格子上有黑色，其它位置都是白色的。
每过一分钟，黑色就会扩散一点。具体的，如果一个格子里面是黑色，它
就会扩散到上、下、左、右四个相邻的格子中，使得这四个格子也变成黑色
（如果原来就是黑色，则还是黑色）。
请问，经过 2020 分钟后，画布上有多少个格子是黑色的
题解
#include <stdio.h>
#include <stdlib.h>
//由最大点（4040，4020规定空间）
int map[6080][6050]; //增加点空间可以避免讨论边界问题
int dir[4][2]={
{
1,0},{
0,1},{
-1,0},{
0,-1}};
typedef struct node{
int x;
int y;
int step; //当达到2020时我们就不以该结点来生成新结点
struct node * next;
} Node;
typedef struct{
struct node * front; //头指针
struct node * rear; //尾指针
int size;
}Queue;
void Init(Queue *q)
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
int isEmpty(Queue *q)
{
if(q->size==0)
return 1;
return 0;
}
void EnQueue(int x,int y,int step,Queue *q)
{
Node *pnew = (Node *)malloc(sizeof(Node));
pnew->x = x;
pnew->y = y;
pnew->step = step;
pnew->next = NULL;
if(isEmpty(q))
{
q->front = q->rear = pnew;
}
else
{
q->rear->next = pnew;
q->rear = pnew;
}
q->size++;
}
void DeQueue(Node *temp,Queue *q)
{
Node *t = q->front;
*temp = *t; //把t的值赋到temp的地址上
q->front = q->front->next;
q->size--;
if(isEmpty(q))
q->rear=NULL;
free(t);
}
void BFS()
{
Queue q;
Init(&q);
EnQueue(2020,2020,0,&q);
EnQueue(4040,2031,0,&q);
EnQueue(2031,2034,0,&q);
EnQueue(4020,4020,0,&q);
map[2020][2020]=1;
map[4040][2031]=1;
map[2031][2034]=1;
map[4020][4020]=1;
Node temp;
while(!isEmpty(&q))
{
DeQueue(&temp,&q);
if(temp.step==2020)
continue;
for(int i=0;i<4;i++)
{
int x=temp.x+dir[i][0];
int y=temp.y+dir[i][1];
if(!map[x][y])
{
map[x][y]=1;
EnQueue(x,y,temp.step+1,&q);
}
}
}
}
int main()
{
int i,j;
int ans=0;
BFS();
for(i=0;i<6080;i++)
for(j=0;j<6050;j++)
if(map[i][j])
ans++;
printf("%d",ans);
return 0;
}
试题 C: 阶乘约数
本题总分:10 分
【问题描述】
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
题解
(本来我推出来是2^(n-1),看答案发现错了)
数论：
6的约数（1,2,3,6），6=23（质因数分解）,约数个数为：（1+1）（1+1）——2质数个数乘3质数个数
24的约数（1,2,3,4,6,8,12,24） 24=2223 ,约数个数为：（3+1）(1+1)
就是质因数分解，由于阶乘的数很大我们不能直接对其进行质因数分解，只能对组成它的数进行质因数分解（1—100）
该质因数分解的代码：
任何非质数都是由质数组成我们从最小的质数2开始分解就解决了后面非质数的问题，如：4就可以被两个质数2分解，24就是3个质数2，1个质数3.
答案：39001250856960000
#include <stdio.h>
#include <stdlib.h>
int main()
{
int num[101]={
0},i,j;
for(i=2;i<=100;i++)
{
int t=i;
j=2;
while(t>1)
{
if(t%j==0)
{
num[j]++;
t/=j;
}
else
j++;
}
}
long long int ans=1;
for(i=2;i<=100;i++)
{
printf("%d:%d\n",i,num[i]);
if(num[i]!=0)
ans*=(num[i]+1);
}
printf("%lld",ans);
return 0;
}
试题 D: 本质上升序列
问题描述】
小蓝特别喜欢单调递增的事物。
在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
例如，在字符串 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 个小写英文字母，分四行显示）：如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个？
题解
LIS问题加上简单的去重：
LIS问题可以看看我之前写的博客：https://blog.csdn.net/m0_52103105/article/details/116404276?spm=1001.2014.3001.5501
答案：3616159
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char str[202];
scanf("%s",str);
int i,j,k;
int dp[202],len=strlen(str);
for(i=0;i<len;i++)
{
int flag=1;
for(j=0;j<i;j++)
if(str[i]==str[j])
flag=0;
if(flag)
dp[i]=1;
else
dp[i]=0;
}
for(i=1;i<len;i++){
for(j=0;j<i;j++)
if(str[i]>str[j])
{
int flag=1;
for(k=j+1;k<i;k++)
if(str[k]==str[i])
flag=0;
if(flag)
dp[i]+=dp[j];
}
printf("%d:%d\n",i,dp[i]);
}
int ans=0;
for(i=0;i<len;i++)
ans+=dp[i];
printf("%d\n",ans);
return 0;
}
试题 E: 玩具蛇
【问题描述】
小蓝有一条玩具蛇，一共有 16 节，上面标着数字 1 至 16。每一节都是一
个正方形的形状。相邻的两节可以成直线或者成 90 度角。
小蓝还有一个 4×4 的方格盒子，用于存放玩具蛇，盒子的方格上依次标着
字母 A 到 P 共 16 个字母。
小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将
玩具蛇放进去。
下图给出了两种方案：
题解
送分题了，直接dfs就好了，加个数组去重就行。
答案：552
#include <stdio.h>
#include <stdlib.h>
int map[4][4];
int save[1000][4][4];
int count;
int has_map() //查重
{
int i,j,k;
for(k=0;k<count;k++){
int flag=1;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
if(map[i][j]!=save[count][i][j])
flag=0;
}
if(flag==1)
return 1;
}
/*for(int a=0;a<4;a++)
for(int b=0;b<4;b++)
{
printf("%d ",map[a][b]);
if(b==3)
putchar('\n');
}*/
return 0;
}
int dir[4][2]={
{
1,0},{
-1,0},{
0,1},{
0,-1} };
void DFS(int x,int y,int step)
{
int i;
map[x][y]=step;
if(step==16)
{
if(!has_map())
count++;
return ;
}
for(i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if( xx>=0 && xx<4 && yy>=0 && yy<4 && !map[xx][yy])
{
DFS(xx,yy,step+1);
map[xx][yy]=0;
}
}
}
int main()
{
int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
for(int a=0;a<4;a++)
for(int b=0;b<4;b++)
map[a][b]=0; //初始化
DFS(i,j,1);
}
printf("%d",count);
return 0;
}
转载：https://blog.csdn.net/m0_52103105/article/details/117233652