题目标题都不会读，我太蕈了

题意

概括了一下，将就着看。

有一幅

n\times m

的画，每个像素上有一个颜色，有三种操作：

选择一个 $2\times2$ 的区域，将其像素顺时针旋转。
交换相邻的两个像素。
对于一个 $h_i\times w_i$ 的区域，替换成配方列表中的另一个画面。

现在给定你初始的画和

k

种配方，构造一个方案，在使用不大于

400

次替换操作，且总步数在

4\times10^5

步内使其变为另一幅给定的画。

n,m,k\le 20,|\Sigma|\le62

。

思路

不拿发现旋转操作可以用

O(1)

次原地交换解决，所以先不考虑这种操作，除非上界卡得很死。

然后发现正着做操作和状态非常的多。此时考虑离线下来，时光倒流（本人昨天考试才碰到了这个 trick），从最终画面倒着考虑。

那么交换操作显然在新意义下不变。

于是替换操作就变成了每次找到一个配方列表的画面，然后使用这个配方，然后这些字符的取值我们就不关心了（不管原来是什么，总之被覆盖后就是对应的颜色），可以理解为变成了通配符 *。

综上，每次枚举每个配方，判断字符数量够不够使用这个配方（注意通配符也要算进去），然后：

如果通配符数量不能增加，也就是全用通配符进行的替换，那么这个操作显然无意义。
否则找一个位置，把对应的字符挪过去，拼成那个配方，随后将其全部替换成通配符 *。

不妨将初始局面也看成一个配方，每次判断初始局面能不能被使用。

最后别忘了把操作序列倒序输出。

然后这道题就成小模拟了，稍微用一点时间就写完了。

分析

对于我们上面的操作，分析一下是否符合题目要求的上界。

由于每次都能将至少一个字符转化成通配符，所以只会使用

O(nm)

次配方，而把每个字符移动到我们想要的位置需要

O(n+m)

步，每个字符只会被尝试移动

O(k)

次。

所以只会使用

O(nm)\le400

次替换操作，符合题意。

所以只会使用

O(nmk(n+m))\le4\times 10^5

次替换操作，符合题意。

所以你会发现前面提到的“找一个位置”根本不用可以特殊考虑，实际代码中直接无脑找的左上角。同时这个“旋转操作”十分没用，当作没有就行了。

由于

n,m,k,|\Sigma|

都很小，就不分析总时间复杂度了，随便实现都应该不会 T。

代码

代码难度并不高，感觉似乎没有黑？

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+10,maxm=4e5+10;
char c[maxn][maxn][maxn],b[maxn][maxn],(&a)[maxn][maxn]=c[0];
int h[maxm],w[maxm],vis[maxn][maxn],&n=h[0],&m=w[0],k;
struct opt{int op,x,y;}ans[maxm];int cnt[128],tot;
int check(int k){
	memset(cnt,0,sizeof cnt);
	int res=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cnt[b[i][j]]++;
	for(int i=1;i<=h[k];i++){
		for(int j=1;j<=w[k];j++){
			if(cnt[c[k][i][j]])cnt[c[k][i][j]]--,res++;
			else if(cnt['*'])cnt['*']--;
			else return -1;
		}
	}
	return res;
}
void solve(int k){
	memset(vis,0,sizeof vis);
	for(int i=1;i<=h[k];i++){
		for(int j=1;j<=w[k];j++){
			int x=0,y=0;
			for(int l=1;l<=n;l++){
				if(x||y)break;
				for(int r=1;r<=m;r++)
					if(!vis[l][r]&&b[l][r]==c[k][i][j]){x=l,y=r;break;}
			}
			for(int l=1;l<=n;l++){
				if(x||y)break;
				for(int r=1;r<=m;r++)
					if(!vis[l][r]&&b[l][r]=='*'){x=l,y=r;break;}
			}
			while(x<i)swap(b[x][y],b[x+1][y]),ans[++tot]={-3,x++,y};
			while(y<j)swap(b[x][y],b[x][y+1]),ans[++tot]={-1,x,y++};
			while(x>i)swap(b[x][y],b[x-1][y]),ans[++tot]={-4,x--,y};
			while(y>j)swap(b[x][y],b[x][y-1]),ans[++tot]={-2,x,y--};
			vis[i][j]=1;
		}
	}
	for(int i=1;i<=h[k];i++)
		for(int j=1;j<=w[k];j++)
			b[i][j]='*';
	if(k)ans[++tot]={k,1,1};
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>b[i][j];
	for(int i=1;i<=k;i++){
		cin>>h[i]>>w[i];
		for(int j=1;j<=h[i];j++)
			for(int l=1;l<=w[i];l++)
				cin>>c[i][j][l];
	}
	while(!~check(0)){
		bool f=1;
		for(int i=1;i<=k;i++)
			if(check(i)>0)f=0,solve(i);
		if(f){cout<<-1;return 0;}
	}
	solve(0);
	cout<<tot<<'\n';
	for(int i=tot;i>=1;i--){
		auto [op,x,y]=ans[i];
		cout<<op<<' '<<x<<' '<<y<<'\n';
	}
	return 0;
}

题目标题都不会读，我太蕈了

文章操作

题意

思路

分析

代码

相关推荐

评论

题目标题都不会读，我太蕈了