10.2模拟赛总结

大概难度：t1t2黄t3蓝t4紫
预估得分：100+0+0+0~10
实际得分：100+0+0+10=110
黄题切不出来，我是人机
t1大概20~30min有思路，但当时的思路是l到r的区间总数-全奇数的区间总数。代码大概写了1h左右发现少减了全偶数的情况。剩下的时间就都在调代码和加特判，11:30左右调完，剩下30min在t1的long long在纠结，还顺便在t4cout了个-1

t1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10;
int a[N],jl[N],jr[N],sl[N],sr[N];
ll sumj[N],sums[N];
ll js(ll l,ll r){return r-l+1+(r-l+1)*(r-l)/2;
}
int main(){freopen("math.in","r",stdin);freopen("math.out","w",stdout);int n,q;cin>>n>>q;for(int i=1,x;i<=n;++i){scanf("%d",&x); a[i]=(x&1);}int tot=0;for(int i=1;i<=n;){while(i<=n&&a[i]==0) ++i;if(i<=n){jl[++tot]=i;while(i<=n&&a[i]==1) ++i;jr[tot]=i-1;}}int cnt=0;for(int i=1;i<=n;){while(i<=n&&a[i]==1) ++i;if(i<=n){sl[++cnt]=i;while(i<=n&&a[i]==0) ++i;sr[cnt]=i-1;}}for(int i=1;i<=tot;++i){sumj[jr[i]]=js(jl[i],jr[i]);}for(int i=1;i<=cnt;++i){sums[sr[i]]=js(sl[i],sr[i]);}for(int i=1;i<=n;++i){sumj[i]+=sumj[i-1]; sums[i]+=sums[i-1];}ll ans=0;for(int t=1,l,r,i,j;t<=q;++t){ans=0;scanf("%d %d",&l,&r);ans=js(l,r);i=(int)(upper_bound(jl+1,jl+tot+1,l)-jl-1); j=(int)(upper_bound(jl+1,jl+tot+1,r)-jl-1);if(jl[i]<=l&&jr[i]>=r){printf("0\n"); continue;}if(jr[i]>=l) ans-=js(l,jr[i]);if(jr[j]>=r) ans-=(i!=j)?js(jl[j],r):0;else j+=1;if(i+1<=j-1) ans-=sumj[jr[j-1]]-sumj[jl[i+1]-1];i=(int)(upper_bound(sl+1,sl+cnt+1,l)-sl-1); j=(int)(upper_bound(sl+1,sl+cnt+1,r)-sl-1);if(sl[i]<=l&&sr[i]>=r){printf("0\n"); continue;}if(sr[i]>=l) ans-=js(l,sr[i]);if(sr[j]>=r) ans-=(i!=j)?js(sl[j],r):0;else j+=1;if(i+1<=j-1) ans-=sums[sr[j-1]]-sums[sl[i+1]-1];printf("%lld\n",ans);}return 0;
}

t2

#include <iostream>
#include <stack>
using namespace std;
const int N=3010;
stack<int>st;
int a[N][N],dp[N][N],l[N][N],s[N][N];
int main(){freopen("art.in","r",stdin);freopen("art.out","w",stdout);int n,m;cin>>n>>m;char ch;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cin>>ch; a[i][j]=(ch=='W')?1:2;}}int ans=1;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){l[i][j]=(a[i][j]==a[i][j-1])?l[i][j-1]+1:1;}}for(int j=2;j<=m;++j){for(int i=1;i<=n;++i){while(st.size()&&l[st.top()][j]>l[i][j]){dp[st.top()][j]+=i-st.top(); st.pop();}st.push(i);}while(st.size()){dp[st.top()][j]+=n+1-st.top(); st.pop();}for(int i=n;i>=1;--i){while(st.size()&&l[st.top()][j]>l[i][j]){dp[st.top()][j]+=st.top()-i-1; st.pop();}st.push(i);}while(st.size()){dp[st.top()][j]+=st.top()-1; st.pop();}}for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){ans=max(ans,min(dp[i][j],l[i][j])*min(dp[i][j],l[i][j]));}}cout<<ans;return 0;
}

t3

(待补）

t4

(待补）