S+CSP2025模拟赛7
A. 俄罗斯方块
暴力枚举。
代码：
#include<bits/stdc++.h>
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<n&&y>=0&&y<m;
}
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.num<4){
int cx=sx[t],cy=sy[t--];
b.p[b.num][0]=cx;
b.p[b.num][1]=cy;
b.num++;
if(cx<b.mnx)b.mnx=cx;
if(cx>b.mxx)b.mxx=cx;
if(cy<b.mny)b.mny=cy;
if(cy>b.mxy)b.mxy=cy;
for(int i=0;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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;i<4;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<n;i++)cin>>g[i];
memset(v,0,sizeof(v));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j]!='.'&&!v[i][j]){
B b;
get(i,j,b);
chk(b);
}
for(int i=0;i<5;i++)cout<<c[i]<<endl;
return 0;
}B. 矩形染色
显而易见可以只统计一个象限，
可以贪心将所占纵向长度排序，
若当前横坐标比上一个大，说明有贡献。
代码：
#include<bits/stdc++.h>
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<=n;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;i<=n;i++) if(a[i].id>lst) ans+=1ll*(a[i].id-lst)*a[i].h,lst=a[i].id;
cout<<ans*4ll;
return 0;
}C. 帝国重建
单调队列优化，
维护一个单调队列来高效找到最优分割点，
使得分割后的每一段（合并后的堆）高度非递减，
最终用总堆数减去最大保留段数得到最少合并次数。
#include<bits/stdc++.h>
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<=n;i++) cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=n;i++){
while(l<r&&a[i]-a[q[l+1]]>=s[q[l+1]]) l++;
dp[i]=dp[q[l]]+1,s[i]=a[i]-a[q[l]];
while(l<=r&&s[q[r]]+a[q[r]]>a[i]+s[i]) r--;
q[++r]=i;
}
cout<<n-dp[n];
return 0;
}
Comments NOTHING