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;
}
View Code
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;
}
View Code
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;
}
View Code
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;
}
View Code
思路：期待值=∑该区间的概率*该区间不同元素的个数=区间概率*∑该区间不同元素的个数（每个区间的概率相同）。
∑该区间不同元素的个数=每个元素的贡献值，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;
}
View Code
标签：Summer,typedef,const,Contest,int,SMU,long,--,solve From： https://www.cnblogs.com/bible-/p/17554750.html