二分写法

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

思路

我们观察可以发现，对于第

n

级表格，它是一个边长为

2^n

的正方形表格。

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

2*2

的表格。

这么多

2

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

第一种情况

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

做法：我们从高到低逐级判断，只考虑该层

2*2

表格的情况；

p

为这一级的权重。

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

综合一下：

左上角，输出 A。
右上角，输出 B。
左下角，输出 C。
右下角，输出 D。

CPP

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$

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

纵坐标：

定义上边界 $u$ ，下边界 $d$

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

CPP

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

献上完整代码

CPP

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

文章操作

思路

第一种情况

第二种情况

献上完整代码

相关推荐

评论

二分写法