杭电OJ 1032

题目：点击打开链接

想不出什么太好的方法（比如通过数论……），所以不明白那些0MS的AC是怎么做的。我的方法就是建表，递归……考虑到超出10W的数据没法确定表长了，偷懒用了C++的map模板，查询的cost稍微费些（map的数据结构为红黑树，查询的时间复杂为O(log(n))吧）。以下为15MS的AC代码。

#include <cstdio>
#include <cstring>
#include <map>

using namespace std;

typedef map<int, int> CountMap;
CountMap count_map;

int Cal(int i)
{
    CountMap::iterator it = count_map.find(i);
    if (it != count_map.end()) {
	return it->second;
    }
    
    int temp = 0;
    if (i % 2 == 0) {
	temp = i / 2;
    } else {
	temp = 3*i + 1;
    }
    int count = Cal(temp) + 1;
    count_map[i] = count;
    return count;
}

void Init()
{
    count_map[1] = 1;
}

int main()
{
    Init();

    int a, b;
    while (scanf("%d%d", &a, &b) != EOF) {
	int small, big;
	if (a > b) {
	    big = a;
	    small = b;
	} else {
	    big = b;
	    small = a;
	}

	int max = 0;
	for (int i=small; i<big+1; ++i) {
	    int count = Cal(i);
	    if (count > max) max = count;
	}

	printf("%d %d %d\n", a, b, max);
    }

    return 0;
}

这道题本来无甚，但解题过程中确碰到了很令我困扰的问题——原先的代码，i%2用了位运算，i&1——调试下来，当i为偶数时i&1 == 0的判定结果 竟然为假，跑到else里去执行了，但在else里打印i&1，结果分明是0嘛……