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.只有一個點的話，無歐拉路，但是有解..