P11113 [ROI 2024] 2026 (Day 1) 題解

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

貪心，模擬。

分析

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

簡(jiǎn)化操作序列

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

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

所以我們得到了兩條簡(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，U 操作是無(wú)效的。

那么我們把這個(gè)循環(huán)節(jié)拆出來(lái)，就發(fā)現(xiàn)：如果點(diǎn)全部在矩形一角，那么做一遍循環(huán)節(jié)上的操作（后稱(chēng)為“循環(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(\sum nm)\)。代碼寫(xiě)得稍有凌亂，但是總體還算簡(jiǎn)潔。

constexpr int N(1e6+10);

bool vis[N];
char s[N];
int Cas,n,m,t,Q;
int fa[N];
vector<int> a[N],b[N],idx[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(vector<int> *a) {
	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(vector<int> *a) {
	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(vector<int> *a) {
	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(vector<int> *a) {
	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(vector<int> *a) {
	FOR(i,1,n) {
		FOR(j,1,m)putchar(~a[i][j]?'a'+a[i][j]:'.');
		putchar('\n');
	}
	return 0;
}

int Cmain() {
	/*DE("Input");*/
	I(n,m),t=n*m;
	FOR(i,1,n) {
		scanf("%s",s+1),a[i]=vector<int>(m+1,-1);
		FOR(j,1,m)if(s[j]!='.')a[i][j]=s[j]-'a';
	}
	/*DE("Query");*/
	scanf("%s",s+1),Q=0;
	int tmp(strlen(s+1));
	auto typ=[&](char a) { return a=='L'||a=='R'; };
	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]=='R'?Right(a):(s[i]=='U'?Up(a):Down(a)));
		return Output(a);
	}
	/*DE("Build");*/
	tmp=4+Q%4;
	FOR(i,1,tmp)s[i]=='L'?Left(a):(s[i]=='R'?Right(a):(s[i]=='U'?Up(a):Down(a)));
	Q-=tmp;
	FOR(i,1,Q)s[i]=s[i+tmp];
	FOR(i,1,n) {
		idx[i]=vector<int>(m+1,-1);
		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]=='R'?Right(idx):(s[i]=='U'?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)b[i]=vector<int>(m+1,-1);
	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);
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	for(I(Cas); Cas; --Cas) {
		Cmain();
		/*DE("Clear");*/
		FOR(i,1,t)vis[i]=false;
		FOR(i,1,n)a[i].clear(),b[i].clear(),idx[i].clear();
	}
	return 0;
}