二分写法

shaoxqy · 2025-04-27 12:15:06 · 题解

由于本人编程技术不够精湛，所以以数学思维思考。

思路

我们观察可以发现，对于第 n 级表格，它是一个边长为 2^n 的正方形表格。

每一级都是在上一级的最小格子内，划分为 2*2 的表格。

这么多 2 让我想起二分法，于是本人的写法由此引申出来了。

第一种情况

分析：根据它所给的层数和坐标，输出这个格子的编号。

做法：我们从高到低逐级判断，只考虑该层 2*2 表格的情况； p 为这一级的权重。

1. 如果横坐标大于权重的一半，则说明其在右半表格。
2. 如果横坐标小于等于权重的一半，则说明其在左半表格。
3. 如果纵坐标大于权重的一半，则说明其在下半表格。
4. 如果纵坐标小于等于权重的一半，则说明其在上半表格。

综合一下：

1. 左上角，输出 A。
2. 右上角，输出 B。
3. 左下角，输出 C。
4. 右下角，输出 D。

   if(m==0){
           cin>>n>>x>>y;
           w=n;
           for(int i=1;i<=n;i++){
               p=f(2,w);//2的w次方 
               if(x%p==0){
                   x=p;
               }
               else{
                   x%=p;
               }
               if(y%p==0){
                   y=p;
               }
               else{
                   y%=p;
               }//预处理
               if(2*y<=p&2*x<=p){
                   cout<<"A";
               }
               if(2*y>p&2*x<=p){
                   cout<<"B";
               }
               if(2*y<=p&2*x>p){
                   cout<<"C";
               }
               if(2*y>p&2*x>p){
                   cout<<"D";
               }//输出
               w--;//判断下一级
           }
           cout<<endl;
       }

   第二种情况

   分析：根据它所给的编号，输出这个格子的层数和坐标。

做法： n 没什么好说的，输出字符串长度即可。

坐标的话，可以使用二分的思路。

横坐标：

• 定义左边界 l ，右边界 r
  1. 输入的字符为 A 或 C，则将右边界 r 移至 (r+l)/2 处。
  2. 输入的字符为 B 或 D，则将左边界 l 移至 (r+l)/2+1 处。

纵坐标：

• 定义上边界 u ，下边界 d
  1. 输入的字符为 A 或 B，则将下边界 d 移至 (d+u)/2处。
  2. 输入的字符为 C 或 D，则将左边界 l 移至 (d+u)/2+1 处。

else{
            cin>>s1;
            n=s1.length();
            cout<<n<<" ";
            p=f(2,n);
            for(int i=1;i<=n;i++){
                arr[i]=s1.at(i-1);
            }
            int u=1,l=1,d=p,r=p;
            for(int i=1;u<d;i++){
                if(arr[i]=='A'||arr[i]=='B'){
                    d=(d+u)/2;
                }
                else{
                    u=(d+u)/2+1;
                }
            }
            for(int i=1;l<r;i++){
                if(arr[i]=='A'||arr[i]=='C'){
                    r=(r+l)/2;
                }
                else{
                    l=(r+l)/2+1;
                }
            }
            cout<<u<<" "<<l<<endl;
        }

献上完整代码

#include<iostream>
#include<string>
using namespace std;

char arr[35];

int f(int x,int y){
    int z=x;
    while(y>1){
        z=z*x;
        y--;
    }
    return z;
}

int main(){
    int T,m,n,x,y,w,p;
    string s1;
    cin>>T;
    while(T--){
        cin>>m;
        if(m==0){
            cin>>n>>x>>y;
            w=n;
            for(int i=1;i<=n;i++){
                p=f(2,w);//2的w次方 
                if(x%p==0){
                    x=p;
                }
                else{
                    x%=p;
                }
                if(y%p==0){
                    y=p;
                }
                else{
                    y%=p;
                }
//              cout<<endl<<x<<"　"<<y<<endl;
                if(2*y<=p&2*x<=p){
                    cout<<"A";
                }
                if(2*y>p&2*x<=p){
                    cout<<"B";
                }
                if(2*y<=p&2*x>p){
                    cout<<"C";
                }
                if(2*y>p&2*x>p){
                    cout<<"D";
                }
                w--;
            }
            cout<<endl;
        }
        else{
            cin>>s1;
            n=s1.length();
            cout<<n<<" ";
            p=f(2,n);
            for(int i=1;i<=n;i++){
                arr[i]=s1.at(i-1);
            }
            int u=1,l=1,d=p,r=p;
            for(int i=1;u<d;i++){
                if(arr[i]=='A'||arr[i]=='B'){
                    d=(d+u)/2;
                }
                else{
                    u=(d+u)/2+1;
                }
            }
            for(int i=1;l<r;i++){
                if(arr[i]=='A'||arr[i]=='C'){
                    r=(r+l)/2;
                }
                else{
                    l=(r+l)/2+1;
                }
            }
            cout<<u<<" "<<l<<endl;
        }
    }
    return 0; 
}