专栏文章

P9262

llsj2009Isj2OO9
P9262题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqlfjci
此快照首次捕获于
2025/12/04 06:43
3 个月前
此快照最后确认于
2025/12/04 06:43
3 个月前
查看原文

Description

有一个大小 n×mn\times m 的矩阵（有些地方有东西，有些地方为空），有 qq 次操作，每次操作会改变整个矩阵的 重力方向（仅限于上下左右）。
即矩形上的所有东西都朝着重力方向移动直到遇到边界或者遇到其他物品（想一下 2048 小游戏？）
求 qq 操作之后的矩阵长什么样子。
1≤n,m≤5001\le n,m\le 500，1≤k≤5×1051\le k\le 5\times 10^5。
1.00s，512MB。

Solution

我们首先消去连续的同一方向类型（上下为一类型，左右为一类型）的操作，再删去间隔一位的相同操作，会发现最终只剩下开头（要把所有东西搞到角落）、结尾的 O(1)\mathcal{O}(1) 次操作和 O(k)\mathcal{O}(k) 次「转圈」。
其中 O(1)\mathcal{O}(1) 次操作可以暴力做，考虑如何快速做「转圈」。
注意到「转圈」有不同种类（如右下左上和下右上左是不同的），但总归只有 O(1)\mathcal{O}(1) 种，并且「转圈」具有 交换律，也就是我先转那个圈还是先转这个圈是无所谓的（想想证明？这很重要。），所以我们把相同种类的转圈归到一起做就好了。
Observation：进行一轮「转圈」之后，物品的轮廓是不变的。
手摸一下还是比较显然的。这里其实也就解释了「转圈」具有交换律的原因。
则由于轮廓不变，所以每次一个位置 (x,y)(x,y) 在转一圈后去到的位置 P(x,y)P_{(x,y)} 是一致的
事实上 PP 是一个置换，则转 kk 次后 (x,y)(x,y) 就会去到 P(x,y)kP^k_{(x,y)}，问题转换为求置换的 kk 次方，可以直接把置换环拉出来然后拿出每个点往后 kk 个点的位置即可；或者注意到置换具有结合律，跑一个快速幂即可。
两种实现，前者复杂度为 O(nm+k)\mathcal{O}(nm+k)，后者为 O(k+nmlog⁡k)\mathcal{O}(k+nm\log{k})。

Code

CPP
#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
//	system("fc .out .ans");
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
bool M1;
const int N=5e2+5,M=5e5+5;
char s[N][N],t[M],ans[M];
int a[N][N],d[N][N],p[M],q[M],tot,n,m,k;
bool used[M];
int c[M],ttot;
void dfs(int u) {
	if(used[u])
		return;
	used[u]=true;
	c[++ttot]=u;
	dfs(p[u]);
}
int new_node() {
	return ++tot;
}
template<typename T>
void upd(T s[N][N],T x,char op) {
	T b[N];
	if(op=='G') {
		rep(j,1,m) {
			int len=0;
			rep(i,1,n) {
				if(s[i][j]!=x)
					b[++len]=s[i][j];
			}
			rep(i,1,len)
				s[i][j]=b[i];
			rep(i,len+1,n)
				s[i][j]=x;
		}
	} else if(op=='D') {
		rep(j,1,m) {
			int len=0;
			per(i,n,1) {
				if(s[i][j]!=x)
					b[++len]=s[i][j];
			}
			rep(i,1,len)
				s[n-i+1][j]=b[i];
			rep(i,len+1,n)
				s[n-i+1][j]=x;
		}
	} else if(op=='L') {
		rep(i,1,n) {
			int len=0;
			rep(j,1,m) {
				if(s[i][j]!=x)
					b[++len]=s[i][j];
			}
			rep(j,1,len)
				s[i][j]=b[j];
			rep(j,len+1,m)
				s[i][j]=x;
		}
	} else {
		rep(i,1,n) {
			int len=0;
			per(j,m,1) {
				if(s[i][j]!=x)
					b[++len]=s[i][j];
			}
			rep(j,1,len)
				s[i][m-j+1]=b[j];
			rep(j,len+1,m)
				s[i][m-j+1]=x;
		}
	}
}
int get1(char op) {
	return op=='G'||op=='D';
}
int get2(char op) {
	return op=='G'||op=='L';
}
map<stack<char>,int> cnt;
void solve() {
	scanf("%d%d",&n,&m);
	rep(i,1,n)
		scanf("%s",s[i]+1);
	scanf("%d",&k);
	scanf("%s",t+1);
	int S=0,pos=k,op1=-1,op2=-1;
	rep(i,1,k) {
		S|=1<<get1(t[i]);
		if(S==3) {
			pos=i;
			break;
		}
	}
	int x=0,y=0;
	per(i,pos,1) {
		if(get1(t[i])) {
			op1=get2(t[i]);
			x=i;
			break;
		}
	}
	per(i,pos,1) {
		if(!get1(t[i])) {
			op2=get2(t[i]);
			y=i;
			break;
		}
	}
	if(x>y)
		swap(x,y);
	if(x)
		upd(s,'.',t[x]);
	if(y)
		upd(s,'.',t[y]);
	if(pos==k) {
		rep(i,1,n)
			printf("%s\n",s[i]+1);
		return;
	}
	stack<char> st;
	rep(i,pos+1,k) {
		if(get1(t[i])) {
			if((t[i]=='G')==op1)
				continue;
			if(!st.empty()&&get1(st.top()))
				st.pop();
			else
				st.push(t[i]);
			op1^=1;
		} else {
			if((t[i]=='L')==op2)
				continue;
			if(!st.empty()&&!get1(st.top()))
				st.pop();
			else
				st.push(t[i]);
			op2^=1;
		}
		if((int)st.size()==4) {
			++cnt[st];
			while(!st.empty())
				st.pop();
		}
	}
	for(auto x:cnt) {
		tot=0;
		rep(i,1,n) {
			rep(j,1,m) {
				if(s[i][j]!='.') {
					int u=new_node();
					d[i][j]=a[i][j]=u;
					ans[u]=s[i][j];
				} else
					a[i][j]=d[i][j]=0;
			}
		}
		stack<char> st=x.first;
		int tt[5],len=0;
		while(!st.empty())
			tt[++len]=st.top(),st.pop();
		reverse(tt+1,tt+len+1);
		rep(i,1,len)
			upd(a,0,tt[i]);
		rep(i,1,n) {
			rep(j,1,m) {
				if(d[i][j])
					p[d[i][j]]=a[i][j];
			}
		}
		rep(i,1,tot)
			used[i]=false;
		int cc=x.second;
		rep(i,1,tot) {
			if(!used[i]) {
				ttot=0;
				dfs(i);
				rep(j,1,ttot)
					q[c[j]]=c[(j+cc-1)%ttot+1];
			}
		}
		rep(i,1,n) {
			rep(j,1,m) {
				if(d[i][j])
					s[i][j]=ans[q[d[i][j]]];
				else
					s[i][j]='.';
			}
		}		
	}
	int tt[5],len=0;
	while(!st.empty())
		tt[++len]=st.top(),st.pop();
	reverse(tt+1,tt+len+1);
	rep(i,1,len)
		upd(s,'.',tt[i]);
	rep(i,1,n)
		printf("%s\n",s[i]+1);
}
/*
3 5
C.CB.
.C..C
C.C..
8
GLDPGLDP


*/
bool M2;
signed main() {
	//file_IO();
	int testcase=1;
	//scanf("%d",&testcase);
	while(testcase--)
		solve();
	fprintf(stderr,"used time = %ldms\n",1000*clock()/CLOCKS_PER_SEC);
	fprintf(stderr,"used memory = %lldMB\n",(&M2-&M1)/1024/1024);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...