2021-7-13紀中【普及組】模拟賽C組

紀中【普及組】模拟賽C組目錄

• 前言
• T1：遞推1
• • 題目概述
  • 思路
  • 代碼
• T2：遞推2
• • 題目概述
  • 思路
  • 代碼
• T3：遞推3
• • 題目概述
  • 思路
  • 代碼
• 溫馨提示
• T4：遞推4
• • 題目概述
  • 思路
  • 代碼
• T5：遞推5
• • 題目概述
  • 思路
  • 代碼
  • • 60分的代碼
    • • 60分代碼分析
    • 100分的代碼
    • • 100分的代碼分析
• 總結

前言

光陰似箭，日月如梭。大家好，我盛藝承又回來了。今天給大家講一講我們紀中的DP題目綜合。

T1：遞推1

題目概述

用1 x 1和2 x 2的磁磚不重疊地鋪滿N x 3的地闆，共有多少種方案？

輸入

一個數字N<=1000

輸出

所求的答案mod 12345.

樣例輸入

2

樣例輸出

3

思路

這一題就是模闆題。直接畫圖畫出方案數然後推出遞推式就行了。

由于這一題很水，是以我直接就給代碼了。不細講（是以這就是你偷懶的理由？）。

代碼

#include<bits/stdc++.h>
using namespace std;
long long n,i,f[1001]={0,1,3};
int main(){
	freopen("problem1.in","r",stdin);
	freopen("problem1.out","w",stdout);
	cin>>n;
	for(i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2]*2)%12345;
	cout<<f[n]%12345;
}
           

T2：遞推2

題目概述

從原點出發，一步隻能向右走、向上走或向左走。恰好走N步且不經過已走的點共有多少種走法？

輸入

一個數字N<=1000

輸出

一個數表示所求答案mod 12345.

樣例輸入

2

樣例輸出

7

思路

這也是一道裸體。隻用枚舉一下（也是畫圖）就行了。最後推出遞推公式（偷懶的理由又來了！！！）。

代碼

#include<bits/stdc++.h>
using namespace std;
long long n,i,f[1001]={1,3};
int main(){
	freopen("problem2.in","r",stdin);
	freopen("problem2.out","w",stdout);
	cin>>n;
	for(i=2;i<=n;i++) f[i]=f[i-1]*2+f[i-2],f[i]%=12345;
	cout<<f[n]%12345;
}
           

T3：遞推3

題目概述

在所有的N位數中，有多少個數中有偶數個數字3？

輸入

一個整數N<=1000

輸出

輸出一個數表示答案mod 12345.

樣例輸入

2

樣例輸出

73

思路

此題也是非常的簡單啊，是以。。。。。。（部落客的兄弟：是以你又想偷懶是不是？給爺寫！）我隻好把思路寫出來。

這一題有一點不一樣，他要用到兩個數組。然後還是推出遞推公式。。。。。。

好的，思路我們就講到這裡。我們來看看代碼ヽ(￣▽￣)و

代碼

#include<bits/stdc++.h>
using namespace std;
int n,s1[1005]={0,9},s2[1005]={0,1};
int main(){
	freopen("problem3.in","r",stdin);
	freopen("problem3.out","w",stdout);
	cin>>n;
	for(int i=2;i<=n;i++){
		s1[i]=(s1[i-1]*9+s2[i-1])%12345;
		s2[i]=(s1[i-1]+s2[i-1]*9)%12345;
	}
	cout<<(s1[n]-s1[n-1]+12345)%12345;
}
           

溫馨提示

各位，我今天馬上開始更新！！！

T4：遞推4

題目概述

圓周上有N個點。連接配接任意多條（可能是0條）不相交的弦（共用端點也算相交）共有多少種方案？

輸入

讀入一個數N。1<=N<=1000。

輸出

輸出這個答案mod 12345的值。

樣例輸入

4

樣例輸出

9

思路

這一題推就完了。也沒什麼思路，隻要把遞推公式推出來就行了。

代碼

#include<bits/stdc++.h>
using namespace std;
int n,f[1005]={1,1},k,i,j;
int main(){
	freopen("problem4.in","r",stdin);
	freopen("problem4.out","w",stdout);
	cin>>n;
	for(i=2;i<=n;i++){
		f[i]=f[i-1];
		k=0;
		for(j=i-2;j>=0;j--) f[i]+=f[j]*f[k++],f[i]%=12345;
	}
	cout<<f[n];
}
           

T5：遞推5

題目概述

在網格中取一個N x 1的矩形，并把它當作一個無向圖。這個圖有2(N+1)個頂點，有3(N-1)+4條邊。這個圖有多少個生成樹？答案 mod 12345 後輸出。

輸入

樣例輸入：1

輸出

樣例輸出：4

答案 mod 12345 後輸出。

樣例輸入

1

樣例輸出

4

思路

這一題也是遞推。不過在推出遞推公式的時候，要把他+12345。這樣就相當于給他弄了一個絕對值。就讓他不會變成負數。

為什麼呢？因為如果你得到的答案是負數，那麼+12345，就變成了正數。如果你得到的答案是正數，那麼後面的%12345也可以讓+12345被%掉。

代碼

先給大家看看我60分的代碼

60分的代碼

#include<bits/stdc++.h>
using namespace std;
int f[10005]={1,4},i,n;
int main(){
	freopen("problem5.in","r",stdin);
	freopen("problem5.out","w",stdout);
	cin>>n;
	for(i=2;i<=n;i++) f[i]=(f[i-1]*4-f[i-2])%12345;
	cout<<(f[n])%12345;
}
           

60分代碼分析

這個代碼哪裡錯了呢？為什麼隻有60分呢？大家如果仔細看的話，就會發現我在下圖畫圈的地方，沒有+12345。是以啊各位，不加上12345，很吃虧的啊！

100分的代碼

#include<bits/stdc++.h>
using namespace std;
int f[10005]={1,4},i,n;
int main(){
	freopen("problem5.in","r",stdin);
	freopen("problem5.out","w",stdout);
	cin>>n;
	for(i=2;i<=n;i++) f[i]=(f[i-1]*4-f[i-2]+12345)%12345;
	cout<<(f[n])%12345;
}
           

100分的代碼分析

大家肯定也看到了。我100分的代碼隻是少加了一個12345，就錯了。是以，一個12345頂40分！

總結

這次的題目不算太難。主要是我不夠認真，導緻有許多我意料之外的錯誤。下一次我要更努力才行！