HDU1391 (Number Steps)[map]

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1391
根据仔细分析题意后可以找出n和坐标x, y有如下关系：

n%4 x y
0 n/2 n/2
1 n/2+1 n/2+1
2 n/2+1 n/2-1
3 n/2+2 n/2

枚举n求出对应的x, y并用二维的map建立索引就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
const int maxc = 10000 + 10;
std::map<int, std::map<int, int> > m;

int main() {
	int T, x, y;
	for(int i = 0; i <= maxc; i += 4) 
		m[(i>>1)][(i>>1)] = i + 1;
	for(int i = 1; i <= maxc; i += 4) 
		m[(i>>1)+1][(i>>1)+1] = i + 1;
	for(int i = 2; i <= maxc; i += 4) 
		m[(i>>1)+1][(i>>1)-1] = i + 1;
	for(int i = 3; i <= maxc; i += 4) 
		m[(i>>1)+2][(i>>1)] = i + 1;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d", &x, &y);
		if (m[x][y]) printf("%d\n", m[x][y] - 1);
		else printf("No Number\n");
	}
	return 0;
}