某島

… : "…アッカリ~ン . .. . " .. .
August 27, 2010

HOJ 2963. Count Subset

Brief description :

卡搜索,卡DP的子集和問題。
(N<=40, M<=1,000,000,000)

Analyse :

存在著一種折衷的辦法,即將折半搜索出兩張散列表,再拼接。
複雜度是 O(2^20) ,勉強可以卡過它。

/*
    Author: xiaodao
    Prog: HOJ 2963. Count Subset
    Status: Accepted
    Last modifiy: GMT +8 Aug. 29th 17:49
*/
#include 
#include 
const int PRIME = 3214567; //4500989
const int N = 40;
struct node{
    int k, s;
} hash[PRIME];
int n, step; int a[N];
long long m, ans;



int h(int k){
	return (k % PRIME);
}
int Search(int k){
	int y = h(k);
	while (hash[y].k != k && hash[y].s!=0)
		y = (y+1) % PRIME;
	return y;
}
void Insert(int k){
	node &y = hash[Search(k)];
	y.k = k; y.s++;
}


void dfs1(int k, long long s){
    if (s>m) return;
    if (k==step) Insert(s);
    else{
        dfs1(k+1, s+a[k]);
        dfs1(k+1, s);
    }
}

void dfs2(int k, long long s){
    if (s>m) return;
    if (k==step) ans += hash[Search(m-s)].s;
    else{
        dfs2(k+1, s+a[k]);
        dfs2(k+1, s);
    }
}


void solve(){
    step = n/2; dfs1(0, 0);
    step = n; dfs2(n/2, 0);
}


void init(){
    scanf("%d", &n);

    int x, y;
    for (int i=0;i

Hit :

此題內存供應比較緊張,要注意一下幾個方面。

1. iostream 會消耗1000KB的空間,stdio.c 消耗的空間比 cstdio 的空間要多。
2. 只開一張散列表。(也就是第二次搜索到葉子結點的時候直接在先前的散列表中查詢了。)
3. 採用簡單的閉散列。(其實理論分析這種方法雖然有助於固定內存,但應該對總的內存訪問量沒有幫助,
不過考慮到也許系統沒有辦法立即釋放掉指針的內存。)

因此我手寫了一個線性探查的閉散列,注意到如果用STL::MAP,無論我怎麼寫都要 MLE 。