B.找单词——(HDU 2082 普通型母函数)

简介:

传送门

找单词

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5721    Accepted Submission(s): 4026


Problem 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
 

解题思路:

这是一个母函数的题,因为ACM与CMA认为是同一个单词,因为这是组合问题,所以这不是指数型的母函数。在下一篇博客中会详细介绍一下关于普通型母函数的知识点。这里就简单的说几句,就拿第一个例子来说吧,就拿第一个例子来说吧,我们可以这样想因为A, B, C的字母只有一个而且他们的价值还不相同,A=1,B=2,C=3,所以我们可以组成的单词可以是(1+X) * (1+X^2) * (1+X^3) == 1 + X + X^2 + 2*X^3 + X^4 + X^5 + X^6,所以价值不 小于50的就是 <=50的 X 的系数加起来, But没有X^0前面的系数不需要,因为没有字母就不是单词,想明白这个之后就是写程序了, 请看我的代码:


My Code:

#include <iostream>
using namespace std;

int c1[55];///每一次存的多项式中的数
int c2[55];///中间转化变量
int arr[30];///输入的价值数组

///初始化
void Init()
{
    for(int i=0; i<55; i++)
    {
        c1[i] = 0;
        c2[i] = 0;
    }
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        Init();
        for(int i=1; i<=26; i++)
            cin>>arr[i];
        c1[0] = 1;
        for(int i=1; i<=26; i++)///一共26个多项式相乘
        {
            for(int j=0; j<=50; j++)///指数最多是50
            {
                for(int k=0; k<=arr[i] && k*i+j<=50; k++)///循环次数,k*i也是指数,就是多项式相乘
                {
                    c2[k*i+j] += c1[j];
                }
            }
            for(int j=0; j<=50; j++)///c1才是系数
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        int ret = 0;
        for(int i=1; i<=50; i++)///指数是0的不算单词
            ret += c1[i];
        cout<<ret<<endl;
    }
    return 0;
}




目录
相关文章
|
8月前
|
缓存 监控 算法
详细介绍一下淘宝商品详情API接口系列的调用频率限制
淘宝商品详情 API 系列(核心为taobao.item.get)的调用频率限制,采用应用级 QPS + 分钟级 + 日总量三重管控,按开发者身份、应用类型、接口版本、套餐等级分级执行,是平台保障服务稳定性、防滥用的核心机制。以下从限制规则、限流机制、超限处理、提额申请、调用方控频方案五方面详细说明。
|
8月前
|
供应链 数据处理 数据库
医疗器械唯一标识(UDI)赋码产线升级改造全方案
本方案面向医疗器械企业,聚焦法规合规、产线适配、自动赋码、数据互通与质量可控五大核心,提供覆盖小/中/大批量产能的标准化UDI产线改造方案,支持人工、半自动、全自动三种模式,兼容多包装类型,满足YY/T 1879、1943等标准及国家UDI实施要求。(239字)
773 0
|
10月前
|
数据采集 人工智能 机器人
2026年 智能体来了!什么是 AI 智能体工程化?为什么金加德强调 Workflow + Code 才能真正落地?
AI智能体工程化是将AI从聊天工具升级为“数字员工”,通过流程编排(Workflow)、代码逻辑(Code)与知识增强(RAG),让其稳定执行重复性业务流程,实现可复用、可落地的自动化生产。
981 7
|
10月前
|
人工智能 弹性计算 运维
阿里云无影云电脑商业版是什么?优势、应用场景及业务模式全解析
阿里云无影云电脑商业版是面向直播、AI教育、设计渲染等高价值场景的云上工作空间,融合“硬件+软件+安全+运维”能力,提供开箱即用的专业环境。具备极致体验、原生安全、统一运维、绿色节能与AI智能五大优势,支持六大行业场景应用,助力企业降本增效、合规创新,重塑数字化生产力。
|
11月前
|
人工智能 运维 监控
用 AI 做日志语义检索与异常摘要——不是为了炫技,是为了让 on-call 少掉几根头发
用 AI 做日志语义检索与异常摘要——不是为了炫技,是为了让 on-call 少掉几根头发
387 12
|
人工智能 搜索推荐 网络架构
TryOffAnyone:快速将模特服装图还原为平铺商品图,生成标准化的服装展示效果
TryOffAnyone 是一款基于 AI 技术的工具,能够将模特穿着服装的图像快速还原为平铺商品图,支持智能识别、自动优化等功能,适用于电商平台和虚拟试衣场景。
1305 12
TryOffAnyone:快速将模特服装图还原为平铺商品图,生成标准化的服装展示效果
|
网络协议 关系型数据库 应用服务中间件
【项目场景】请求数据时测试环境比生产环境多花了1秒是怎么回事?
这是一位粉丝(谢同学)给V哥的留言,描述了他在优化系统查询时遇到的问题:测试环境优化达标,但生产环境响应时间多出1秒。通过抓包分析,发现MySQL请求和响应之间存在500毫秒的延迟,怀疑是网络传输开销。V哥给出了以下优化建议:
640 4
|
Web App开发 前端开发 程序员
将微信公众号文章同步到阿里云开发者社区
本文介绍了一种通过自己拓展的浏览器插件,便捷地将微信公众号文章同步到阿里云开发者社区的方法。
834 6
|
机器学习/深度学习 人工智能 安全
针对AI模型的对抗性攻击日益增多:你现在应该怎么做?
针对AI模型的对抗性攻击日益增多:你现在应该怎么做?
|
Prometheus 运维 监控
智能运维实战:Prometheus与Grafana的监控与告警体系
【10月更文挑战第27天】在智能运维中,Prometheus和Grafana的组合已成为监控和告警体系的事实标准。Prometheus负责数据收集和存储,支持灵活的查询语言PromQL;Grafana提供数据的可视化展示和告警功能。本文介绍如何配置Prometheus监控目标、Grafana数据源及告警规则,帮助运维团队实时监控系统状态,确保稳定性和可靠性。
1570 0