第六届Code+程序设计网络挑战赛-COORDINATE

题目描述

题目描述

在视频编码中，往往需要将一帧画面分块。

为了简化问题，我们考虑将一幅图片看作 $2^n $ * $ 2^n $的网格。为了对图片进行处理，编码器往往会遍历每个格子，但遍历格子的方式在不同的应用中是不同的。

其中一种方式叫做光栅遍历，就是按照从左到右，从上到下的顺序依次进行标号。下图是一个 8×8 的例子：

另一种方式叫做 Z 字型遍历。先看一个 8×8 的例子：

可以构造性的给出描述：

1.对于$2^0 $ * $ 2^0 $的网格，直接遍历

2.对于$2^k $ * $ 2^k $ (k>0)的网格，将其横着从中间、竖着从中间各分成两半，形成4个$2^{k-1} $ * $ 2^{k-1} $的方格，这四个方格按照左上、右上、左下、右下的顺序依次遍历。

输入格式

输入的第一行为两个整数 n,m ,$2^n$ 为矩形的边长，m 为询问次数。

接下来 m 行，每行是一个询问，询每个询问给出一个方格，方式有两种，如下：

• Z x 给出 Z 字形遍历中标号是 x 的方格。
• R x 给出光栅遍历中标号是 x 的方格。

保证存在标号为x的方格。

输出格式

对于每种询问，请输出一行一个正整数，表示在另一种遍历方式中，给出格子的标号。

样例输入

3 2
Z 37
R 37

样例输出

35
49

解题思路

从题意可知，我们需要找到与输入的排列方格序号位置对应的另一张排列方格位置序号。

我们先从输入R出发进行计算

输入 R x

比如样例R 37，我们可以从题面的图片看出，它所对应的位置为第 4 行第 5 列（初始为第0行第0列，，以下缩写为（x,y））。

我们观察Z遍历可发现，如果我们把方格分成四个小方格，每个方格大小一样，每个位置所对应的值的差是一个值的整数倍。比如对于 49 和 33 ，33 和 17 ，17 和 1 ，他们在小方格中位置相同，差值均为小方格的大小（$ 2^n $ * $ 2^n $ / 4），因此，我们可以根据每个数字所在的方格位置，判断它所在的方格，从而算出它对应的值。

比如，对于（ 4 , 5 ），我们可以看出他所在的方块为第四块（小方块按遍历顺序编号1234），因此我们可以知道在Z中它的值 n >=（$ 2^n $ * $ 2^n $ / 4）* 3 ,所以我们先保存这一部分值，然后将其对应到第一个方格所对应的位置（即行和列均减去边长的一半），因为我们已经将它放在了第一个方格，其他三个方格已经没有作用了，因此我们可以将边长减小为现在的一半。然后重复此步操作。

一次操作后，大方格的已经变成了

而( 4 , 5 )现在所对应的位置为（ 0 ，1），再分成四个小方格后在第一个方格，因此对行和列不操作，边长再减小一半。

现在，他的所对应的位置依然为（ 0 , 1 ）现在的大方格为

所在小方格编号为2，因此列数减去当前边长的一半，保存当前面积（$ 2^1 $ * $ 2^1 $ / 4 * 1）。此时，它的坐标已经变成了（0 ，0），计算结束。

上面进行了三次操作，其大致顺序为：

1.找到坐标对应的小方格编号。

2.把当前坐标移动到第一个小方格，记录移动所改变的值。

3.重复步骤1,2，直到坐标变为（0 , 0）。

4.输出总的改变的值。

比如上面的（ 4 , 5 ），我们三次操作保存的值为$ 2^3 $ * $ 2^3 $ / 4 * 3 = 48 ；0 ； $2^1 $ * $ 2^1 $ / 4 * 1 = 1。加起来的值为49，即最终答案。

这就是输入为R时的计算方法。

代码如下：

ll i=x/line; //当前所在行
ll j=x%line; //当前所在列
ll res=0;
ll l=line*line/4; //line为边长，l为一个小方格的面积
ll fen=line/2; //fen为每个小方格的边长
while(i>0 || j>0){
	if(j>=fen && i<fen){ //表示在第二个小方格
		j-=fen; //
		res+=l; //储存当前操作所改变的值
	}
	else if(i>=fen && j<fen){ //表示在第三个小方格
		i-=fen;
		res+=l*2;
	}
	else if(i>=fen && j>=fen){ //表示在第四个小方格
		i-=fen;
		j-=fen;
		res+=l*3;
	}
	fen/=2;//将方块边长缩为原来的1/2,面积缩为原来的1/4
	l/=4;
}
printf("%lld\n",res);

输入Z x

输入R时是根据行和列判断最终值，而输入Z时正好相反，根据x的值判断所在行和列。

我们如果知道x的大小，就可以判断它所在的小方格编号，因此也可以层层求出行和列的值。

代码如下：

ll sumx=0,sumy=0; //储存行和列
l=line*line/4; //同上
ll fen=line/2; //同上
while(x>0){
	if(x/l==1){//根据值可判断出所在的小方格，从而判断出行和列应该加的值
		sumy+=fen;
		x-=l;//减去对应的值，即上面的将坐标移动到第一个小方格
	}
	else if(x/l==2){
		sumx+=fen;
		x-=l*2;
	}
	else if(x/l==3){
		sumx+=fen;
		sumy+=fen;
		x-=l*3;
	}
	fen/=2; //同上
	l/=4;
}

这样，我们就可以求出所有的值了。

完整代码如下（做题时提交代码）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int,int>
int main()
{
	ll n,m;
	char op;
	ll x;
	ll i,j;
	scanf("%lld %lld",&n,&m);
	ll line=1;
	for(ll i=0;i<n;i++) line*=2;
//	printf("%lld %lld",line,(ll)pow(2,n));
//  当时使用pow()提交wa了一次，改后ac了，可能精度有问题 
	while(m--){
		ll l;
		getchar();
		scanf("%c %lld",&op,&x);
		if(op=='Z'){
			ll sumx=0,sumy=0;
			l=line*line/4;
			ll fen=line/2;
			while(x>0){
				if(x/l==1){
					sumy+=fen;
					x-=l;
				}
				else if(x/l==2){
					sumx+=fen;
					x-=l*2;
				}
				else if(x/l==3){
					sumx+=fen;
					sumy+=fen;
					x-=l*3;
				}
				fen/=2;
				l/=4;
			}
			printf("%lld\n",sumx*line+sumy);
		}
		else if(op=='R'){
			i=x/line;
			j=x%line;
			ll res=0;
			l=line*line/4;
			ll fen=line/2;
			while(i>0 || j>0){
				if(j>=fen && i<fen){
					j-=fen;
					res+=l;
				}
				else if(i>=fen && j<fen){
					i-=fen;
					res+=l*2;
				}
				else if(i>=fen && j>=fen){
					i-=fen;
					j-=fen;
					res+=l*3;
				}
				fen/=2;
				l/=4;
			}
			printf("%lld\n",res);
		}
	}
	return 0;
}