常用技巧精选(1)再三题 POJ3279 POJ3684 POJ2785

POJ 3279 (开关问题 + 状态压缩)

如果说poj3276是一维的开关问题, 那么这题是二维的开关问题. 在一维问题中, 可以直接由第一个元素往后计算出所有元素的开关状态, 在本题中, 以每一个小个子为一个元素进行计算是不行的, 因为一个格子的状态会影响他周围格子的状态, 更为本质的说, 存在这样的情况使得后面的状态影响了前面的状态, 因此想找出一个拓扑序向下计算是困难的. 《挑战》书中给出了一种降维的思想解决了这个问题. 每行为一个元素, 枚举第一行可能的所有状态, 然后推出其余行的状态.

这里是一种无损降维, 因此使用的编程手段和状态压缩是一样的, 可以使用二进制位来进行计算.

POJ 3684 (弹性碰撞)

在discuss里面有一句很搞笑的

这样搞下去，ICPC可以变成International Complex Physic Competition了

挺费脑的地方是要想出他和”Ants”这道题的区别所在. Ants碰撞返回是没有半径的. 这里不仅有半径, 而且每个球下落的时间是不一样的, 所以从下往上每一个球的净碰撞次数都少一次, 因此最后i号球的位置要加上2Ri, 所谓净碰撞, 意思就是往下碰一次往上碰一次就相当于半径为0的碰撞了, 是不用加上2R的. 想通这个真是费劲.

POJ 2785 (双向搜索之折半枚举)

这题的思路和平时手算某些东西的时候思路是很相像的, 所以算法也很好理解, 代码也很好写, 就是运行起来要6579MS.

int a[] = {1, 2, 2, 2, 4};
int b = 2;
cout << upper_bound(a, a+5, b) << " " << lower_bound(a, a+5, b) << endl;
cout << upper_bound(a, a+5, 2) - lower_bound(a, a+5, 2) <<endl;

上面代码运行的结果是

0x46d010 0x46d004
3