P9262 [PA 2022] ?amig?ówka 題解

知識(shí)點(diǎn)

貪心，模擬。

分析

首先知道暴力可以直接 \(O(nmK)\) 的解決。

簡(jiǎn)化操作序列

發(fā)現(xiàn)對(duì)于操作序列中，連在一起的 LL 等相同的字符可以縮掉，然后再進(jìn)一步發(fā)現(xiàn)，如果同是水平方向的操作（L、P）挨在一起，那么只需要留最后一個(gè)即可，例如 LPLPLPLLLPLPL 保留 L。那么對(duì)于豎直方向的 G、D 也是同理。

現(xiàn)在操作序列相鄰的操作方向不可能平行，例如 LGLGPD，但是我們發(fā)現(xiàn)還可以簡(jiǎn)化，比如中間 LGL 的部分，發(fā)現(xiàn)可以證明右邊那個(gè) L 是無(wú)效的，其余也是類似。

所以我們得到了兩條簡(jiǎn)化操作序列的規(guī)則：

1. 連續(xù)的方向平行的操作只保留最后一個(gè)。
2. 如果這次操作與上一次方向平行的操作相同，那么可以直接忽略。

這個(gè)過(guò)程可以用棧來(lái)實(shí)現(xiàn)。

循環(huán)節(jié)性質(zhì)

發(fā)現(xiàn)簡(jiǎn)化完的操作序列一定是四個(gè)方向操作按某個(gè)順序各做一次作為循環(huán)節(jié)，然后多次重復(fù)形成的一個(gè)循環(huán)，最后可能還有多 \(1\sim 3\) 個(gè)操作。證明也較簡(jiǎn)單，只需根據(jù)上面兩條規(guī)則即可。

我們定義矩形狀態(tài)“點(diǎn)全部在矩形一角”為：做往這個(gè)角兩種方向的操作，內(nèi)部的字母不會(huì)移動(dòng)。例如，當(dāng)“點(diǎn)全部在矩形左上角”，那么做 L，G 操作是無(wú)效的。

那么我們把這個(gè)循環(huán)節(jié)拆出來(lái)，就發(fā)現(xiàn)：如果點(diǎn)全部在矩形一角，那么做一遍循環(huán)節(jié)上的操作（后稱為“循環(huán)節(jié)變換”），原本有字母的位置還是有字母，沒(méi)有字母的位置還是沒(méi)有字母，但是中間字母的位置是變換的。

我們考慮把矩陣的每個(gè)有字母的點(diǎn)放入一張圖，那么這個(gè)點(diǎn)在經(jīng)過(guò)循環(huán)節(jié)變換后會(huì)到達(dá)另一個(gè)點(diǎn)，我們連一條單向邊。發(fā)現(xiàn)每個(gè)點(diǎn)有一條出邊和一條入邊，所以整張圖就形成了一堆簡(jiǎn)單環(huán)。

那么我們只要做一點(diǎn)邊界處理，然后在環(huán)上對(duì)操作數(shù)取個(gè)模就可以找到答案。

邊界處理

由于上述性質(zhì)是基于“點(diǎn)全部在矩形一角”這個(gè)狀態(tài)，我們可以取出少量的操作先暴力做，剩下的操作再放入循環(huán)節(jié)，這樣性質(zhì)是不變的。取出的操作次數(shù)至少為兩次，可以在這里把循環(huán)節(jié)之外多的 \(1\sim 3\) 個(gè)操作一并處理掉。

那么就可以分情況處理：（設(shè) \(Q\) 為簡(jiǎn)化后的操作序列長(zhǎng)度）

1. \(Q\le 8\)：那么直接全部暴力處理。
2. \(Q>8\)：取出前 \(4+Q\bmod 4\) 次操作暴力做，后面的將環(huán)處理出來(lái)，然后再在環(huán)上對(duì)操作次數(shù)取模即可找到最終轉(zhuǎn)移點(diǎn)。

代碼

復(fù)雜度 \(O(nm)\)。代碼寫得稍有凌亂，但是總體還算簡(jiǎn)潔。

constexpr int N(5e2+10),M(2.5e5+10),Qr(5e5+10);

bool vis[M];
char s[Qr];
int Cas,n,m,t,Q;
int fa[M];
int a[N][N],b[N][N],idx[N][N];

int X(int u) { return (u-1)/m+1; }

int Y(int u) { return u%m?u%m:m; }

int ID(int x,int y) { return (x-1)*m+y; }

void Up(int a[N][N]) {
	FOR(j,1,m) {
		int tmp(0);
		FOR(i,1,n)if(~a[i][j]) {
			int num(a[i][j]);
			a[i][j]=-1,a[++tmp][j]=num;
		}
	}
}

void Down(int a[N][N]) {
	FOR(j,1,m) {
		int tmp(n+1);
		DOR(i,n,1)if(~a[i][j]) {
			int num(a[i][j]);
			a[i][j]=-1,a[--tmp][j]=num;
		}
	}
}

void Left(int a[N][N]) {
	FOR(i,1,n) {
		int tmp(0);
		FOR(j,1,m)if(~a[i][j]) {
			int num(a[i][j]);
			a[i][j]=-1,a[i][++tmp]=num;
		}
	}
}

void Right(int a[N][N]) {
	FOR(i,1,n) {
		int tmp(m+1);
		DOR(j,m,1)if(~a[i][j]) {
			int num(a[i][j]);
			a[i][j]=-1,a[i][--tmp]=num;
		}
	}
}

int Output(int a[N][N]) {
	FOR(i,1,n) {
		FOR(j,1,m)putchar(~a[i][j]?'a'+a[i][j]:'.');
		putchar('\n');
	}
	return 0;
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	/*DE("Input");*/
	I(n,m),t=n*m;
	FOR(i,1,n)FOR(j,1,m)a[i][j]=b[i][j]=idx[i][j]=-1;
	FOR(i,1,n) {
		scanf("%s",s+1);
		FOR(j,1,m)if(s[j]!='.')a[i][j]=s[j]-'a';
	}
	/*DE("Query");*/
	int tmp(0);
	I(tmp),scanf("%s",s+1),Q=0;
	auto typ=[&](char a) { return a=='L'||a=='P'; };
	FOR(i,1,tmp) {
		char c(s[i]);
		while(Q&&typ(s[Q])==typ(c))--Q;
		if(Q<2||s[Q-1]!=c)s[++Q]=c;
	}
	/*DE("Check");*/
	if(Q<=8) {
		FOR(i,1,Q)s[i]=='L'?Left(a):(s[i]=='P'?Right(a):(s[i]=='G'?Up(a):Down(a)));
		return Output(a);
	}
	/*DE("Build");*/
	tmp=4+Q%4;
	FOR(i,1,tmp)s[i]=='L'?Left(a):(s[i]=='P'?Right(a):(s[i]=='G'?Up(a):Down(a)));
	Q-=tmp;
	FOR(i,1,Q)s[i]=s[i+tmp];
	FOR(i,1,n)FOR(j,1,m)if(~a[i][j])idx[i][j]=ID(i,j);
	FOR(i,1,4)s[i]=='L'?Left(idx):(s[i]=='P'?Right(idx):(s[i]=='G'?Up(idx):Down(idx)));
	Q/=4;
	FOR(i,1,n)FOR(j,1,m)if(~idx[i][j])fa[idx[i][j]]=ID(i,j);
	/*DE("Trans");*/
	FOR(i,1,n)FOR(j,1,m)if(~a[i][j]&&!vis[ID(i,j)]) {
		const int u(ID(i,j));
		vector<int> tmp {u};
		for(int v(fa[u]); v&&v!=u; v=fa[v])tmp.push_back(v),vis[v]=true;
		int y(Q%tmp.size());
		for(int x:tmp)b[X(tmp[y])][Y(tmp[y])]=a[X(x)][Y(x)],y=(y+1)%tmp.size();
	}
	/*DE("Output");*/
	return Output(b);
}