P8422 题解
RainRecall · · 题解
P8422 题解
前言
这题我从去西安旅游的时候就开始写，写炸了之后，去日照集训的时候重构，回济南又写了一天，才调出来，总用时
题目解法
本题为纯模拟。模拟顺序不难，大概是这样：
每一次询问，先交换元素，判断是否合法，对于每一轮：
-
枚举，消除元素。
-
统计第
1,3 种奖分。 -
重力下落。
一次询问结束后，统计第
每过
接下来让我们来看看每一种奖分怎么统计：
消除奖分
每一轮过后统计即可。
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);
}组合奖分
最大坑点！我来给大家梳理一下：
你消除的是：在同一行或同一列的连续至少
你统计的是：你本次消除的原来颜色相同的四联通块大小。
明白了这个就不难了，开个数组记录一下，深搜即可。
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;
}