2009年11月12日星期四
今天看MrBayes的源代碼了，就A了兩道
sgu108:篩法的推廣和滾動(dòng)數(shù)組優(yōu)化
很精簡(jiǎn)，很強(qiáng)大的一題...
設(shè)n為當(dāng)前數(shù),那么d(n)最大值為 n + 7 * 9所以64大小的數(shù)組已經(jīng)足夠
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];//預(yù)處理sum
is_prime[i & 63] = true;
is_prime[next & 63] = false;
}
}
sgu101:歐拉路
非常強(qiáng)大的一題...
按照題意以骨牌為節(jié)點(diǎn)建圖的話，題目就變成了hamilton路徑搜索。
注意到骨牌的值只有0~6，可以考慮用節(jié)點(diǎn)值為節(jié)點(diǎn)建圖，這樣就變成了尋找歐拉路徑
注意:
1.判圖連通
2.判歐拉回路的存在行
3.如果存在則需要從<存在>的節(jié)點(diǎn)開始搜索
4.歐拉回路需要回溯
5.只有一個(gè)點(diǎn)的話，無歐拉路，但是有解..