一堆遞推題 - BuringStraw

一堆遞推題#

—— 來自義冢 OJ 和義冢 OJ 的 contests

P1367【訓練題】爬樓梯 [2]#

描述#

　　何老師爬樓梯，他可以每步上 1 、2 或 3 級，輸入樓梯的級數，求不同的走法數。例如：樓梯一共有 3 級，他可以每步都走一级，或者第一步走一级，第二步走兩級，也可以第一步走兩級，第二步走一级，還有就是第一步就上 3 級，所以一共 4 種方法。

　　但不幸的是，樓梯上有 K 級壞了，何老師不能踩在這些樓梯上，現在給出樓梯的級數 N 和壞了的 K 級樓梯，請你計算他上樓梯的方法總數。

輸入#

　　第一行：N、K。　　第二行：K 個整數 h [i]，表示壞了的樓梯的級數 (1<=h [i]<=N)。

輸出#

　　不同的走法數，這個數字可能很巨大，所以輸出最後答案 mod 1234567。

輸入範例 1#

5 2
2 4

輸出範例 1#

提示#

　　1 <= N <= 1000 0 <= k < N

思路#

把所有有坑的樓梯的方案數在遞推過程中設為 0

注意有可能最前面幾級也有坑

所以用 0 作為邊界

中途檢查是否越界

#include<cstdio>
#include<iostream>
using namespace std;

const int MAXN=1005;

int f[MAXN];
bool h[MAXN];

int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=k;++i){
		int t;
		cin>>t;
		h[t]=1;
	}
	f[0]=1;
//	f[1]=1;
	for(int i=1;i<=n;++i){
		if(h[i]){
			f[i]=0;
			continue;
		}
		else if(!f[i]){
			if(i-1>=0)f[i]+=f[i-1];
			if(i-2>=0)f[i]+=f[i-2];
			if(i-3>=0)f[i]+=f[i-3];
			f[i]%=1234567;
		}
	}
	cout<<f[n]<<endl;
	return 0;
}

鋪瓷磚#

描述#

用紅色的 1×1 和黑色的 2×2 兩種規格的瓷磚不重疊地鋪滿 n×3 的路面，求出有多少種不同的鋪設方案。

輸入#

一行一個整數 n，0<n<1000。

輸出#

一行一個整數，為鋪設方案的數量模 12345 的結果。

輸入範例 1#

輸出範例 1#

思路#

從之前一格開始填有一種方法

從之前兩格開始填有 3 種方法

但是全用 1x1 包含在從之前一格開始填裡面

所以f[i]=f[i-1]+f[i-2]*2

f[0]=f[1]=1;

#include<cstdio>
#include<iostream>
using namespace std;

int f[1005];

int main(){
	int n;
	cin>>n;
	f[0]=f[1]=1;
	//f[2]=3;
	for(int i=2;i<=n;++i){
		f[i]=f[i-1]+f[i-2]*2;
		f[i]%=12345;
	}
	cout<<f[n]<<endl;
	return 0;
}

城市路徑#

描述#

地圖上有 n 個城市，一隻奶牛要從 1 號城市開始依次經過這些城市，最終到達 n 號城市。但是這隻奶牛覺得這樣太無聊了，所以它決定跳過其中的一個城市 (但是不能跳過 1 號和 n 號城市)，使得它從 1 號城市開始，到達 n 號城市所經過的總距離最小。假設每一個城市 i 都有一個坐標 (x i ，y i )，從 (x 1 ，y 1 ) 的城市 1 到 (x 2 ，y 2 ) 的城市 2 之間的距離為 | x 1 -x 2 | + | y 1 -y 2 |。

輸入#

第 1 行 1 個正整數 n，表示城市個數。接下來的 n 行，每行 2 個數 x i 和 y i ，表示城市 i 的坐標。

輸出#

一行一個數，使得它從 1 號城市開始，跳過某一個城市，到達 n 號城市所經過的最小總距離。

輸入範例 1#

輸出範例 1#

提示#

【樣例說明】跳過 2 號城市。【數據規模】對於 40% 的數據滿足：n≤1000。對於 100% 的數據滿足：3≤n≤100000，-1000≤x i ，y i ≤1000。

思路#

有的題，表面上是一道遞推題，實際上可以用模擬做
? —— 魯迅

這是貪心

? ——~~hqx~~perisino 大佬

比較每一個點刪除之後對路程的影響，選出刪除之後最短的

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;

const int MAXN=1e5+5;

struct zb{
	int x,y;
} city[MAXN];
int n;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&city[i].x,&city[i].y);
	}
	int maxs=0,maxi=0;
	int he=0;
	
	for(int i=2;i<n;++i){
		int tmp=
			abs(city[i+1].x-city[i].x)+abs(city[i+1].y-city[i].y)
			+abs(city[i-1].x-city[i].x)+abs(city[i-1].y-city[i].y);
		tmp-=abs(city[i+1].x-city[i-1].x)+abs(city[i+1].y-city[i-1].y);
		if(tmp>maxs){
			maxi=i;
			maxs=tmp;
		}
		he+=abs(city[i-1].x-city[i].x)+abs(city[i-1].y-city[i].y);
	}
	he+=abs(city[n-1].x-city[n].x)+abs(city[n-1].y-city[n].y);
	he-=maxs;
	printf("%d\n",he);
	return 0;
}

彩帶#

描述#

一中 90 週年校慶，小林準備用一些白色、藍色和紅色的彩帶來裝飾學校超市的櫥窗，他希望滿足以下兩個條件：

(1) 相同顏色的彩帶不能放在相鄰的位置；

(2) 一條藍色的彩帶必須放在一條白色的彩帶和一條紅色的彩帶中間。

現在，他想知道滿足要求的放置彩帶的方案數有多少種。

例如，如圖 9.4-1 所示為櫥窗寬度 n=3 的所有放置方案，共 4 種。

輸入#

一行一個整數 n，表示櫥窗寬度 (或者說彩帶數目)。

輸出#

一行一個整數，表示裝飾櫥窗的彩帶放置方案數。

輸入範例 1#

輸出範例 1#

提示#

對 30% 的數據滿足：1≤n≤15。對 100% 的數據滿足：1≤n≤45。

思路#

此題感謝perisino 大佬的指點

f[i]為彩帶數目為 i 時的方案數

注意最後一條不能是藍色

當

第(i-1)條為紅色或白色：因為最後一條不能是藍色，所以有一種情況
第(i-1)條為藍色：第i條與第(i-2)條顏色相反，有一種情況
~~大佬之前把第二個(i-1)寫成了(i-2)我差點沒看懂~~

所以f[i]=f[i-1]+f[i-2]

#include<cstdio>
#include<iostream>
using namespace std;

const int MAXN=50;

int f[MAXN];
int n;

int main(){
	f[1]=2;
	f[2]=2;
	cin>>n;
	for(int i=3;i<=n;++i){
		f[i]=f[i-1]+f[i-2];
	}
	cout<<f[n]<<endl;
	return 0;
}

斐波那契前 N 項和#

描述#

求斐波那契數列前 n 項和取模 m

輸入#

一行兩個整數 n m

輸出#

輸出前 n 項和取模 m

輸入範例 1#

5 1000

輸出範例 1#

提示#

1<=n<=2*10^91<=m<=1000000010

思路#

是前 n 項和不是第 n 項

數據範圍非常大，用矩陣

~~矩陣快速幂都忘了，丟人~~

矩陣 A：1x3

? 內容：f(i-1),f(i-2),g(i-1)

? 其中f(i)表示斐波那契數列的第i項，g(i)表示前i項的和

矩陣 B：3x3

? 內容：

		1 1 1
		1 0 1
		0 0 1

則 $f (n)=A\cdot B^{(n-2)}$

要用 long long 要用 long long 要用 long long

#include<cstdio>
#include<cstring>
#include<iostream>
#define LL long long
using namespace std;

const LL MAXN=5;

LL n,m;

struct juzhen{
	private:
		LL v[MAXN][MAXN];
		LL h,l;
		
		void prLL(void){
			for(LL i=1;i<=h;++i){
				for(LL j=1;j<=l;++j){
					cout<<v[i][j]<<' ';
				}
				cout<<'\n';
			}
		}
	
	public:
		juzhen(LL he,LL le){
			memset(v,0,sizeof(v));
			h=he,l=le;
		}
		
		friend juzhen operator *(juzhen a,juzhen b){
			juzhen c(a.h,b.l);
			for(LL i=1;i<=a.h;++i){
				for(LL j=1;j<=b.l;++j){
					 for(LL k=1;k<=a.l;++k){
					 	c.v[i][j]+=(a.v[i][k]*b.v[k][j]%m);
					 	c.v[i][j]%=m;
					 }
				}
			}
			return c;
		}
		
		friend juzhen operator ^(juzhen a,LL b){
			
			juzhen ret(a.h,a.l),sum=a;
			for(LL i=1;i<=a.h;++i){
				ret.v[i][i]=1;
			}
			while(b){
				if(b&1){
					ret=ret*sum;
				}
				sum=sum*sum;
				b>>=1;
			}
//			ret.prLL();
			return ret;
		}
		
		void writeV(LL x,LL y,LL val) {
			v[x][y]=val;
		}
		
		LL callV(LL x,LL y){
			return v[x][y];
		}
};

	juzhen a(1,3),b(3,3);
int main(void){
	cin>>n>>m;
	a.writeV(1,1,1);
	a.writeV(1,2,1);
	a.writeV(1,3,2);
	
	b.writeV(1,1,1);
	b.writeV(1,2,1);
	b.writeV(1,3,1);
	b.writeV(2,1,1);
	b.writeV(2,2,0);
	b.writeV(2,3,1);
	b.writeV(3,1,0);
	b.writeV(3,2,0);
	b.writeV(3,3,1);
	
	juzhen c=a*(b^(n-2));
	cout<<c.callV(1,3)<<endl;
	
	
	return 0;
}

偶數個 3#

描述#

編程求出所有的 n 位數中，有多少個數中有偶數個數字 3。

輸入#

一行一個正整數 n，0<n<1000。

輸出#

一行一個正整數，表示 n 位數中有多少個數有偶數個 3。最後答案為 12345 取模

輸入範例 1#

輸出範例 1#

思路#

好難一道題！

看著大佬打完表找出規律 AC 了，我的眼眶也濕潤了。

然後我也 dfs 打了個表

然而找不到半分規律

最後看了大佬的規律和題解。。。

~~發現這規律可能我這輩子都找不出來。。~~

~~可能這就是我和大佬的差距吧~~

這裡的大佬指的是 (wyx 大佬)[https://wuyanxi.top] 和 (perisino 大佬)[https://cnblogs.com/perisino]

忽略上面這部分

主要解法就是用f[i][0]表示i位數中有偶數個3的數量

? 用f[i][1]表示i位數中有奇數個3的數量

若一個(i-1)位數中有偶數個3，要使i位數有偶數個3

則可以在其後追加1,2,4,5,6,7,8,9,0

若有奇數個，則可追加一個3

可得

f[i][0]=f[i-1][0]*9+f[i-1][1];
f[i][1]=f[i-1][1]*9+f[i-1][0];

回文拆分#

描述#

對一個正整數 K，求出 K 的所有拆分，並統計輸出其中回文數列的個數。所謂回文數列是指該數列中的所有數字，從左向右或從右向左看都相同。例如：

K=4 時，有如下的拆分：

4=1+1+1+1 （回文數列 1）

=1+1+2

=1+2+1 （回文數列 2）

=2+1+1

=2+2 （回文數列 3）

=1+3

=3+1

回文數列共有 3 個

輸入#

一行，一個正整數 K，1<=K<=26

輸出#

一個正整數，表示回文數列個數

輸入範例 1#

輸出範例 1#

思路#

~~有的題在遞推的 contest 裡，但它實際上是道遞歸題~~

? ~~—— 魯迅~~

寫了個 dfs 想看看能過幾個點，沒想到 AC 了。

#include<cstdio>
#include<iostream>
using namespace std;

int f[30];

void dfs(int step,int tot);
int k,cnt;

int main(){
	cin>>k;
	dfs(1,0);
	cout<<cnt<<endl;
	return 0;
}

void dfs(int step,int tot){
	if(tot>k)return;
	if(tot==k){
		bool flag=1;
		for(int i=1;i<=(step-1)/2;++i){
			if(f[i]!=f[step-i]){
				flag=0;
				break;
			}
		}
		if(flag){
			++cnt;
//			for(int i=1;i<step;++i){
//				cout<<f[i]<<' ';
//			}
//			cout<<'\n';
		}
	}
	for(int i=1;i<=k-tot&&i<k;++i){
		f[step]=i;
		dfs(step+1,tot+i);
	}
}

看到自己是 400+ms，而其他人都是 2,3ms，感覺很尷尬

就打了個表

for(int i=1;i<=26;++i){
    cnt=0;
    memset(f,0,sizeof(f));
    k=i;
    dfs(1,0);
    cout<<i<<' '<<cnt<<endl;
}

得到

打表結果

這不是 $(2^n-1)$ 嗎。。。

所以又 AC 一遍

#include<cstdio>
#include<iostream>
using namespace std;

int qkpow(int x,int y);

int main(void){
	int k;
	cin>>k;
	cout<<qkpow(2,k/2)-1<<endl;
	return 0;
}

int qkpow(int x,int y){
	if(y==0){
		return 1;
	}
	int ret=1,sum=x;
	while(y){
		if(y&1){
			ret*=sum;
		}
		sum*=sum;
		y>>=1;
	}
	return ret;
}

恩~~