15011418730 LV 7 @ 2025-8-24 22:38:54

自动搬运

来自洛谷，原作者为

	Milthm ?

搬运于2025-08-24 22:38:54，当前版本为作者最后更新于2023-07-21 18:25:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8422 题解

前言

这题我从去西安旅游的时候就开始写，写炸了之后，去日照集训的时候重构，回济南又写了一天，才调出来，总用时 $14$ 个小时。这题本身并没有那么难，但是有一些坑点，这篇题解主要给大家说一下做法和一些坑点。

题目解法

本题为纯模拟。模拟顺序不难，大概是这样：

每一次询问，先交换元素，判断是否合法，对于每一轮：

枚举，消除元素。
统计第 $1,3$ 种奖分。
重力下落。

一次询问结束后，统计第 $2$ 种奖分。

每过 $5$ 次询问，统计一次第 $4$ 种奖分。所有询问都结束后，统计最后一种奖分。

接下来让我们来看看每一种奖分怎么统计：

消除奖分

每一轮过后统计即可。

void solve(){
	int lunshu=0;
	bool nengxiaochu=1;
	while(nengxiaochu){
		......
		ans1+=he*lunshu;//he 为颜色编号之和,lunshu 为轮数
	}
	......
}

连锁奖分

void solve(){
	int lunshu=0;
	bool nengxiaochu=1;
	while(nengxiaochu){
    	......
	}
	lunshu--;//如果你和我的实现方式一样，记得千万要把轮数减一下，因为不能消除的那一次也算在内了
	ans2+=80*(lunshu-1)*(lunshu-1);
}

组合奖分

最大坑点！我来给大家梳理一下：

你消除的是：在同一行或同一列的连续至少 $3$ 个相同颜色的棋子。

你统计的是：你本次消除的原来颜色相同的四联通块大小。

明白了这个就不难了，开个数组记录一下，深搜即可。

void dfs(int ax,int ay,int x,int y){
	vis[x][y]=1;++L;
	for(int i=0;i<4;++i){
		int px=x+w[i][0];
		int py=y+w[i][1];
		if(hefa(px,py)&&vis[px][py]==0&&del[px][py]&&a[ax][ay].x==a[px][py].x){
			dfs(ax,ay,px,py);
		}
	}
}
void solve(){
	int lunshu=0;
	bool nengxiaochu=1;
	while(nengxiaochu){
		......
		clear();//清空 vis 数组
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(del[i][j]&&vis[i][j]==0){//记得判断是不是被访问过
					dfs(i,j,i,j);
					ans3+=(L-3)*(L-3)*50;
					L=0;//记得清零！！！
				}
			}
		}
		......
	}
	......
}

牌型奖分

最麻烦的一个，其实一点都不难，直接五重循环暴力枚举，按照题意模拟即可。可以使用集合和排序减少码量。

小坑点：记得记录最大值，不要直接返回。

void paixing(){
	int zzy[10]={0};
	s.clear();
	int cnt=0;
	for(int i=0;i<=1;++i){
		for(int j=0;j<=1;++j){
			for(int k=0;k<=1;++k){
				for(int l=0;l<=1;++l){
					for(int o=0;o<=1;++o){
						zzy[1]=color[1][i];
						zzy[2]=color[2][j];
						zzy[3]=color[3][k];
						zzy[4]=color[4][l];
						zzy[5]=color[5][o];
						if(zzy[1]==0||zzy[2]==0||zzy[3]==0||zzy[4]==0||zzy[5]==0)continue;//记得判断有没有颜色！！！！
						sort(zzy+1,zzy+6);
						for(int p=1;p<=5;++p)s.insert(zzy[p]);
						int len=s.size();
						if(len==5)cnt=max(cnt,50+zzy[5]);
						else if(len==4){
							int r=0;
							for(int p=1;p<=4;++p){
								if(zzy[p]==zzy[p+1]){
									r=zzy[p];break;
								}
							}
							cnt=max(cnt,100+r*2);
						}
						else if(len==3){
							int r=0,rr=0; 
							for(int p=1;p<=4;++p){
								if(zzy[p]==zzy[p+1]){
									if(r==0)r=zzy[p];
									else rr=zzy[p];
								}
							}
							if(r!=rr)cnt=max(cnt,200+max(r,rr)*2+min(r,rr));
							else{
								cnt=max(cnt,300+r*3);
							}	
						}
						else if(len==2){
							if(zzy[1]==zzy[4]||zzy[2]==zzy[5]){
								cnt=max(cnt,750+zzy[3]*5);
							}
							else{
								int bt=0;
								for(int p=1;p<=5;++p){
									if(zzy[p]!=zzy[3]){
										bt=zzy[p];
									}
								}
								cnt=max(cnt,500+zzy[3]*3+bt);
							}
						}
						else{
							cnt=max(cnt,1000+zzy[1]*10);
						}
						s.clear();
					}
				}
			}
		}
	}
	ans4+=cnt;
}

终局奖分

最后判断即可，很简单。

AC 代码

不加注释了，上面讲的很详细。

#include<iostream>
#include<cmath>
#include<set>
#include<algorithm>
#define qwq 0
using namespace std;
struct node{
	int x,b;
}a[505][505];
int n,m,k,q,x,y,x2,y2,die[505][505],ans1,ans2,ans3,ans4,del[505][505];
int he,color[105][2],u,vis[505][505],L;
set<int>s; 
bool quanbuhefa=1;
bool hefa(int x,int y){
	return (x>=1&&x<=n&&y>=1&&y<=m);
}
void xiaochu(int x,int y){
	if(die[x][y]||a[x][y].x==0)return;
	die[x][y]=1;
	if(a[x][y].b==1){
		for(int i=1;i<=m;++i){
			if(i!=y)xiaochu(x,i);
		}
	}
	else if(a[x][y].b==2){
		for(int i=1;i<=n;++i){
			if(i!=x)xiaochu(i,y);
		}
	}
	else if(a[x][y].b==3){
		for(int i=1;i<=m;++i){
			if(i!=y)xiaochu(x,i);
		}
		for(int i=1;i<=n;++i){
			if(i!=x)xiaochu(i,y);
		}
	}
	else if(a[x][y].b==4){
		for(int i=x-1;i<=x+1;++i){
			for(int j=y-1;j<=y+1;++j){
				if(!(x==i&&y==j)&&hefa(i,j))xiaochu(i,j);
			}
		}
	}
	else if(a[x][y].b==5){
		for(int i=x-2;i<=x+2;++i){
			for(int j=y-2;j<=y+2;++j){
				if(!(x==i&&y==j)&&hefa(i,j))xiaochu(i,j);
			}
		}
	}
	else if(a[x][y].b==6){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if((!(x==i&&y==j))&&a[i][j].x==a[x][y].x)xiaochu(i,j);
			}
		}
	}
} 
int heng_len(int x,int y,bool f){
	if(a[x][y].x==0)return 0;
	int px=x-1,ans=1;
	if(f)xiaochu(x,y),del[x][y]=1;
	while(px>=1&&a[px][y].x==a[x][y].x){
		if(f)xiaochu(px,y),del[px][y]=1;
		++ans,--px;
	}
	px=x+1;
	while(px<=n&&a[px][y].x==a[x][y].x){
		if(f)xiaochu(px,y),del[px][y]=1;;
		++ans,++px;
	}
	return ans;
}
int shu_len(int x,int y,bool f){
	if(a[x][y].x==0)return 0;
	int py=y-1,ans=1;
	if(f)xiaochu(x,y),del[x][y]=1;
	while(py>=1&&a[x][py].x==a[x][y].x){
		if(f)xiaochu(x,py),del[x][py]=1;
		++ans,--py;
	}
	py=y+1;
	while(py<=m&&a[x][py].x==a[x][y].x){
		if(f)xiaochu(x,py),del[x][py]=1;
		++ans,++py;
	}
	return ans;
}
void print(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cout<<a[i][j].x<<"("<<a[i][j].b<<") ";
		}
		cout<<'\n';
	}
	cout<<"-----------------\n";
}
void clear(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[i][j]=0;
		}
	}
}
void xialuo(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(die[i][j]){
				he+=a[i][j].x;
				a[i][j]={0,0};
			}
			die[i][j]=0;
			del[i][j]=0;
		}
	}	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			int px=i;
			while(a[px][j].x!=0&&a[px+1][j].x==0&&px<n){
				swap(a[px][j],a[px+1][j]);
				++px;
			}
		}
	}
}
int w[4][2]={{0,1},{1,0},{-1,0},{0,-1}},zuhe;
void dfs(int ax,int ay,int x,int y){
	vis[x][y]=1;++L;
	for(int i=0;i<4;++i){
		int px=x+w[i][0];
		int py=y+w[i][1];
		if(hefa(px,py)&&vis[px][py]==0&&del[px][py]&&a[ax][ay].x==a[px][py].x){
			dfs(ax,ay,px,py);
		}
	}
}
void solve(){
	int lunshu=0;
	bool nengxiaochu=1;
	while(nengxiaochu){
		lunshu++;
		nengxiaochu=0;
		he=0;
		zuhe=0,L=0;
		for(int i=n;i>=1;--i){
			for(int j=1;j<=m;++j){
				if(lunshu==1&&(!(x==i&&y==j))&&(!(x2==i&&y2==j)))continue;
				//cout<<i<<" "<<j<<endl;
				int hh=heng_len(i,j,0),ss=shu_len(i,j,0);
				//cout<<i<<" "<<j<<" "<<hh<<" "<<ss<<endl;
				if(hh>=3||ss>=3){
					int qq=a[i][j].x;
					if(hh>=3)heng_len(i,j,1);
					die[i][j]=0;
					a[i][j].x=qq;
					if(ss>=3)shu_len(i,j,1);
					die[i][j]=1;
					nengxiaochu=1;
					L=0;
				} 
			}
		}
		//print();
		clear();
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(del[i][j]&&vis[i][j]==0){
					dfs(i,j,i,j);
					ans3+=(L-3)*(L-3)*50;
					L=0;
				}
			}
		}
		for(int i=1;i<=200;++i)xialuo();

		ans1+=he*lunshu;
		//print();
	}
	lunshu--;
	ans2+=80*(lunshu-1)*(lunshu-1);
}
void paixing(){
	int zzy[10]={0};
	s.clear();
	int cnt=0;
	for(int i=0;i<=1;++i){
		for(int j=0;j<=1;++j){
			for(int k=0;k<=1;++k){
				for(int l=0;l<=1;++l){
					for(int o=0;o<=1;++o){
						zzy[1]=color[1][i];
						zzy[2]=color[2][j];
						zzy[3]=color[3][k];
						zzy[4]=color[4][l];
						zzy[5]=color[5][o];
						if(zzy[1]==0||zzy[2]==0||zzy[3]==0||zzy[4]==0||zzy[5]==0)continue;
						sort(zzy+1,zzy+6);
						for(int p=1;p<=5;++p)s.insert(zzy[p]);
						int len=s.size();
						if(len==5)cnt=max(cnt,50+zzy[5]);
						else if(len==4){
							int r=0;
							for(int p=1;p<=4;++p){
								if(zzy[p]==zzy[p+1]){
									r=zzy[p];break;
								}
							}
							cnt=max(cnt,100+r*2);
						}
						else if(len==3){
							int r=0,rr=0; 
							for(int p=1;p<=4;++p){
								if(zzy[p]==zzy[p+1]){
									if(r==0)r=zzy[p];
									else rr=zzy[p];
								}
							}
							if(r!=rr)cnt=max(cnt,200+max(r,rr)*2+min(r,rr));
							else{
								cnt=max(cnt,300+r*3);
							}	
						}
						else if(len==2){
							if(zzy[1]==zzy[4]||zzy[2]==zzy[5]){
								cnt=max(cnt,750+zzy[3]*5);
							}
							else{
								int bt=0;
								for(int p=1;p<=5;++p){
									if(zzy[p]!=zzy[3]){
										bt=zzy[p];
									}
								}
								cnt=max(cnt,500+zzy[3]*3+bt);
							}
						}
						else{
							cnt=max(cnt,1000+zzy[1]*10);
						}
						s.clear();
					}
				}
			}
		}
	}
	ans4+=cnt;
}
int main(){
	cin>>n>>m>>k>>q;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j].x;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j].b;
		}
	}
	while(q--){
		cin>>x>>y>>x2>>y2;
		swap(a[x][y],a[x2][y2]);
		int h1=heng_len(x,y,0),h2=heng_len(x2,y2,0);
		int s1=shu_len(x,y,0),s2=shu_len(x2,y2,0);
		int o=abs(x-x2),o2=abs(y-y2);
		if(o+o2!=1||hefa(x,y)==0||hefa(x2,y2)==0||(h1<3&&s1<3&&h2<3&&s2<3)||a[x2][y2].x==0||a[x][y].x==0){
			swap(a[x][y],a[x2][y2]);
			quanbuhefa=0;continue;
		}
		++u;
		if(h1>=3||s1>=3)color[u][0]=a[x][y].x;
		if(h2>=3||s2>=3){
			if(color[u][0])color[u][1]=a[x2][y2].x;
			else color[u][0]=a[x2][y2].x;
		}
		if(u==5){
			int as=ans4;
			paixing();
			for(int i=1;i<=5;++i){
				color[i][0]=color[i][1]=0;
			}
			u=0;
			//cout<<ans4-as<<endl;
		}
		solve();
		//cout<<ans1+ans2+ans3+ans4<<endl;
	}
	int ans=0;
	if(quanbuhefa)ans=1000;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i][j].x!=0)goto R;
		}
	}
	ans+=10000;
	R:cout<<ans+ans1+ans2+ans3+ans4<<endl;
	//cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4;
	return qwq;
}

ID

7779

时间

1000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

P8422 题解

前言

题目解法

消除奖分

连锁奖分

组合奖分

牌型奖分

终局奖分

AC 代码

[THUPC 2022 决赛] 德州消消乐

信息

1 条题解

自动搬运

以下是正文

P8422 题解

前言

题目解法

消除奖分

连锁奖分

组合奖分

牌型奖分

终局奖分

AC 代码

[THUPC 2022 决赛] 德州消消乐

信息

还没有账户？

登录