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

试题 F: 皮亚诺曲线距离

【问题描述】
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形，它是从左下角出发，经过一个 3×3 的
方格中的每一个格子，最终到达右上角的一条曲线.

下图给出了皮亚诺曲线的 2 阶情形，它是经过一个 3 2 × 3 2 的方格中的每一
个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

下图给出了皮亚诺曲线的 3 阶情形，它是经过一个 3 3 × 3 3 的方格中的每一
个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

皮亚诺曲线总是从左下角开始出发，最终到达右上角。
我们将这些格子放到坐标系中，对于 k 阶皮亚诺曲线，左下角的坐标是
(0,0)，右上角坐标是 (3 k − 1,3 k − 1)，右下角坐标是 (3 k − 1,0)，左上角坐标是
(0,3 k − 1)。
给定 k 阶皮亚诺曲线上的两个点的坐标，请问这两个点之间，如果沿着皮
亚诺曲线走，距离是到少？
【输入格式】
输入的第一行包含一个正整数 k，皮亚诺曲线的阶数。
第二行包含两个整数 x 1 , y 1 ，表示第一个点的坐标。
第三行包含两个整数 x 2 , y 2 ，表示第二个点的坐标。
【输出格式】
输出一个整数，表示给定的两个点之间的距离。
【样例输入】
1
0 0
2 2
【样例输出】
8
【样例输入】
2
0 2
0 3
【样例输出】
13
【评测用例规模与约定】
对于 30% 的评测用例，0 ≤ k ≤ 10。
对于 50% 的评测用例，0 ≤ k ≤ 20。
对于所有评测用例，0 ≤ k ≤ 100, 0 ≤ x 1 ,y 1 , x 2 ,y 2 < 3 k , x 1 ,y 1 , x 2 ,y 2 ≤ 10 18 。
数据保证答案不超过 10 18 。

题解
不会，太难了

试题 G: 游园安排

【问题描述】
L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 L 星球
游乐园的管理员。
为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系
统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟
0 个或多个小写英文字母。游客可能重名。
小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部
分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预
约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的
名字。
一个名字 A 小于另一个名字 B 是指：存在一个整数 i，使得 A 的前 i 个字
母与 B 的前 i 个字母相同，且 A 的第 i+1 个字母小于 B 的第 i+1 个字母。（如
果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母，也视为 A 的第 i + 1 个字
母小于 B 的第 i + 1 个字母）
作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽
量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出
上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一
个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此
类推选择第三个、第四个……游客名字最小的方案。
【输入格式】
输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名
字之间没有字符分隔。
【输出格式】
按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。
【样例输入】
WoAiLanQiaoBei
【样例输出】
AiLanQiao
【评测用例规模与约定】
对于 20% 的评测数据，输入的总长度不超过 20 个字母。
对于 50% 的评测数据，输入的总长度不超过 300 个字母。
对于 70% 的评测数据，输入的总长度不超过 10000 个字母。
对于所有评测数据，每个名字的长度不超过 10 个字母，输入的总长度不超
过 1000000 个字母。

题解
LIS问题和上面的本质上升子序列差不多。
（纠正个细节，图稿里的i和j应该代表当前单词的位置）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define Max(a,b) ((a)>(b)?(a):(b))
#define M 1000000

typedef struct
{
    int start;
    int end;
}Word;

int dp[M/10];
char str[M];
Word words[M/10];

int main()
{
    int i,j,k;
    scanf("%s",str);
    int len=strlen(str);
    int count=0;

    for(i=0;i<len;i++)
    {
        if(isupper(str[i]))
        {
            words[count].start=i;
        }
        if(i==len-1 || isupper(str[i+1]))
           words[count++].end=i;
    }

    for(i=0;i<count;i++)
        dp[i]=1;  //初始化状态

    for(i=1;i<count;i++)
        for(j=0;j<i;j++)
    {
        if(str[words[i].start]>str[words[j].start])
        {
            dp[i]=Max(dp[i],dp[j]+1);
        }
        else if(str[words[i].start]==str[words[j].start])
        {
            int flag=1;
            int len_i=words[i].end-words[i].start;
            int len_j=words[j].end-words[j].start;
            int min=len_i>len_j?len_i:len_j;
            for(k=1;k<min;k++)
                if(str[words[i].start+k]<str[words[j].start+k])
                  {
                      flag=0;
                      break;
                  }
                else if(str[words[i].start+k]>str[words[j].start+k])
                {
                    flag=0;
                    dp[i]=Max(dp[i],dp[j]+1);
                    break;
                }
            if(flag=0)
                continue;
            if(len_i>len_j)
                dp[i]=Max(dp[i],dp[j]+1);
        }
    }

    int ans=0;
    for(i=0;i<count;i++)
        if(dp[i]>dp[ans])
        ans=i;
    //printf("%d:%d\n",ans,dp[ans]);
    int start=words[ans-dp[ans]+1].start;
    int end=words[ans].end;
    for(i=start;i<=end;i++)
        printf("%c",str[i]);
    return 0;
}

试题 H: 答疑

【问题描述】
有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。
一位同学答疑的过程如下：

首先进入办公室，编号为 i 的同学需要 s i 毫秒的时间。
然后同学问问题老师解答，编号为 i 的同学需要 a i 毫秒的时间。
答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可
以忽略。
最后同学收拾东西离开办公室，需要 e i 毫秒的时间。一般需要 10 秒、
20 秒或 30 秒，即 e i 取值为 10000，20000 或 30000。
一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群
里面发消息的时刻之和最小。
【输入格式】
输入第一行包含一个整数 n，表示同学的数量。
接下来 n 行，描述每位同学的时间。其中第 i 行包含三个整数 s i , a i , e i ，意
义如上所述。
【输出格式】
输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。
【样例输入】
3
10000 10000 10000
20000 50000 20000
30000 20000 30000
【样例输出】
280000
【样例说明】
按照 1, 3, 2 的顺序答疑，发消息的时间分别是 20000, 80000, 180000。
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n ≤ 20。
对于 60% 的评测用例，1 ≤ n ≤ 200。
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ s i ≤ 60000，1 ≤ a i ≤ 1000000，
e i ∈ {10000,20000,30000}，即 e i 一定是 10000、20000、30000 之一。

题解
全排列问题，我用的是递归法（DFS必定超时），用c++的可以直接调用stl的next函数就行了比我这快多了

#include <stdio.h>
#include <stdlib.h>
#define INF 2<<28

long long int ans=INF;
typedef struct
{
    int s;
    int a;
    int e;
}Answer;


void swap(Answer *a,Answer *b)  //实现互换
{
    Answer t=*a;
    *a=*b;
    *b=t;
}

void perm(Answer s[],int start,int end)
{
    if(start>end)
    {
        int i,next=0;
        long long int sum=0;
        long long int temp=0;

        /*putchar('\n');
        for(i=0;i<=end;i++)
            printf("%d %d %d\n",s[i].s,s[i].a,s[i].e);*/

        for(i=0;i<=end;i++)
        {
            temp=temp+next+s[i].s+s[i].a;
            sum+=temp;
            next=s[i].e;
            /*printf("temp%d sum%d next%d\n",temp,sum,next);*/
        }
        /*printf("%d\n",sum);*/
        if(sum<ans)
            ans=sum;
    }
    else
    {
        int i;
        for(i=start;i<=end;i++)
        {
            swap(&s[i],&s[start]);
            perm(s,start+1,end);
            swap(&s[i],&s[start]);
        }
    }
}

int main()
{
    Answer s[1002];
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d%d%d",&s[i].s,&s[i].a,&s[i].e);
    perm(s,0,n-1);
    printf("%lld\n",ans);

    return 0;
}

试题 I: 出租车

【问题描述】
小蓝在 L 市开出租车。
L 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以看成直线段。东西向的道路互相平行，南北向的道路互相平行，任何一条东西向道路垂直于任何一条南北向道路。
从北到南一共有 n 条东西向道路，依次标号为 H 1 , H 2 , ···, H n 。从西到东一共有 m 条南北向的道路，依次标号为 S 1 , S 2 , ···, S m 。
每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，H i与 S j 的交叉路口记为 (i, j)。
从 H 1 和 S 1 的交叉路口 (1,1) 开始，向南遇到的路口与 (1,1) 的距离分别
是 h 1 , h 2 , ···, h n−1 ，向东遇到路口与 (1,1) 的距离分别是 w 1 , w 2 , ···, w m−1 。道路的每个路口都有一个红绿灯。
时刻 0 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段
时间（每个路口不同），然后南北向变成红灯，东西向变成绿灯，持续一段时间后，再变成南北向绿灯，东西向红灯。
已知路口 (i, j) 的南北向绿灯每次持续的时间为 g ij ，东西向的绿灯每次持
续的时间为 r ij ，红绿灯的变换时间忽略。
当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯，
可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为
看到绿灯，如果刚好由绿灯变为红灯，则视为看到红灯。
每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头，只
能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时
间可以忽略。
小蓝时刻 0 从家出发。今天，他接到了 q 个预约的订单，他打算按照订单
的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。
小蓝的家在两个路口的中点，小蓝喜欢用 x 1 , y 1 , x 2 , y 2 来表示自己家的位
置，即路口 (x 1 ,y 1 ) 到路口 (x 2 ,y 2 ) 之间的道路中点的右侧，保证两个路口相邻（中间没有其他路口）。请注意当两个路口交换位置时，表达的是路的不同两边，路中间有栏杆，因此这两个位置实际要走比较远才能到达。
小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图省时间而同时接两位乘客，也不能插队完成后面的订单。
小蓝只对 L 市比较熟，因此他只会在给定的 n 条东西向道路和 m 条南北向道路上行驶，而且不会驶出 H 1 , H n , S 1 , S m 这几条道路所确定的矩形区域（可以到边界）。小蓝行车速度一直为 1，乘客上下车的时间忽略不计。请问，小蓝最早什么时候能完成所有订单回到家。
【输入格式】
输入第一行包含两个整数 n, m，表示东西向道路的数量和南北向道路的数量。
第二行包含 n − 1 个整数 h 1 , h 2 , ···, h n−1 。
第三行包含 m − 1 个整数 w 1 , w 2 , ···, w m−1 。
接下来 n 行，每行 m 个整数，描述每个路口南北向绿灯的时间，其中的第i 行第 j 列表示 g ij 。
接下来 n 行，每行 m 个整数，描述每个路口东西向绿灯的时间，其中的第i 行第 j 列表示 r ij 。
接下来一行包含四个整数 x 1 , y 1 , x 2 , y 2 ，表示小蓝家的位置在路口 (x 1 ,y 1 )到路口 (x 2 ,y 2 ) 之间的道路中点的右侧。
接下来一行包含一个整数 q，表示订单数量。
接下来 q 行，每行描述一个订单，其中第 i 行包含八个整数 x i1 , y i1 , x i2 , y i2 ,x i3 , y i3 , x i4 , y i4 ，表示第 i 个订单的起点为路口 (x i1 ,y i1 ) 到路口 (x i2 ,y i2 ) 之间的道路中点的右侧，第 i 个订单的终点为路口 (x i3 ,y i3 ) 到路口 (x i4 ,y i4 ) 之间的道路中点的右侧。
【输出格式】
输出一个实数，表示小蓝完成所有订单最后回到家的最早时刻。四舍五入
保留一位小数。
【样例输入】
2 3
200
100 400
10 20 10
20 40 30
20 20 20
20 20 20
2 1 1 1
1
2 2 1 2 1 2 1 3
【样例输出】
1620.0
【样例说明】
小蓝有一个订单，他的行车路线如下图所示。其中 H 表示他家的位置，S
表示订单的起点，T 表示订单的终点。小明在最后回家时要在直行的红绿灯路
口等绿灯，等待时间为 20。

题解
太长了不想看

试题 J: 质数行者

【问题描述】
小蓝在玩一个叫质数行者的游戏。
游戏在一个 n×m×w 的立体方格图上进行，从北到南依次标号为第 1 行到
第 n 行，从西到东依次标号为第 1 列到第 m 列，从下到上依次标号为第 1 层到第 w 层。
小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w层。每一步，他可以向东走质数格、向南走质数格或者向上走质数格。每走到一个位置，小蓝的角色要稍作停留。
在游戏中有两个陷阱，分别为第 r 1 行第 c 1 列第 h 1 层和第 r 2 行第 c 2 列第h2 层。这两个陷阱的位置可以跨过，但不能停留。也就是说，小蓝不能控制角色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。
小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。所谓两个走法不同，是指小蓝稍作停留的位置集合不同。
请帮小蓝计算一下，他总共有多少种不同的走法。
提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。
【输入格式】
输入第一行包含两个整数 n, m, w，表示方格图的大小。
第二行包含 6 个整数，r 1 , c 1 , h 1 , r 2 , c 2 , h 2 ，表示陷阱的位置。
【输出格式】
输出一行，包含一个整数，表示走法的数量。答案可能非常大，请输出答
案除以 1000000007 的余数。
【样例输入】
5 6 1
3 4 1 1 2 1
【样例输出】
11
【样例说明】
用 (r,c,h) 表示第 r 行第 c 列第 h 层，可能的走法有以下几种：

(1,1,1) − (1,3,1) − (1,6,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (1,3,1) − (3,3,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (1,3,1) − (3,3,1) − (5,3,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (3,3,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (3,3,1) − (5,3,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (5,1,1) − (5,3,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (5,1,1) − (5,4,1) − (5,6,1)。
(1,1,1) − (1,4,1) − (1,6,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (1,6,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (3,6,1) − (5,6,1)。
(1,1,1) − (3,1,1) − (5,1,1) − (5,6,1)。
【评测用例规模与约定】
对于 30% 的评测用例 1 ≤ n,m,w ≤ 50。
对于 60% 的评测用例 1 ≤ n,m,w ≤ 300。
对于所有评测用例，1 ≤ n,m,w ≤ 1000，1 ≤ r 1 ,r 2 ≤ n, 1 ≤ c 1 ,c 2 ≤ m,
1 ≤ h 1 ,h 2 ≤ w，陷阱不在起点或终点，两个陷阱不同。

题解
DAG上的动态规划，可以看我之前写的博客，都是这个类型的题，但这并不是正解三维开不了1000，我觉得正解应该是dp加压缩但是我实在想不出来只能骗分了
注意：1不是素数，我因为这个浪费了不少时间。。。。低级错误才是最致命的

嵌套矩阵，DAG上的动态规划加记忆化数组
https://blog.csdn.net/m0_52103105/article/details/116136629

硬币问题
https://blog.csdn.net/m0_52103105/article/details/116210488

巴比伦塔
https://blog.csdn.net/m0_52103105/article/details/116263306

#include <stdio.h>
#include <stdlib.h>
#define N 302
#define MOOD 1000000007
//所犯错误把1当成素数
int m,n,w;
int r1,c1,h1,r2,c2,h2;
int d[N][N][N];
int perm[N]={0,0};
int flag[N];
int count=0;

int dp(int x,int y,int z)
{
    if(x==n && y==m && z==w)
        return 1;
    if(x>n || y>m ||z>w)
        return 0;

    if(d[x][y][z]!=-1)
        return d[x][y][z];
    int ans=0;
    for(int i=0;i<count;i++)
    {
        ans=(ans+dp(x+perm[i],y,z))%MOOD;
        ans=(ans+dp(x,y+perm[i],z))%MOOD;
        ans=(ans+dp(x,y,z+perm[i]))%MOOD;
    }

    return d[x][y][z]=ans;
}

int main()
{
    int i,j;

    //普通筛选法求素数，素数的倍数不是素数
    for(i=2;i<N;i++)
    {
        if(!flag[i])
      {
        perm[count++]=i;
        for(j=i*2;j<=N;j+=i)
         flag[j]=1;
      }
    }

    /*printf("count%d\n",count);
    for(i=0;i<count;i++)
        printf("%d\n",perm[i]);
        */

    memset(d,-1,sizeof(d));

    scanf("%d%d%d",&n,&m,&w);
    scanf("%d%d%d%d%d%d",&r1,&c1,&h1,&r2,&c2,&h2);
    d[r1][c1][h1]=d[r2][c2][h2]=0;


    printf("%d\n",dp(1,1,1));

    return 0;
}

原文链接:https://blog.csdn.net/m0_52103105/article/details/117233652