试题 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;
}