专栏文章

题解：B4322 [科大国创杯小学组 2025] 正方形划分

CCharles_with_wkc
B4322题解参与者 9已保存评论 22

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
22 条
当前快照
1 份
快照标识符
@mipjcsfx
此快照首次捕获于
2025/12/03 12:57
3 个月前
此快照最后确认于
2025/12/03 12:57
3 个月前
查看原文

思路

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

op=1op = 1

我这里考虑如下 我们发现每有一个字母题目就会去掉 34\frac{3}{4} 的数据。我们一次分析 44 种字母。这里我们定义 44 个变量。
CPP
int l1=1,l2=(1<<n),r1=1,r2=(1<<n);
这四个变量的作用是看这个 strstr 在那个范围内，等我们搜完了以后，答案一定是 l1l_1 和 r1r_1。（这里算到最后 l1=l2l_1 = l_2，r1=r2r_1 = r_2）
我们还需要算一下，答案在第几轮，但是这个比较好算。我们这里定义 strstr 长度为 ll，那么 strstr 在第 ll 轮出现，因为每次都会翻倍增长。
至于，上面的 1<<n 这个是位运算，为 2n2^n。这里也清晰易懂，每轮都是翻倍增长的，所以，第 nn 轮，矩阵一定是 2n×2n2^n \times 2^n 大小的。
这里定义一个特殊的变量 pylpyl 意为偏移量。为什么需要这个变量下面会说。这你先说一下 pylpyl 的变化，初始的时候 pyl=1<<(n-1) 因为，我这里不停的缩小答案范围，我们对于 pylpyl 的初值，进行举例说明。（详细见下）我们 pylpyl 每次都是要 ÷2\div 2 的。（详细见下） 还用这个图。 现在，我们检测到第一个字符为 AA。我们知道如果第一个字母为 AA，那么这个字符串，一定就在左上角。（如图）
我们刚开始设置了 44 个变量，是控制答案范围的。这里显然，l1l_1 和 r1r_1 都是对的，但是 l2l_2 和 r2r_2 需要调整。
r2r_2 在 (1,4)(1,4) 的位置，但是他应该在 (1,2)(1,2) 这里需要减 22。同理，l2l_2 也需要减 22。（22 怎么来的，见下文） 比如，说我第 22 个检测到了又检测到了 AA，但是这次 l2l_2 和 r2r_2 都是需要减 11 了。
对比，两次举例，我们发现 1×2=21 \times 2 = 2，如果按照这个规律，第 33 轮时，这里第一次应该减 44。（可以自己画图）
根据以上的内容，我们容易发现在第 ii 层的时候自然就会减 2i−12^{i-1}，这个就是我们前面定义的 pylpyl。
总结一下。（以下 sis_i 表示 strstr 的第 ii 个字符）
当 sis_i 为 AA 时（如下）
CPP
l2-=pyl
r2-=pyl
当 sis_i 为 BB 时（如下）
CPP
l1+=pyl
r2-=pyl
当 sis_i 为 CC 时（如下）
CPP
l2-=pyl
r1+=pyl
当 sis_i 为 DD 时（如下）
CPP
l1+=pyl
r1+=pyl
恭喜你，op=1op = 1 正确了。

op=2op = 2

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

代码

CPP
#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;
}

评论

共 22 条评论，欢迎与作者交流。

正在加载评论...