题解：P11113 [ROI 2024 Day 1] 2026
第一回交题解，写的不好请见谅qaq
我们很容易可以发现以下三点
1 . 对于 LL 这种连续两个相同，可以只保留一个，即 LL；
2 . 对于 LR 这种，可以只保留后面那个，即 LR；
3 . 对于 LUL 这种前后两个相同的，可以只保留前面那个，即 LRL
(第三个如果没看出来建议自己手动模拟一下)
那么如果有一个已经确定的 LU，后面为了不被消掉就只能接 R，递推下去得到 LURDLURD...容易看出来是在顺时针循环操作。同理可得也可以 LDRULDRU 地逆时针操作。那么在经过以上方式消除后，剩下的操作就变成了许多次的周期为4的循环。
这里消除操作我采用的是双向链表，在经过化简后的暴力可以拿到 43pts 的好成绩。
在知道剩下的操作序列是循环后，容易想到倍增优化，即算出一个循环会造成的影响，使用链表存储，然后倍增即可。
举例
abcdef...
ghijk....
lm.......
.........这么一个矩阵在经过一次逆时针操作后会变成
lghcab...
mijde....
kf.......
.........发现阶梯形状是一样的，只是位置变了，链表存储操作一周期后会走到哪个位置即可。
Talk is cheap,show me the code
码风魔鬼，谨慎入内
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define sfor(i,j,k) for(register int i=j;i<=k;++i)
#define dfor(i,j,k) for(register int i=k;i>=j;--i)
inline int read(){
register int x = 0, t = 1;
register char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
t=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*t;
}
inline void write(int x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
string s[2000006];
int ans[2000006],cyj[2000006],tto[2000006],pre[2000006],aft[2000006],n,m,f[2][2000006],la=0,sg=1,z[2000006],ca[2000006],fi[2000006];
inline int getnum(int x,int y) {return x*m+y-m;}
inline void U()
{sfor(i,1,n*m) f[sg][i]=0;
sfor(j,1,m)
{int tt=0;
sfor(i,1,n) if(f[la][getnum(i,j)]) z[++tt]=f[la][(getnum(i,j))];
sfor(i,1,tt) f[sg][getnum(i,j)]=z[i];}
swap(la,sg);return;
}
inline void D()
{sfor(i,1,n*m) f[sg][i]=0;
sfor(j,1,m)
{int tt=0;
dfor(i,1,n) if(f[la][getnum(i,j)]) z[++tt]=f[la][(getnum(i,j))];
sfor(i,1,tt) f[sg][getnum(n+1-i,j)]=z[i];}
swap(la,sg);return;
}
inline void L()
{sfor(i,1,n*m) f[sg][i]=0;
sfor(i,1,n)
{int tt=0;
sfor(j,1,m) if(f[la][getnum(i,j)]) z[++tt]=f[la][(getnum(i,j))];
sfor(j,1,tt) f[sg][getnum(i,j)]=z[j];}
swap(la,sg);return;
}
inline void R()
{sfor(i,1,n*m) f[sg][i]=0;
sfor(i,1,n)
{int tt=0;
dfor(j,1,m) if(f[la][getnum(i,j)]) z[++tt]=f[la][(getnum(i,j))];
sfor(j,1,tt) f[sg][getnum(i,m+1-j)]=z[j];}
swap(la,sg);return;
}
inline void del(int x)
{pre[aft[x]]=pre[x];
aft[pre[x]]=aft[x];
return;
}
int main()
{
int T=read();
while(T--){
la=0,sg=1;
n=read(),m=read();
sfor(i,1,n*m) tto[i]=0;
sfor(i,1,n) {cin>>s[i];s[i]=' '+s[i];}
sfor(i,1,n)
sfor(j,1,m)
{if(s[i][j]=='.') f[0][getnum(i,j)]=0;
else f[0][getnum(i,j)]=s[i][j]-'a'+1;
}
string cz;
cin>>cz;
int q=cz.size();
cz=' '+cz;
sfor(i,1,q)
{if(cz[i]=='L') ca[i]=0;
if(cz[i]=='R') ca[i]=1;
if(cz[i]=='U') ca[i]=2;
if(cz[i]=='D') ca[i]=3;
}
sfor(i,1,q) pre[i]=i-1,aft[i]=i+1;
aft[q]=0;
aft[0]=1;
int now=1;
ca[0]=-114514;//为了防止和L搞混就随便赋一个错乱的值吧awa
while(now)
{if(aft[now]==0) break;
if(aft[now]!=0&&ca[aft[now]]==ca[now]||ca[pre[now]]==ca[aft[now]])
{del(aft[now]);
continue;}
if(aft[now]!=0&&!(ca[aft[now]]^ca[now]^1))
{del(now);
if(pre[now]!=0) now=pre[now];
else now=aft[now];
continue;}
now=aft[now];
}
int cztt=0;//化简后还剩下多少步
now=aft[0];
while(now)
{fi[++cztt]=ca[now];
now=aft[now];
}
sfor(i,1,min(2,cztt))
{if(fi[i]==0) L();
if(fi[i]==1) R();
if(fi[i]==2) U();
if(fi[i]==3) D();
}
if(cztt>2)
{int lun=(cztt-2)/4,yu=cztt-2-lun*4;
if(lun)
{sfor(i,1,n*m) if(f[la][i]) ans[i]=f[la][i],f[la][i]=i;
sfor(i,3,6)
{if(fi[i]==0) L();
if(fi[i]==1) R();
if(fi[i]==2) U();
if(fi[i]==3) D();}
sfor(i,1,n*m) if(f[la][i]) tto[f[la][i]]=i;
lun--;//开始走一遍了
while(lun)
{if(lun%2)
{sfor(i,1,n*m) f[sg][i]=0;
sfor(i,1,n)
sfor(j,1,m)
f[sg][tto[getnum(i,j)]]=f[la][getnum(i,j)];
swap(la,sg);
}
lun/=2;
sfor(i,1,n*m) cyj[i]=tto[i];
sfor(i,1,n*m) tto[i]=cyj[cyj[i]];
}
sfor(i,1,n*m) if(f[la][i]) f[la][i]=ans[f[la][i]];
}
sfor(i,cztt-yu+1,cztt)
{if(fi[i]==0) L();
if(fi[i]==1) R();
if(fi[i]==2) U();
if(fi[i]==3) D();
}
}
sfor(i,1,n)
{sfor(j,1,m)
if(f[la][getnum(i,j)]==0) cout<<'.';
else cout<<(char)('a'-1+f[la][getnum(i,j)]);
cout<<endl;
}
sfor(i,1,n*m) f[0][i]=f[1][i]=ans[i]=tto[i]=0;//最后清理一下
}
}