文章目錄

• • 試題 A: 美麗的 2
  • 試題 B: 擴散
  • 試題 C: 階乘約數
  • 試題 D: 本質上升序列
  • 試題 E: 玩具蛇
  • 試題 F: 皮亞諾曲線距離
  • 試題 G: 游園安排
  • 試題 H: 答疑
  • 試題 I: 出租車
  • 試題 J: 質數行者

試題 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;}elsej++;}}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;elsedp[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 1000000typedef 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<<28long 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; }

總結

以上是生活随笔為你收集整理的2020第十一届蓝桥杯C/C++国赛B组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。