P9262
lsj2009
·
·
题解
Description
有一个大小 n\times m 的矩阵（有些地方有东西，有些地方为空），有 q 次操作，每次操作会改变整个矩阵的 重力方向（仅限于上下左右）。
即矩形上的所有东西都朝着重力方向移动直到遇到边界或者遇到其他物品（想一下 2048 小游戏？）
求 q 操作之后的矩阵长什么样子。
1.00s，512MB。
## Solution
我们首先消去连续的同一方向类型（上下为一类型，左右为一类型）的操作，再删去间隔一位的相同操作，会发现最终只剩下开头（要把所有东西搞到角落）、结尾的 $\mathcal{O}(1)$ 次操作和 $\mathcal{O}(k)$ 次「转圈」。
其中 $\mathcal{O}(1)$ 次操作可以暴力做，考虑如何快速做「转圈」。
注意到「转圈」有不同种类（如右下左上和下右上左是不同的），但总归只有 $\mathcal{O}(1)$ 种，并且「转圈」具有 **交换律**，也就是我先转那个圈还是先转这个圈是无所谓的（想想证明？这很重要。），所以我们把相同种类的转圈归到一起做就好了。
Observation：**进行一轮「转圈」之后，物品的轮廓是不变的。**
手摸一下还是比较显然的。这里其实也就解释了「转圈」具有交换律的原因。
则由于轮廓不变，**所以每次一个位置 $(x,y)$ 在转一圈后去到的位置 $P_{(x,y)}$ 是一致的**
事实上 $P$ 是一个置换，则转 $k$ 次后 $(x,y)$ 就会去到 $P^k_{(x,y)}$，**问题转换为求置换的 $k$ 次方**，可以直接把置换环拉出来然后拿出每个点往后 $k$ 个点的位置即可；或者注意到置换具有结合律，跑一个快速幂即可。
两种实现，前者复杂度为 $\mathcal{O}(nm+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;
}
```