Training:母函数

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博客 ,格式可能有所偏差。