一起来做题~欢乐赛1
A 可以用map离散化
#include<bits/stdc++.h> using namespace std; int const N=2e5+7; int t,n,m; map<int,int>pos,cnt; //可以用map离散化 //记录在数轴的位置并映射出它的值 map<int,int>::iterator it; int main(){ cin >> t; while(t--){ cin >> n >> m; pos.clear();cnt.clear(); for(int i=1;i<=n;++i){ int a;cin >> a; pos[a]=1;cnt[a]++; } for(int i=1;i<=m;++i){ int a;cin >> a; pos[a]=0;cnt[a]=0; } int ans=0,sum=0; for(it=pos.begin();it!=pos.end();++it){ if(it->second) sum+=cnt[it->first]; else sum=0; ans=max(ans,sum); } if(ans) cout << ans << "\n"; else cout << "Impossible\n"; } return 0; }
B 按灯题
尝试着分析(画一画,举例子)可以发现是按灯题的模型
第一个确定了,放法就确定了
#include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e4+7; int n; int a[N],l[N]; int pan(){ for(int i=2;i<=n;++i){ l[i]=a[i-1]-l[i-1]-l[i-2]; if(l[i]<0||l[i]>1) return 0; } if(l[n]+l[n-1]!=a[n]) return 0; return 1; } int main(){ cin >> n; for(int i=1;i<=n;++i){ cin >> a[i]; } int cnt=0; l[1]=1; if(pan()) cnt++; l[1]=0; if(pan()) cnt++; cout << cnt; return 0; }
C 提前操作和反向操作
发功后对前面的无影响,对后面的有影响,所以可以让其全部发完功再操作
操作可以从后往前
看到区间修改就要反映过来(差分前缀和、线段树)
特别是看到区间相对大小的变化,要反映过来是差分
#include<bits/stdc++.h> using namespace std; #define ll long long int const N=5e4+7; int t,n,m; int a[N],b[N],sex[N]; int main(){ cin >> t; while(t--){ cin >> n >> m; for(int i=1;i<=n;++i){ cin >> sex[i] >> a[i]; b[i]=a[i]-a[i-1]; } for(int i=1;i<=m;++i) { int x;cin >> x; b[1]+=1;b[x+1]-=1; } for(int i=1;i<=n;++i) b[i]+=b[i-1]; int maxn[2]={0,0},cnt=0; for(int i=n;i>=1;--i){ if(b[i]>=maxn[sex[i]^1]) cnt++; maxn[sex[i]]=max(maxn[sex[i]],b[i]); } cout << cnt << "\n"; } return 0; }
D 记搜写dp
背包也是线性dp,想到可以由前面覆盖(转移),而无背包的形,要反映过来是线性dp
求分数,f肯定表示分数,而其表示的搜索状态一般为题目所给的条件
#include<bits/stdc++.h> using namespace std; #define ll long long int const N=357; int n,m,op[6]; int a[N],f[47][47][47][47]; int dfs(int i,int j,int k,int l){ if(i<0||j<0||k<0||l<0) return 0; if(f[i][j][k][l]!=0) return f[i][j][k][l]; f[i][j][k][l]=max( max(dfs(i-1,j,k,l),dfs(i,j-1,k,l)), max(dfs(i,j,k-1,l),dfs(i,j,k,l-1)) ) + a[1+i+2*j+3*k+4*l]; return f[i][j][k][l]; } int main(){ cin >> n >> m; for(int i=1;i<=n;++i) cin >> a[i]; for(int i=1;i<=m;++i) { int x;cin >> x; op[x]++; } int ans=0; ans=dfs(op[1],op[2],op[3],op[4]); cout << ans; return 0; }
E 用倍增预处理
#include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e6+7; int n,m,k; ll a[N]; ll f[N][24]; int pan(int l,int r){ int ans=0; for(int j=20;j>=0;--j){ if(f[l][j]<=r){ ans+=(1<<j); l=f[l][j]; } } //if(f[l][0]==l&&a[l]>k) return 0; if(f[l][0]<=r) return 0; return ans+1; } int main(){ cin >> n >> m >> k; for(int i=1;i<=n;++i){ cin >> a[i]; } for(int j=0;j<=20;++j){ for(int i=1;i<=n+1;++i){ //注意这里到n+1 f[i][j]=n+1; //初始化 } } ll sum=0; for(int i=1,j=0;i<=n;++i){ while(j<=n&&sum<=k) sum+=a[++j]; f[i][0]=j; //初始化 sum-=a[i]; } for(int j=1;j<=20;++j){ for(int i=1;i<=n;++i){ f[i][j]=f[f[i][j-1]][j-1]; } } int l,r; for(int i=1;i<=m;++i){ cin >> l >> r; int ans=0; ans=pan(l,r); if(ans) cout << ans << "\n"; else cout << "Chtholly\n"; } return 0; }