首页 > 代码库 > 使用母函数方法解答几个问题
使用母函数方法解答几个问题
由于在货币组合的题目中使用了母函数的方法，就顺便搜索一些资料和练习，加深自己的理解。
杭电ACM课件中简要介绍了母函数的方法，并给出了几道相关的题目。
1. HDU1398 Square Coins
使用指定的货币来组合一个给定的目标值，问一共有多少种可能。这道题和我们以前的货币组合题目大同小异，代码如下：
1 #include <stdio.h> 2 3 #define MAXITEMS 2048 4 5 int v[17] = {0}; 6 int c1[MAXITEMS]; 7 int c2[MAXITEMS]; 8 int result[MAXITEMS]; 9 10 void11 MultiplePoly(int c1[], int max1, int c2[], int max2)12 {13 int i, j;14 for (i = 0; i <= max1; i++) {15 for (j = 0; j <= max2; j++) {16 result[i + j] += c1[i] * c2[j];17 }18 }19 }20 21 int 22 main(int argc, char** argv)23 {24 int i, j; 25 26 for (i = 0; i < 17; i++) {27 v[i] = (i+1)*(i+1);28 }29 30 memset(c1, 0, sizeof(int) * MAXITEMS);31 for (i = 0; i <= 300; i++) {32 c1[i] = 1;33 }34 35 for (i = 1; i < 17; i++) { 36 memset(c2, 0, sizeof(int) * MAXITEMS);37 for (j = 0; j <= 300; j += v[i]) {38 c2[j] = 1;39 }40 memset(result, 0, sizeof(int) * MAXITEMS);41 MultiplePoly(c1, 300, c2, 300);42 memmove(c1, result, sizeof(int) * MAXITEMS);43 }44 int input;45 while (scanf("%d", &input) == 1) {46 if (input == EOF) {47 break;48 }49 printf("%d\n", result[input]);50 }51 52 return 0;53 }
2. HDU1028 Ignatius and the Princess III
将大的数字分解成小的数字，问一共有多少种可能。和货币组合大同小异，代码如下：
1 #include <stdio.h> 2 3 #define MAXITEMS 8196 4 5 int v[120] = {0}; 6 int c1[MAXITEMS]; 7 int c2[MAXITEMS]; 8 int result[MAXITEMS]; 9 10 void11 MultiplePoly(int c1[], int max1, int c2[], int max2)12 {13 int i, j;14 for (i = 0; i <= max1; i++) {15 for (j = 0; j <= max2; j++) {16 result[i + j] += c1[i] * c2[j];17 }18 }19 }20 21 int 22 main(int argc, char** argv)23 {24 int i, j; 25 26 for (i = 0; i < 120; i++) {27 v[i] = i+1;28 }29 30 memset(c1, 0, sizeof(int) * MAXITEMS);31 for (i = 0; i <= 120; i++) {32 c1[i] = 1;33 }34 35 for (i = 1; i < 120; i++) { 36 memset(c2, 0, sizeof(int) * MAXITEMS);37 for (j = 0; j <= 120; j += v[i]) {38 c2[j] = 1;39 }40 memset(result, 0, sizeof(int) * MAXITEMS);41 MultiplePoly(c1, 120, c2, 120);42 memmove(c1, result, sizeof(int) * MAXITEMS);43 }44 int input;45 while (scanf("%d", &input) != EOF) {46 printf("%d\n", result[input]);47 }48 49 return 0;50 }
3. HDU1085 Holding Bin-Laden Captive
给定个数的1元、2元和5元，问不可能组成的最小的货币值。就是求母函数的第一个系数为0的下标。代码如下：
1 #include <stdio.h> 2 3 #define MAXITEMS 8196 4 5 int v[3] = {1, 2, 5}; 6 int c1[MAXITEMS]; 7 int c2[MAXITEMS]; 8 int result[MAXITEMS]; 9 10 void11 MultiplePoly(int c1[], int max1, int c2[], int max2)12 {13 int i, j;14 int *pResult;15 for (i = 0; i <= max1; i++) {16 if (c1[i] != 0) {17 pResult = &result[0];18 pResult += i;19 for (j = 0; j <= max2; j++) {20 pResult[j] += c1[i] * c2[j];21 }22 }23 }24 }25 26 int 27 main(int argc, char** argv)28 {29 int i, j;30 int resultIdx;31 int num[3] = {0, 0, 0};32 while (scanf("%d %d %d", &num[0], &num[1], &num[2]) == 3) {33 if (num[0] == 0 && num[1] == 0 && num[2] == 0) {34 break;35 }36 memset(c1, 0, sizeof(int) * MAXITEMS);37 for (i = 0; i <= num[0]; i++) {38 c1[i] = 1;39 }40 for (i = 1; i < 3; i++) { 41 memset(c2, 0, sizeof(int) * MAXITEMS);42 for (j = 0; num[i] >= 0; j += v[i], num[i]--) {43 c2[j] = 1;44 }45 memset(result, 0, sizeof(int) * MAXITEMS);46 MultiplePoly(c1, 3000, c2, 5000);47 memmove(c1, result, sizeof(int) * MAXITEMS);48 }49 for (resultIdx = 0; resultIdx < MAXITEMS; resultIdx++) {50 if (result[resultIdx] == 0) {51 printf("%d\n", resultIdx);52 break;53 }54 }55 }56 57 return 0;58 }
4. HDU1171 Big Event in HDU
有若干件物品，每种物品有它的价值。现在要将这些物品分配给两个机构A和B，要求分给A的不少于分给B的。等价于求母函数的系数不为零的项的中间一个项，就是给A分配的物品总价值，余下的就是给B的。代码如下（不能AC，报超时，暂时不管）：
1 #include <stdio.h> 2 3 #define MAXITEMS 250000 4 5 int v[50]; 6 int m[50]; 7 int c1[MAXITEMS]; 8 int c2[MAXITEMS]; 9 int result[MAXITEMS];10 11 void12 MultiplePoly(int c1[], int max1, int c2[], int max2)13 {14 int i, j;15 int *pResult;16 for (i = 0; i <= max1; i++) {17 if (c1[i] != 0) {18 pResult = &result[0];19 pResult += i;20 for (j = 0; j <= max2; j++) {21 pResult[j] += c1[i] * c2[j];22 }23 }24 }25 }26 27 int 28 main(int argc, char** argv)29 {30 int i, j, k;31 int inputCnt;32 int sum;33 int tmp;34 while (scanf("%d", &inputCnt) == 1)35 {36 if (inputCnt < 0) {37 break;38 }39 memset(v, 0, sizeof(int) * 50);40 memset(m, 0, sizeof(int) * 50);41 /* read the v array and m array */42 for (k = 0; k < inputCnt; k++) {43 scanf("%d %d", &v[k], &m[k]);44 }45 /*printf("sum: %d\n", sum);*/46 sum = 0;47 /* initial first polynomial */48 memset(c1, 0, sizeof(int) * MAXITEMS);49 tmp = m[0];50 sum += m[0]*v[0];51 for (i = 0; tmp >= 0; i+=v[0], tmp--) {52 c1[i] = 1;53 }54 /* then initial others, if there is any */55 for (i = 1; i < inputCnt; i++) { 56 memset(c2, 0, sizeof(int) * MAXITEMS);57 tmp = m[i];58 sum += m[i]*v[i];59 for (j = 0; tmp >= 0; j += v[i], tmp--) {60 c2[j] = 1;61 }62 memset(result, 0, sizeof(int) * MAXITEMS);63 MultiplePoly(c1, sum, c2, m[i]*v[i]);64 memmove(c1, result, sizeof(int) * MAXITEMS);65 }66 /* output */67 memset(result, 0, sizeof(int) * MAXITEMS);68 int count = 0;69 for (i = 0; i <= sum; i++) {70 if (c1[i] > 0) {71 result[count] = i;72 count++;73 }74 }75 int partA = result[count/2];76 int partB = sum - partA;77 printf("%d %d\n", partA, partB);78 }79 return 0;80 }
5. HDU1709 The Balance
有一架天平，给你若干个砝码，可以把砝码放在左边或者右边，能够表示出不同的克数。砝码放在左边，表示在母函数中系数为负，右边则为正。代码还没写。
先写到这里。
使用母函数方法解答几个问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。