hdu 2110 - Crisis of HDU

缺乏、安全感 2022-05-28 13:40 101阅读 0赞

# 地址 #

[http://acm.hdu.edu.cn/showproblem.php?pid=2110][http_acm.hdu.edu.cn_showproblem.php_pid_2110]

# 定位 #

*  排列组合问题
 *  母函数
 *  大数陷阱

# 分析 #

*  物品种类数 n，第 i 行输入：物品价值 v\[i\]，物品数量 n2\[i\]。
 *  目标总价值 ∑niv\[i\]n2\[i\]3，可能不被3整除，及目标总价值不是整数。又因为 v\[i\] 和 n2\[i\] 均为整数，一定没有分配方案，直接输出 sorry。
 *  母函数 
    
    g(x)=(1\+xv\[1\]\+...\+xn2\[1\]v\[1\])...(1\+xv\[i\]\+...\+xn2\[i\]v\[i\])...(1\+xv\[n\]\+...\+xn2\[n\]\]v\[n\])

# 代码 #

**\[cpp\]** view plain copy

print ?

1.  \#include <iostream>  
2.  \#include <stdio.h>  
3.  \#include <string.h>  
4.    
5.  using namespace std;  
6.    
7.  int a\[10001\],b\[10001\];  
8.  int v\[101\],n1\[101\],n2\[101\];  
9.    
10. /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* 
11. Function:       GenerateFunc(int N,int P) 
12. Description:    生成函数系数计算 
13. Input:          int N : 相乘的因子个数 
14.                 int P : 待求的最大指数 
15. Output:         void 
16. Return:         void 
17. Others:         修改的全局变量 a\[\] b\[\] 
18.                 只读的全局变量 v\[\] n1\[\] n2\[\] 
19. \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
20. void GenerateFunc(int N,int P) \{  
21.     memset(a,0,sizeof(a));  
22.     a\[0\]=1;  
23.     for(int i=0; i<N; i++) \{  
24.         memset(b,0,sizeof(b));  
25.         for(int j=n1\[i\]; j<=n2\[i\]&&j\*v\[i\]<=P; j++) \{  
26.             for(int k=0; k+j\*v\[i\]<=P; k++) \{  
27.                 b\[k+j\*v\[i\]\]+=a\[k\];  
28.                 b\[k+j\*v\[i\]\]%=10000;  
29.             \}  
30.         \}  
31.         memcpy(a,b,sizeof(b));  
32.     \}  
33. \}  
34.   
35. int main() \{  
36.     int n,p;  
37.     memset(n1,0,sizeof(n1));  
38.     scanf(”%d”,&n);  
39.     while(n!=0) \{  
40.         p=0;  
41.         for(int i=0; i<n; i++) \{  
42.             scanf(”%d %d”,&v\[i\],&n2\[i\]);  
43.             p+=v\[i\]\*n2\[i\];  
44.         \}  
45.         if(p%3!=0) \{  
46.             printf(”sorry\\n”);  
47.             scanf(”%d”,&n);  
48.             continue;  
49.         \}  
50.         p/=3;  
51.         GenerateFunc(n,p);  
52.         if(a\[p\]==0) \{  
53.             printf(”sorry\\n”);  
54.         \} else \{  
55.             printf(”%d\\n”,a\[p\]);  
56.         \}  
57.         scanf(”%d”,&n);  
58.     \}  
59. \}

# 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">15MS</td> 
   <td align="center">1872K</td> 
   <td align="center">1168B</td> 
   <td align="center">c++</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

*  大数限制

输出结果要求对10000取模，暗示方案数会很大，而且中间计算过程很可能出现大数。因此，不仅要在最后输出时做取模运算，在中间计算过程中，也要及时取模规避大数问题。

[http_acm.hdu.edu.cn_showproblem.php_pid_2110]: http://acm.hdu.edu.cn/showproblem.php?pid=2110