CSP-J2022山东补赛题解

1.植树节

原题：https://www.luogu.com.cn/problem/U285015

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+255;
int a[N],n,x,y,maxb=-1e9,ans=-1e9;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		a[x]++;a[y+1]--;
		maxb=max(maxb,y);
	}
	for(int i=0;i<=maxb;i++)a[i]+=a[i-1];
	for(int i=0;i<=maxb;i++)ans=max(ans,a[i]);
	cout<<ans;
	return 0;
}

解题思路：

差分模板，计算出最大的b，求差分数组，取最大值即可

2.宴会

原题：https://www.luogu.com.cn/problem/U285016

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+255;
int T,n,x[N],t[N],minn=1e9,maxn=-1e9;
int main(){
	cin>>T;
	while(T--){
		maxn=-1e9;minn=1e9;
		cin>>n;
		for(int i=1;i<=n;i++)cin>>x[i];
		for(int i=1;i<=n;i++)cin>>t[i],maxn=max(maxn,x[i]+t[i]),minn=min(minn,x[i]-t[i]);
		cout<<(minn+maxn)/2.0<<'\n';
	}
	return 0;
}

解题思路：

枚举每个人向左走的最小值，向右走的最大值，求平均数就是答案

3.部署

原题：https://www.luogu.com.cn/problem/U285018

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+255;
int n,m,q,x,y,a[N],b[N],c[N],head[N],cnt=-1;
struct edg{
	int to,next;
}e[4*N];
void add(int x,int y){
	e[++cnt]=(edg){y,head[x]};
	head[x]=cnt;
}
void dfs(int x,int y){
	a[x]+=b[x];
	a[y]+=c[x];
	a[x]+=c[x];
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].to;
		if(v==y)continue;
		a[v]+=c[x];
		b[v]+=b[x];
		dfs(v,x);
	}
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	cin>>m;
	for(int i=1,p;i<=m;i++){
		cin>>p>>x>>y;
		if(p==1)b[x]+=y;
		else c[x]+=y;
	}
	dfs(1,0);
	cin>>q;
	while(q--){
		cin>>x;
		cout<<a[x]<<'\n';
	}
	return 0;
}

解题思路：

进行预处理，统计两种操作的值，用一个深搜，输出答案就行了

4.吟诗

原题：https://www.luogu.com.cn/problem/U285023

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 998244353,N = 75;
ll move(ll a,ll b){return ((a%MOD)*(b%MOD))%MOD;}
ll add(ll a,ll b){return ((a%MOD)+(b%MOD))%MOD;}
ll n,x,y,z,d,sum,ans=1,f[N][1<<18];
int main(){
	cin>>n>>x>>y>>z;
	d=(1<<x+y+z-1);
	d|=(1<<y+z-1);
	d|=(1<<z-1);
	sum=(1<<x+y+z)-1;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		ans=move(ans,10);
		for(int j=0;j<sum;j++){
			if(!f[i-1][j])continue;
			for(int k=1;k<=10;k++){
				ll num=(j<<k)|(1<<k-1);
				num&=sum;
				if((num&d)!=d)f[i][num]=add(f[i][num],f[i-1][j]);
			}
		}
	}
	for(int i=0;i<sum;i++)ans=add(ans,MOD-f[n][i]);
	cout<<ans;
	return 0;
}

解题思路：

这道题用暴力可以拿到30分，但正解是状态压缩，将x，y，z的前缀和组成一个数d，再求出方案数sum,进行dp,最后累加结果就是答案