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

· · 题解

思路

个人认为 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 需要调整。

比如，说我第 $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$ 时（如下） ```cpp l2-=pyl r2-=pyl ``` 当 $s_i$ 为 $B$ 时（如下） ```cpp l1+=pyl r2-=pyl ``` 当 $s_i$ 为 $C$ 时（如下） ```cpp l2-=pyl r1+=pyl ``` 当 $s_i$ 为 $D$ 时（如下） ```cpp 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;
}