软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 开发杂谈 -> hdu2082找单词(母函数) -> 正文阅读

[开发杂谈]hdu2082找单词(母函数)


找单词
题意:
中文题,考虑是不是要写个英文题意。。(可惜英语水平不够  囧rz)                (题于文末)
 
知识点:
母函数(生成函数):   
    生成函数有普通型生成函数和指数型生成函数两种(本题是普通型)。
    形式上,普通型母函数用于解决多重集的组合问题,
                指数型母函数用于解决多重集的排列问题。
    母函数还可以解决递归数列的通项问题(例如使用母函数解决斐波那契数列,Catalan数的通项公式)。
普通母函数:
    构造母函数G(x), G(x) = a0 + a1*x + a2*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154051598-1698766422.png + a3*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154055582-913563630.png +....+ an*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154059644-111040593.png,  则称G(x)是数列a0,a1…an的母函数。
    通常普通母函数用来解多重集的组合问题,其思想就是构造一个函数来解决问题,一般过程如下:
    1.建立模型:物品n种,每种数量分别为k1,k2,..kn个,每种物品又有一个属性值p1,p2,…pn,(如本题的字母价值),
      求属性值为m的物品组合方法数。(若数量ki无穷 也成立,即对应下面式子中第ki项的指数一直到无穷)
    2.构造母函数:G(x)=(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154100488-503527946.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154103410-1011407148.png[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154104394-1988150098.png)(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154105191-514771929.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154108144-151941179.png+…[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154108973-1797101829.png)…(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154109785-1943078512.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154110676-344737385.png+…[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154111598-1006599262.png)        (一)
                                =a0 + a1*x + a2*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154051598-1698766422.png + a3*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154055582-913563630.png +....+ akk*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154115504-1409281129.png     (设kk=k1·p1+k2·p2+…kn·pn)  (二)
                  G(x)含义: ak 为属性值为k的组合方法数。
母函数利用的思想
    1.把组合问题的加法法则和幂级数的乘幂对应起来。
    2.把离散数列和幂级数对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来
       确定离散数列的构造。
代码实现:
    求G(x)时一项一项累乘。先令G=1=(1+0*x+0*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154116394-583122744.png+…0*[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154123348-1089268002.png),再令G=G*(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154100488-503527946.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154103410-1011407148.png[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154104394-1988150098.png)得到形式(二)的式子…最后令G=G*(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154109785-1943078512.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154110676-344737385.png+…[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154111598-1006599262.png)。
 
题解:
1.建模:物品(字母)26种,每种数量x1,x2…x26,属性值为1,2,3..26,求属性值和<=50的组合方法数。
2.G(x)=(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154127332-736327922.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154128191-1213988736.png[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154129301-269914967.png)(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154139066-1149550598.png+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154142816-1972059053.png+…[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154143863-1251666153.png)…(1+[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154144754-232595985.png+…[img]http://images2015.cnblogs.com/blog/778507/201604/778507-20160402154145644-555851996.png)


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long a[60],b[60];
 
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        a[0]=1;
        int x;
        for(int i=1;i<=26;i++)
        {
            scanf("%d",&x);
            for(int j=0;j<=50;j++)
            {
                for(int k=0;k<=x&&(j+k*i<=50);k++)
                {
                    b[j+k*i]+=a[j];
                }
            }
            for(int j=0;j<=50;j++)
            {
                a[j]=b[j];
                b[j]=0;
            }
        }
        long long ans=0;
        for(int i=1;i<=50;i++)
            ans+=a[i];
        cout<<ans<<endl;
    }
}

找单词
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status
Description
假设有x1个字母A, x2个字母B,..... x26个字母Z,同时假设字母A的价值为1,字母B的价值为2,..... 字母Z的价值为26。那么,对于给定的字母,可以找到多少价值<=50的单词呢?单词的价值就是组成一个单词的所有字母的价值之和,比如,单词ACM的价值是1+3+14=18,单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关,比如ACM与CMA认为是同一个单词)。
Input
输入首先是一个整数N,代表测试实例的个数。
然后包括N行数据,每行包括26个<=20的整数x1,x2,.....x26.
Output
对于每个测试实例,请输出能找到的总价值<=50的单词数,每个实例的输出占一行。
Sample Input
2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9
Sample Output
7 379297
......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2016-04-03 20:46:48  
开发杂谈 最新文章
BloomFilter
大学四年编程之历程
内核分析
造人论坛——意识的本质和一个人工脑模型
OFDM信号[matlab描述]
人类还会进化吗?
HDUACM1035RobotMotion简单模拟题
树、二叉树(二)
iisphpweb.config处理404,500等,跳转友好
DatabaseAsaFortress
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年1日历
2018-1-23 3:37:34
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --