国庆普及模拟赛-5

题目链接：

file:///C:/Users/Administrator/Desktop/%E4%B8%8B%E5%8F%91%E6%96%87%E4%BB%B61005/20241005.pdf

T1：

题目分析：不需要进行模拟，想要获得分数最大化，只需要将大的数据相加，再减去小的数据。 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n,sum1,sum2,k;
signed  main() {
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);

	cin>>n;//n个数
	for(int i=1; i<=n; i++)cin>>a[i];//读入这n个数
	sort(a+1,a+n+1);//排序，小的靠左，大的靠右
	(n%2==0)?(k=n/2):(k=(n-1)/2);//判断一下n是否是单数，好确定加上的和减去的数的个数
	for(int i=1;i<=k;i++)sum1+=a[i];//sum1是小的数相加的和
	for(int i=k+1;i<=n;i++)sum2+=a[i];//sum2是大的数相加的合
	int sum3=sum2-sum1;//按照题目要求相减
	cout<<sum3;
	return 0;
}

T2

题目分析：（题目内容和标题完全没关系）

最大公因数就是那几个因子相乘的乘积，最小公倍数一样。 

#include<bits/stdc++.h>
using namespace std;
const int MOS=1e9+7,N=1e6+5;
int n,m,v,maxn,t[N];
long long cnt=1;
int main() {
	freopen("gcm.in","r",stdin);
	freopen("gcm.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>v;
		t[v]--;//因为最小公倍数一定包含最大公因数，所以先将最大公因数的因子减去，再把最小公倍数的因子加上，数组里面被标记的就是有这个因子的。
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>v;
		t[v]++;
		maxn=max(maxn,v);//最大的因子一定包含在最小公倍数的因子里
	}
	for(int i=1;i<=maxn;i++){
		if(t[i]>0){//如果有这个因子的就把它×2
			cnt=(cnt*2)%MOS;//随时取余
		}
		
	}
	cout<<cnt;
	return 0;
}

T3：原本想法是DFS，考试的时候全WA了。后面AC的解法是用DP，

dp[i][j][0/1]记录是从上面还是左面来的。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],dp[N][N][2],n,m;
long long read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

int main() {
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	n=read();
	m=read();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			a[i][j]=read();
	dp[1][0][0]=dp[1][0][1]=dp[0][1][0]=dp[0][1][1]=a[1][1];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			dp[i][j][0]=max((dp[i][j-1][0]+a[i-1][j]),dp[i][j-1][1])+a[i+1][j]+a[i][j+1];
			dp[i][j][1]=max(dp[i-1][j][0],(dp[i-1][j][1]+a[i][j-1]))+a[i][j+1]+a[i+1][j];
		}
	cout<<dp[n][m][0];//严格来说要取一个max，但是不取能AC，如果是dp[n][m][1]只能拿50分+
	return 0;
}

T4：

打表打错了【哭死】

#include<bits/stdc++.h>
using namespace std;
int x,vis[1000001],a=1,b=1;
long long read() {//用个快读优化一点
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main() {
	freopen("fibonacci.in","r",stdin);
	freopen("fibonacci.out","w",stdout);
	x=read();
	vis[1]=1;
	for(int i=1;i<=1e7; i++) {//数据不大，1e7直接算斐波那契数列
		int c=a+b;
		c%=x;
		a=b;
		b=c;
		vis[b]=1;
		if(a%x==0&&b%x==0) break;//如果这个斐波那契数列的数是x的倍数，就说明x的倍数会是斐波那契书
	}
	int ans=0;
	for(int i=1;i<x;i++) {//
		if(!vis[i%x])ans++;
	}
	printf("%d",ans);
	return 0;
}

总结：

本次考试T1 没扣分，后面的T4没想到思路，T2和正解思路有点偏差。