SMU Summer 2023 Contest Round 3
A - Curriculum Vitae
思路：要求0后不能有1，当某个数都不删时，值为前面所有的0的个数加后面所有1的个数，求出最大即可
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,M=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; void solve(){ int n;cin>>n; vector<int>a(n),b(n),c(n); for(int i=0;i<n;++i)cin>>a[i]; b[0]=(a[0]==0); for(int i=1;i<n;++i){ b[i]=b[i-1]+(a[i]==0); } c[n-1]=a[n-1]; for(int i=n-2;i>=0;--i) c[i]=c[i+1]+a[i]; int res=0; for(int i=0;i<n;++i){ res=max(res,b[i]+c[i]); } cout<<res; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
B - Math Show
思路：枚举完成k个任务时的分数，求最大值
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,M=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; void solve(){ int n,k,m,cnt=0;cin>>n>>k>>m; vector<int>a(k+1); for(int i=1;i<=k;++i)cin>>a[i],cnt+=a[i]; sort(a.begin(),a.end()); int res=0; for(int i=0,c,mm;i<=n&&i*cnt<=m;++i){ c=i*(k+1); mm=m-i*cnt; for(int j=1;j<=k;++j){ int s=min(mm/a[j],n-i); c+=s;mm-=s*a[j]; } res=max(res,c); } //if(m==0)res=0; cout<<res; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
C - Four Segments
思路：要求分成四段 / 求三个分界线，可以枚举第二条，再分别左右遍历出第一和第三条的最大情况
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,M=5000000000000+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; void solve(){ int n;cin>>n; vector<int>a(n+1); int d1,d2,d3,all=-M; for(int i=1;i<=n;++i)cin>>a[i],a[i]+=a[i-1]; for(int i=0;i<=n;++i){ int x=-M,y=-M,dd1=0,dd2=n; for(int j=0;j<=i;++j){ int s1=a[j]-a[0]; int s2=a[i]-a[j]; int s=s1-s2; if(s>x){ dd1=j;x=s; } } for(int j=i;j<=n;++j){ int s1=a[j]-a[i]; int s2=a[n]-a[j]; int s=s1-s2; if(s>y){ dd2=j;y=s; } } if(x+y>all){ all=x+y; d1=dd1,d2=i,d3=dd2; } }//cout<<all<<'\n'; cout<<d1<<' '<<d2<<' '<<d3; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
D - Monitor
思路：二分k
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=100+5,M=5000000000000+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; void solve(){ int n,m,k,q,ans=-1;cin>>n>>m>>k>>q; vector<int>x(q+1),y(q+1),t(q+1); vector<vector<int>>ve(n+1,vector<int>(m+1)); for(int i=1;i<=q;++i)cin>>x[i]>>y[i]>>t[i]; int l=0,r=1000000000; while(l<=r){ int mid=l+r>>1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)ve[i][j]=0; for(int i=1;i<=q;++i) if(t[i]<=mid)ve[x[i]][y[i]]=1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ve[i][j]+=ve[i-1][j]+ve[i][j-1]-ve[i-1][j-1]; bool ok=false; for(int i=k;i<=n;++i){ for(int j=k;j<=m;++j){ if((ve[i][j]-ve[i-k][j]-ve[i][j-k]+ve[i-k][j-k])==k*k)ok=true; } if(ok)break; } if(ok)ans=mid,r=mid-1; else l=mid+1; } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //cin>>t; while(t--){ solve(); } return 0; }
思路：期待值=∑该区间的概率*该区间不同元素的个数=区间概率*∑该区间不同元素的个数（每个区间的概率相同）。
∑该区间不同元素的个数=每个元素的贡献值，f（i）表示前i个数的总贡献。
f[i]状态转移：f[i]=f[i-1]+（i-pre[i]），pre[i]表示上一个与a[i]出现的位置，a[i]在 [pre[i]+1，i] 做贡献
a[i]的实际贡献为f[i]*2-1，因为l，r可交换，l和r相等时[l，r]和[r，l]情况相同。
for (int i = 1; i <= n; ++i) { cin>>a[i]; f[i]=f[i-1]+i-pre[a[i]]; ans+=2.0*f[i]-1; pre[a[i]]=i; }