某岛

… : "…アッカリ~ン . .. . " .. .
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 。