2009年11月12日星期四
今天看MrBayes的源代码了，就A了两道
sgu108:筛法的推广和滚动数组优化
很精简，很强大的一题...
设n为当前数,那么d(n)最大值为 n + 7 * 9所以64大小的数组已经足够
void sieve()
{
int i, j, next;
top = 0;
fill(is_prime, is_prime + 64, 1);
for (i = 1, j = 0; i <= n; i++) {
if (is_prime[i & 63]) {
top++;
while (top == q[j].x) {
q[j++].ans = i;
}
}
next = i + sum[i / 10000] + sum[i % 10000];//预处理sum
is_prime[i & 63] = true;
is_prime[next & 63] = false;
}
}
sgu101:欧拉路
非常强大的一题...
按照题意以骨牌为节点建图的话，题目就变成了hamilton路径搜索。
注意到骨牌的值只有0~6，可以考虑用节点值为节点建图，这样就变成了寻找欧拉路径
注意:
1.判图连通
2.判欧拉回路的存在行
3.如果存在则需要从<存在>的节点开始搜索
4.欧拉回路需要回溯
5.只有一个点的话，无欧拉路，但是有解..