自动搬运

查看原文

来自洛谷，原作者为

	Charles_with_wkc 康庄大道，成就梦想。||加油！努力！一切为了“它” “它” 和 他！ ----wkc

搬运于2025-08-24 21:18:38，当前版本为作者最后更新于2025-04-21 21:08:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

个人认为 $op = 1$ 非常简单，所以我们先讲 $op = 1$。

$op = 1$

我这里考虑如下 我们发现每有一个字母题目就会去掉 $\frac{3}{4}$ 的数据。我们一次分析 $4$ 种字母。这里我们定义 $4$ 个变量。

int l1=1,l2=(1<<n),r1=1,r2=(1<<n);

这四个变量的作用是看这个 $str$ 在那个范围内，等我们搜完了以后，答案一定是 $l_1$ 和 $r_1$。（这里算到最后 $l_1 = l_2$，$r_1 = r_2$）
我们还需要算一下，答案在第几轮，但是这个比较好算。我们这里定义 $str$ 长度为 $l$，那么 $str$ 在第 $l$ 轮出现，因为每次都会翻倍增长。
至于，上面的 1<<n 这个是位运算，为 $2^n$。这里也清晰易懂，每轮都是翻倍增长的，所以，第 $n$ 轮，矩阵一定是 $2^n \times 2^n$ 大小的。
这里定义一个特殊的变量 $pyl$ 意为偏移量。为什么需要这个变量下面会说。这你先说一下 $pyl$ 的变化，初始的时候 pyl=1<<(n-1) 因为，我这里不停的缩小答案范围，我们对于 $pyl$ 的初值，进行举例说明。（详细见下）我们 $pyl$ 每次都是要 $\div 2$ 的。（详细见下） 还用这个图。 现在，我们检测到第一个字符为 $A$。我们知道如果第一个字母为 $A$，那么这个字符串，一定就在左上角。（如图）
我们刚开始设置了 $4$ 个变量，是控制答案范围的。这里显然，$l_1$ 和 $r_1$ 都是对的，但是 $l_2$ 和 $r_2$ 需要调整。
$r_2$ 在 $(1,4)$ 的位置，但是他应该在 $(1,2)$ 这里需要减 $2$。同理，$l_2$ 也需要减 $2$。（$2$ 怎么来的，见下文） 比如，说我第 $2$ 个检测到了又检测到了 $A$，但是这次 $l_2$ 和 $r_2$ 都是需要减 $1$ 了。
对比，两次举例，我们发现 $1 \times 2 = 2$，如果按照这个规律，第 $3$ 轮时，这里第一次应该减 $4$。（可以自己画图）
根据以上的内容，我们容易发现在第 $i$ 层的时候自然就会减 $2^{i-1}$，这个就是我们前面定义的 $pyl$。
总结一下。（以下 $s_i$ 表示 $str$ 的第 $i$ 个字符）
当 $s_i$ 为 $A$ 时（如下）

l2-=pyl
r2-=pyl

当 $s_i$ 为 $B$ 时（如下）

l1+=pyl
r2-=pyl

当 $s_i$ 为 $C$ 时（如下）

l2-=pyl
r1+=pyl

当 $s_i$ 为 $D$ 时（如下）

l1+=pyl
r1+=pyl

恭喜你，$op = 1$ 正确了。

$op = 2$

通过 $op =1$ 的思路，我们不难想出，可以将上面的反过来，然后暴力判断在那个范围内。

代码

#include<bits/stdc++.h>
using namespace std;
long long t,x,y,l,nl1,nl2,nr1,nr2;
bool op,f;
string s;
void dfs1(long long id,long long l1,long long l2,long long r1,long long r2,long long pyl){
	if(f) return ;
	if(id==l){
		f=1;
		x=r1;
		y=l1;
		//我比较脑残写dfs1和dfs2的时候x和y写反了，将就看 
		//因为找到了以后l1=l2,r1=r2是一定的，所以无所谓 
		return ;
	}
	if(s[id]=='A') dfs1(id+1,l1,l2-pyl,r1,r2-pyl,pyl/2);
	else if(s[id]=='B') dfs1(id+1,l1+pyl,l2,r1,r2-pyl,pyl/2);
	else if(s[id]=='C') dfs1(id+1,l1,l2-pyl,r1+pyl,r2,pyl/2);
	else dfs1(id+1,l1+pyl,l2,r1+pyl,r2,pyl/2);
	return ;
}
void dfs2(long long id,long long l1,long long l2,long long r1,long long r2,long long pyl){
	if(f) return ;
	if(id==l){
		f=1;//找到了 
		return ;
	}
	//A
	nl1=l1;
	nl2=l2-pyl;
	nr1=r1;
	nr2=r2-pyl;
	if(nl1<=x&&x<=nl2&&nr1<=y&&y<=nr2){
		s+='A';
		dfs2(id+1,l1,l2-pyl,r1,r2-pyl,pyl/2);
	}
	//B
	nl1=l1+pyl;
	nl2=l2;
	nr1=r1;
	nr2=r2-pyl;
	if(nl1<=x&&x<=nl2&&nr1<=y&&y<=nr2){
		s+='B';
		dfs2(id+1,l1+pyl,l2,r1,r2-pyl,pyl/2);
	}
	//C
	nl1=l1;
	nl2=l2-pyl;
	nr1=r1+pyl;
	nr2=r2;
	if(nl1<=x&&x<=nl2&&nr1<=y&&y<=nr2){
		s+='C';
		dfs2(id+1,l1,l2-pyl,r1+pyl,r2,pyl/2);
	}
	//D 
	nl1=l1+pyl;
	nl2=l2;
	nr1=r1+pyl;
	nr2=r2;
	if(nl1<=x&&x<=nl2&&nr1<=y&&y<=nr2){
		s+='D';
		dfs2(id+1,l1+pyl,l2,r1+pyl,r2,pyl/2);
	}
	return ;
}
int main(){
	/*
	考场freopen 
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	*/
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>op;
		if(op==1){
			cin>>s;
			l=s.size();
			cout<<l<<" ";
			f=0;
			dfs1(0,1,1<<l,1,1<<l,1<<(l-1));
			cout<<x<<" "<<y<<" "<<endl;
		}
		else{
			cin>>l>>x>>y;
			swap(x,y);
			//我比较脑残写dfs1和dfs2的时候x和y写反了，将就看 
			f=0;
			s="";
			//多测不清空，全WA等着哭 
			dfs2(0,1,1<<l,1,1<<l,1<<(l-1));
			cout<<s<<endl;
		}
	}
	return 0;
}