CSP2025模拟赛7 · ooliver

S+CSP2025模拟赛7 A. 俄罗斯方块暴力枚举。代码： #include using namespace std; const int M=100; char g[M][M]; bool v[M][M]; int n,m; int c[5]={0}; struct B{ char clr; int p[4][2]; int num,mnx,mxx,mny,mxy; }; bool ok(int x,int y){ return x>=0&&x=0&&y=0&&b.numb.mxx)b.mxx=cx; if(cyb.mxy)b.mxy=cy; for(int i=0;i3) return 0; return 1; }else if(b.mxx-b.mnx==3&&b.mxy-b.mny==0){ for(int i=0;i3) return 0; return 1; } return 0; } bool z(int r[4][2],B &b){ if((b.mxx-b.mnx==1&&b.mxy-b.mny==2)||(b.mxx-b.mnx==2&&b.mxy-b.mny==1)){ bool f1[4]={0},fm1=1; for(int i=0;i>n>>m; for(int i=0;i>g[i]; memset(v,0,sizeof(v)); for(int i=0;i `#include using namespace std; const int M=100; char g[M][M]; bool v[M][M]; int n,m; int c[5]={0}; struct B{ char clr; int p[4][2]; int num,mnx,mxx,mny,mxy; }; bool ok(int x,int y){ return x>=0&&x=0&&y } void get(int x,int y,B &b){ b.clr=g[x][y]; b.num=0; b.mnx=b.mxx=x; b.mny=b.mxy=y; int sx[4],sy[4],t=0; sx[0]=x,sy[0]=y; v[x][y]=1; int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; while(t>=0&&b.num4){ int cx=sx[t],cy=sy[t--]; b.p[b.num][0]=cx; b.p[b.num][1]=cy; b.num++; if(cxb.mnx)b.mnx=cx; if(cx>b.mxx)b.mxx=cx; if(cyb.mny)b.mny=cy; if(cy>b.mxy)b.mxy=cy; for(int i=0;i4;i++){ int nx=cx+dx[i],ny=cy+dy[i]; if(ok(nx,ny)&&!v[nx][ny]&&g[nx][ny]==b.clr){ v[nx][ny]=1; sx[++t]=nx; sy[t]=ny; } } } } void rel(B &b,int r[4][2]){ for(int i=0;i4;i++){ r[i][0]=b.p[i][0]-b.mnx; r[i][1]=b.p[i][1]-b.mny; } } bool sq(int r[4][2]){ bool f[4]={0}; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==0)||(x==0&&y==1)||(x==1&&y==0)||(x==1&&y==1)){ if(x==0&&y==0)f[0]=1; else if(x==0&&y==1)f[1]=1; else if(x==1&&y==0)f[2]=1; else if(x==1&&y==1)f[3]=1; }else return 0; } return f[0]&&f[1]&&f[2]&&f[3]; } bool ln(int r[4][2],B &b){ if(b.mxx-b.mnx==0&&b.mxy-b.mny==3){ for(int i=0;i4;i++) if(r[i][0]!=0||r[i][1]0||r[i][1]>3) return 0; return 1; }else if(b.mxx-b.mnx==3&&b.mxy-b.mny==0){ for(int i=0;i4;i++) if(r[i][1]!=0||r[i][0]0||r[i][0]>3) return 0; return 1; } return 0; } bool z(int r[4][2],B &b){ if((b.mxx-b.mnx==1&&b.mxy-b.mny==2)||(b.mxx-b.mnx==2&&b.mxy-b.mny==1)){ bool f1[4]={0},fm1=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==0)||(x==0&&y==1)||(x==1&&y==1)||(x==1&&y==2)){ if(x==0&&y==0)f1[0]=1; else if(x==0&&y==1)f1[1]=1; else if(x==1&&y==1)f1[2]=1; else if(x==1&&y==2)f1[3]=1; }else fm1=0; } bool f2[4]={0},fm2=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==1)||(x==1&&y==0)||(x==1&&y==1)||(x==2&&y==0)){ if(x==0&&y==1)f2[0]=1; else if(x==1&&y==0)f2[1]=1; else if(x==1&&y==1)f2[2]=1; else if(x==2&&y==0)f2[3]=1; }else fm2=0; } return (fm1&&f1[0]&&f1[1]&&f1[2]&&f1[3])||(fm2&&f2[0]&&f2[1]&&f2[2]&&f2[3]); } return 0; } bool rz(int r[4][2],B &b){ if((b.mxx-b.mnx==1&&b.mxy-b.mny==2)||(b.mxx-b.mnx==2&&b.mxy-b.mny==1)){ bool f1[4]={0},fm1=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==1)||(x==0&&y==2)||(x==1&&y==0)||(x==1&&y==1)){ if(x==0&&y==1)f1[0]=1; else if(x==0&&y==2)f1[1]=1; else if(x==1&&y==0)f1[2]=1; else if(x==1&&y==1)f1[3]=1; }else fm1=0; } bool f2[4]={0},fm2=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==0)||(x==1&&y==0)||(x==1&&y==1)||(x==2&&y==1)){ if(x==0&&y==0)f2[0]=1; else if(x==1&&y==0)f2[1]=1; else if(x==1&&y==1)f2[2]=1; else if(x==2&&y==1)f2[3]=1; }else fm2=0; } return (fm1&&f1[0]&&f1[1]&&f1[2]&&f1[3])||(fm2&&f2[0]&&f2[1]&&f2[2]&&f2[3]); } return 0; } bool t(int r[4][2],B &b){ if((b.mxx-b.mnx==1&&b.mxy-b.mny==2)||(b.mxx-b.mnx==2&&b.mxy-b.mny==1)){ bool f1[4]={0},fm1=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==1)||(x==1&&y==0)||(x==1&&y==1)||(x==1&&y==2)){ if(x==0&&y==1)f1[0]=1; else if(x==1&&y==0)f1[1]=1; else if(x==1&&y==1)f1[2]=1; else if(x==1&&y==2)f1[3]=1; }else fm1=0; } bool f2[4]={0},fm2=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==0)||(x==1&&y==0)||(x==1&&y==1)||(x==2&&y==0)){ if(x==0&&y==0)f2[0]=1; else if(x==1&&y==0)f2[1]=1; else if(x==1&&y==1)f2[2]=1; else if(x==2&&y==0)f2[3]=1; }else fm2=0; } bool f3[4]={0},fm3=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==0)||(x==0&&y==1)||(x==0&&y==2)||(x==1&&y==1)){ if(x==0&&y==0)f3[0]=1; else if(x==0&&y==1)f3[1]=1; else if(x==0&&y==2)f3[2]=1; else if(x==1&&y==1)f3[3]=1; }else fm3=0; } bool f4[4]={0},fm4=1; for(int i=0;i4;i++){ int x=r[i][0],y=r[i][1]; if((x==0&&y==1)||(x==1&&y==0)||(x==1&&y==1)||(x==2&&y==1)){ if(x==0&&y==1)f4[0]=1; else if(x==1&&y==0)f4[1]=1; else if(x==1&&y==1)f4[2]=1; else if(x==2&&y==1)f4[3]=1; }else fm4=0; } return (fm1&&f1[0]&&f1[1]&&f1[2]&&f1[3])||(fm2&&f2[0]&&f2[1]&&f2[2]&&f2[3])||(fm3&&f3[0]&&f3[1]&&f3[2]&&f3[3])||(fm4&&f4[0]&&f4[1]&&f4[2]&&f4[3]); } return 0; } void chk(B &b){ if(b.num!=4)return; int r[4][2]; rel(b,r); if(sq(r))c[0]++; else if(ln(r,b))c[1]++; else if(rz(r,b))c[2]++; else if(z(r,b))c[3]++; else if(t(r,b))c[4]++; } int main(){ freopen("tetris.in","r",stdin); freopen("tetris.out","w",stdout); cin>>n>>m; for(int i=0;i>g[i]; memset(v,0,sizeof(v)); for(int i=0;i for(int j=0;j if(g[i][j]!='.'&&!v[i][j]){ B b; get(i,j,b); chk(b); } for(int i=0;i5;i++)coutc[i] return 0; }` B. 矩形染色显而易见可以只统计一个象限，可以贪心将所占纵向长度排序，若当前横坐标比上一个大，说明有贡献。代码： #include using namespace std; const int N=(1e7+5)/2; struct node{ int id,h; }; int n; long long ans; node a[N]; bool cmp(node x,node y){ return x.h>y.h; } signed main(){ freopen("rect.in","r",stdin); freopen("rect.out","w",stdout); cin>>n; for(int i=1;i>x>>y; a[i]={x/2,y/2}; } sort(a+1,a+1+n,cmp); int lst=0; for(int i=1;ilst) ans+=1ll*(a[i].id-lst)*a[i].h,lst=a[i].id; cout `#include using namespace std; const int N=(1e7+5)/2; struct node{ int id,h; }; int n; long long ans; node a[N]; bool cmp(node x,node y){ return x.h>y.h; } signed main(){ freopen("rect.in","r",stdin); freopen("rect.out","w",stdout); cin>>n; for(int i=1;i int x,y; cin>>x>>y; a[i]={x/2,y/2}; } sort(a+1,a+1+n,cmp); int lst=0; for(int i=1;iif(a[i].id>lst) ans+=1ll*(a[i].id-lst)*a[i].h,lst=a[i].id; cout4ll; return 0; }` C. 帝国重建单调队列优化，维护一个单调队列来高效找到最优分割点，使得分割后的每一段（合并后的堆）高度非递减，最终用总堆数减去最大保留段数得到最少合并次数。 #include using namespace std; #define int long long const int N=1e6+5; int n,l,r; int a[N],s[N],dp[N],q[N]; signed main(){ freopen("empire.in","r",stdin); freopen("empire.out","w",stdout); cin>>n; for(int i=1;i>a[i],a[i]+=a[i-1]; for(int i=1;i=s[q[l+1]]) l++; dp[i]=dp[q[l]]+1,s[i]=a[i]-a[q[l]]; while(la[i]+s[i]) r--; q[++r]=i; } cout `#include using namespace std; #define int long long const int N=1e6+5; int n,l,r; int a[N],s[N],dp[N],q[N]; signed main(){ freopen("empire.in","r",stdin); freopen("empire.out","w",stdout); cin>>n; for(int i=1;i>a[i],a[i]+=a[i-1]; for(int i=1;i while(la[i]-a[q[l+1]]>=s[q[l+1]]) l++; dp[i]=dp[q[l]]+1,s[i]=a[i]-a[q[l]]; while(ls[q[r]]+a[q[r]]>a[i]+s[i]) r--; q[++r]=i; } coutdp[n]; return 0; }`