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,最后累加结果就是答案