hdu 2082 - 找单词

Bertha 。 2022-05-28 13:24 114阅读 0赞

# 地址 #

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

# 定位 #

*  排列组合问题
 *  母函数

# 分析 #

*  物品种类数 N=26，第 i 种物品数量 xi，第 i 种物品价值 i。
 *  母函数 
    
    g(x)=(1\+x1\+...\+xx1)(1\+x2\+...\+x2x2)...(1\+xi\+...\+xixi)...(1\+x26\+...\+x26x26)

# 代码 #

**\[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\[1001\],b\[1001\];  
8.  int v\[27\],n1\[27\],n2\[27\];  
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.             \}  
29.         \}  
30.         memcpy(a,b,sizeof(b));  
31.     \}  
32. \}  
33.   
34. int main() \{  
35.     int N,sum;  
36.     for(int i=0; i<26; i++) \{  
37.         v\[i\]=i+1;  
38.     \}  
39.     memset(n1,0,sizeof(n1));  
40.     scanf(”%d”,&N);  
41.     while(N–) \{  
42.         sum=0;  
43.         for(int i=0; i<26; i++) \{  
44.             scanf(”%d”,&n2\[i\]);  
45.         \}  
46.         GenerateFunc(26,50);  
47.         for(int i=0; i<=50; i++) \{  
48.             sum+=a\[i\];  
49.         \}  
50.         printf(”%d\\n”,sum-1);  
51.     \}  
52. \}

# 性能 #

<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">1876K</td> 
   <td align="center">1265B</td> 
   <td align="center">c++</td> 
  </tr> 
 </tbody> 
</table>

# 总结 #

*  方案数 sum−1

结合输入输出示例，发现空单词不属于接受方案，应予排除。

*  最后一行的输出格式

题目要求每行输入一个结果，特意在最后一个结果后不输出换行符，导致 Presentation Error。因此，每个结果后伴随输出换行符就行了，不必对最后一行特别处理。

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