備戰藍橋杯——算法訓練之過河馬

xorpay 發布于2021-11-15 11:38 / 3137人閱讀

摘要：而眾所周知，馬是要走日子格的。輸出格式輸出有一行，一個數表示走法數。那為了防止爆掉，我們每加完一條路的總步數之后就取一遍余。題目解法思路如上述，但是這里有一個我之前從來沒有注意過的問題，導致我一直只有分。三題解四題目鏈接過河馬

算法訓練之過河馬

一、題目
二、思路
三、題解
四、題目鏈接

一、題目

資源限制
時間限制：1.0s 內存限制：256.0MB
問題描述
　　在那個過河卒逃過了馬的控制以超級超級多的走法走到了終點之后，這匹馬表示它不開心了……
　　于是，終于有一天，它也過河了！
　　由于過河馬積累了許多的怨念，所以這次它過了河之后，再也沒有什么東西可以限制它，它可以自由自在的在棋盤上馳騁。一開始，它是在一個n行m列棋盤的左下角（1,1）的位置，它想要走到終點右上角（n，m）的位置。而眾所周知，馬是要走日子格的。可是這匹馬在積累了這么多怨念之后，它再也不想走回頭路——也就是說，它只會朝向上的方向跳，不會朝向下的方向跳。
　　那么，這匹馬它也想知道，它想從起點跳到終點，一共有多少種走法呢？
輸入格式
　　第一行兩個數n，m，表示一個n行m列的棋盤，馬最初是在左下角（1,1）的位置，終點在右上角（n，m）的位置。
輸出格式
　　輸出有一行，一個數表示走法數。由于答案可能很大，所以輸出答案除以1000000007所得的余數即可。
樣例輸入
4 4
樣例輸出
2
數據規模和約定
　　n<=100,m<=100

二、思路

如圖，我們理一下思路，從左下角跳到右上角，用一個二維數組來存儲跳到每個點的總步數。我們來逆推，（其中2,3和3,2只可能是從1,1跳來的。），以黃點為例，他可能是A、B、C、D任意一點跳來的。然后，要判斷一下A、B、C、D在不在棋盤內。
然后題目說答案可能很大，輸出答案除以1000000007所得的余數即可。那為了防止爆掉，我們每加完一條路的總步數之后就取一遍余。
題目解法思路如上述，但是這里有一個我之前從來沒有注意過的問題，導致我一直只有90分。那就是我一直習慣于在main函數內聲明變量。。。
具體原因是在這篇博客里看的，詳情點擊傳送門。
其實就是說在main函數外面開一個數組，他的內存分配在數據區里；如果在main函數內部開數組，內存分配在棧區內。一般來說棧區的內存是比較小的，所以平常開一些小一點的數組是沒問題的；但如果題目要求的數組比較大，那就會出現爆出的問題。

三、題解

#includeusing namespace std;int n,m;int cb[105][105];int main(){	cin>>n>>m;	cb[2][3] = cb[3][2] = 1;	for(int i = 1;i <= n;i++)	{				for(int j = 1;j <= m;j++)		{			if(i-1 >=1 && j-2 >= 1)			{				cb[i][j] += cb[i-1][j-2];				cb[i][j] %= 1000000007;			} 			if(i-2 >=1 && j-1 >= 1)			{				cb[i][j] += cb[i-2][j-1];				cb[i][j] %= 1000000007;			} 			if(i-2 >=1 && j+1 <= m)			{				cb[i][j] += cb[i-2][j+1];				cb[i][j] %= 1000000007;				} 			if(i-1 >=1 && j+2 <= m)			{				cb[i][j] += cb[i-1][j+2];				cb[i][j] %= 1000000007;				} 		}	}	cout<<cb[n][m];	return 0;}

四、題目鏈接

ALGO-981 過河馬

GPU云服務器云服務器藍橋杯屆藍橋杯藍橋杯省賽 Java?藍橋杯

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123334.html

藍橋杯算法訓練審美課 java

摘要：問題描述審美的歷程課上有位學生，帥老師展示了幅畫，其中有些是梵高的作品，另外的都出自五歲小朋友之手。輸入格式第一行兩個數和，表示學生數和圖畫數接下來是一個的矩陣如果，表示學生覺得第幅畫是小朋友畫的如果，表示學生覺得第幅畫是梵高畫的。問題描述　　《審美的歷程》課上有n位學生，帥老師展示了m幅畫，其中有些是梵高的作品，另外的都出自五歲小朋友之手。老師請同學們分辨哪些畫的作者是梵高，但是老...

worldligang 2019-08-16 15:36 評論0 收藏0
2021藍橋杯你值得擁有

摘要：文章目錄一你應該知道的藍橋杯含金量獲獎率高不高支持哪些編程語言二川川帶你體驗藍橋杯省賽藍橋杯藍橋杯三個人感受一你應該知道的藍橋杯如果你是計算機相關專業，你不知藍橋杯就過不去了，我們來看看藍橋杯如何，不知道更應該來了解下了。 ...

fanux 2021-11-18 10:02 評論0 收藏0
2018第九屆藍橋杯Java b組總結

摘要：現在小明想統計有哪些帖子曾經是熱帖。如果一個帖子曾在任意一個長度為的時間段內收到不少于個贊，小明就認為這個帖子曾是熱帖。以下行列代表一張海域照片。照片保證第行第列第行第列的像素都是海洋。 2018年4月1日愚人節，我第一次參加了有關計算機算法類比賽藍橋杯，這篇算是經驗總結和題目回顧，水平有限，有不妥之處歡迎留言批評指正，也可以加QQ891465170交流~下面進入正題：第一題：第幾...

codecook 2019-08-15 15:11 評論0 收藏0
【兩萬字精編~建議抱走】藍橋杯算法競賽系列第0章——藍橋必考點及標準模板庫STL（下）

摘要：時間復雜度為，和分別是和的長度示例如下輸出輸出把從號位開始長度為的子串替換為上把的迭代器范圍的子串替換為示例如下歡迎回到：遇見藍橋遇見你，不負代碼不負卿！目錄【補充】：常用頭文件及庫函數 1.#include sscanf() 和 sprintf() 2.#include 3.#...

sixleaves 2021-11-22 09:34 評論0 收藏0
藍橋杯-烏托邦樹

摘要：傳送門題目描述實現一個算法得到烏托邦樹的高度介紹如下烏托邦樹每年經歷個生長周期。每年夏天，它的高度都會增加米。對于一顆在春天開始時種下的高米的樹，問經過指定周期后，樹的高度為多少。輸入描述輸入一個數字，表示指定周期。 ...

caiyongji 2021-11-22 09:34 評論0 收藏0