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分！

总结

这次的题目不算太难。主要是我不够认真，导致有许多我意料之外的错误。下一次我要更努力才行！