Training：母函数

发表于 分类于 Disqus：

HDU 1028：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18473
输入 n ( n ≤ 120 ) ，求 n 的拆分的个数，直接套用母函数模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
const int maxn=10010;
int c1[maxn],c2[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=0;i<=n;++i) c1[i]=1,c2[i]=0;
        for(int i=2;i<=n;++i){
            for(int j=0;j<=n;++j)
                for(int k=0;k+j<=n;k+=i)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=n;++j) c1[j]=c2[j],c2[j]=0;
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}

HDU 1398：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21519
与上题类似，但是数字只能是平方数，所以由 k + = i 变成了 k + = s q , s q = i ∗ i 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
const int maxn=10010;
int c1[maxn],c2[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<=n;++i) c1[i]=1,c2[i]=0;
        for(int i=2;i*i<=n;++i){
            int sq=i*i;
            for(int j=0;j<=n;++j)
                for(int k=0;k+j<=n;k+=sq)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=n;++j) c1[j]=c2[j],c2[j]=0;
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}

HDU 1085：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17611
给出 n 1 个1元硬币， n 2 个3元硬币， n 3 个5元硬币，求最小的不能凑成的金额是多少。
首先求出硬币金额总和，确定循环上届，然后修改母函数模板即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int maxn=10010;
int v[3]={1,2,5},num[3];
bool vis[maxn],tmp[maxn];
int main(){
    while(~scanf("%d%d%d",&num[0],&num[1],&num[2])){
        int sum=v[0]*num[0]+v[1]*num[1]+v[2]*num[2];
        if(!sum) break;
        memset(vis,0,sizeof(vis));
        memset(tmp,0,sizeof(tmp));
        for(int i=0;i<=v[0]*num[0];i+=v[0]) vis[i]=true;
        for(int i=1;i<3;++i){
            for(int j=0;j<=sum;++j)
                for(int k=0;k+j<=sum&&k<=v[i]*num[i];k+=v[i])
                    tmp[k+j]|=vis[j];
            for(int j=0;j<=sum;++j)
                vis[j]=tmp[j],tmp[j]=0;
        }
        int ans=1;
        while(vis[ans]) ++ans;
        printf("%d\n",ans);
    }
    return 0;
}

HDU 1171：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17611
放在母函数专题里，但是我贴多重背包模板做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=250010;
int d[maxn],m[55],w[55],v;
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = max(a[i], a[i - c] + w);
}
void zeroone_pack(int *a, int c, int w)
{
    for(int i = v; i >= c; i--)
        a[i] = max(a[i], a[i - c] + w);
}
void mutiple_pack(int *a, int c, int w, int m)
{
    if(c * m >= v){
        complete_pack(a, c, w);
        return;
    }
    int k = 1;
    while(k < m)
    {
        zeroone_pack(a, k * c, k * w);
        m = m - k;
        k = 2 * k;
    }
    zeroone_pack(a, c * m, w * m);
}
int main(){
    int n;
    while(~scanf("%d",&n)&&!(n<0)){
        int sum=0;
        for(int i=1;i<=n;++i){
            scanf("%d %d",&w[i],&m[i]);
            sum+=m[i]*w[i];
        }
        v=sum/2;
        for(int i=0;i<=v;++i) d[i]=(i?-inf:0);
        for(int i=1;i<=n;++i) mutiple_pack(d,w[i],w[i],m[i]);
        int ans=0;
        for(int i=0;i<=v;++i) ans=max(ans,d[i]);
        printf("%d %d\n",sum-ans,ans);
    }
}

HDU 1709：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32231
给出 n 个砝码的质量，求不能称出总质量以下的哪些质量，砝码可以放在两边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int maxn=10010;
int a[maxn],ans[maxn],tmp[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        memset(ans,0,sizeof(ans));
        int sum=0;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
        for(int i=0;i<=a[1];i+=a[1]) ans[i]=1;
        for(int i=2;i<=n;++i){
            for(int j=0;j<=sum;++j)
                for(int k=0;k+j<=sum&&k<=a[i];k+=a[i])
                    tmp[k+j]+=ans[j],tmp[abs(k-j)]+=ans[j];
            for(int j=0;j<=sum;++j)
                ans[j]=tmp[j],tmp[j]=0;
        }
        int cnt=0;
        for(int i=1;i<=sum;++i){
            if(ans[i]) continue;
            ans[++cnt]=i;
        }
        printf("%d\n",cnt);
        if(!cnt) continue;
        for(int i=1;i<=cnt;++i){
            if(i!=1) printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

HDU 2082：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23618
26个字母的价值分别为1～26，给出26个字母各自的个数，求能组成多少个价值小于50的单词，忽略单词的顺序。
有上界的母函数问题，将模板最内层循环次数修改为当前字母个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
const int maxn=55;
int c1[maxn],c2[maxn],a[30];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(int i=1;i<=26;++i) scanf("%d",&a[i]);
        for(int i=0;i<=a[1];++i) c1[i]=1,c2[i]=0;
        for(int i=2;i<=26;++i){
            for(int j=0;j<=maxn;++j)
                for(int k=0;k+j<=maxn&&k<=a[i]*i;k+=i)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=maxn;++j) c1[j]=c2[j],c2[j]=0;
        }
        int ans=0;
        for(int i=1;i<=50;++i) ans+=c1[i];
        printf("%d\n",ans);
    }
    return 0;
}

HDU 2152：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=31180
给出 n 种水果，要买 m 个，每种又下界 a i 上界 b i 。求有多少种买法。
有上下界的母函数，内层循环下界为 a i 个，上界为 b i 个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=110;
int c1[maxn],c2[maxn],l[maxn],r[maxn];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;++i)
            scanf("%d%d",&l[i],&r[i]);
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        c1[0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=m;++j)
                for(int k=l[i];j+k<=m&&k<=r[i];++k)
                    c2[j+k]+=c1[j];
            for(int j=0;j<=m;++j) c1[j]=c2[j],c2[j]=0;
        }
        printf("%d\n",c1[m]);
    }
    return 0;
}

HDU 1059：
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17678
也是贴多重背包模板过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5000;
int d[maxn],m[7],v;
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = max(a[i], a[i - c] + w);
}
void zeroone_pack(int *a, int c, int w)
{
    for(int i = v; i >= c; i--)
        a[i] = max(a[i], a[i - c] + w);
}
void mutiple_pack(int *a, int c, int w, int m)
{
    if(c * m >= v){
        complete_pack(a, c, w);
        return;
    }
    int k = 1;
    while(k < m)
    {
        zeroone_pack(a, k * c, k * w);
        m = m - k;
        k = 2 * k;
    }
    zeroone_pack(a, c * m, w * m);
}
int main(){
    int t=0;
    while(1){
        v=0;
        for(int i=1;i<=6;++i){
            scanf("%d",&m[i]);
            m[i]%=240,v+=m[i]*i;
        }
        if(!v) break;
        bool ok=true;
        printf("Collection #%d:\n",++t);
        if(v&1) ok=false;
        v/=2;
        for(int i=0;i<=v;++i) d[i]=(i?-inf:0);
        for(int i=1;i<=6;++i) mutiple_pack(d,i,i,m[i]);
        if(d[v]>=0&&ok) printf("Can be divided.\n\n");
        else printf("Can't be divided.\n\n");
    }
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章