真题解析│2017年蓝桥杯软件类省赛传统“送分题”

2017年蓝桥杯软件类省赛C++大学A组第5题“字母组串”。一道代码填空题，据说这是传统的送分题，一起来看看是怎么送分的。

01

题目描述

由 A,B,C 这3个字母就可以组成许多串。比如：“A”,“AB”,“ABC”,“ABA”,“AACBB” …

现在，小明正在思考一个问题：如果每个字母的个数有限定，能组成多少个已知长度的串呢？

他请好朋友来帮忙，很快得到了代码，解决方案超级简单，然而最重要的部分却语焉不详。

请仔细分析源码，填写划线部分缺少的内容。

# include<stdio.h>

// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。

intf( inta, intb, intc, intn)

{

if(a< 0|| b< 0|| c< 0) return0;

if(n== 0) return1;

return______________________________________ ; // 填空

}

intmain

{

printf( “%dn”, f( 1, 1, 1, 2));

printf( “%dn”, f( 1, 2, 3, 3));

return0;

}

对于上面的测试数据，小明口算的结果应该是：

6

19

注意：只填写划线部分缺少的代码，不要提交任何多余内容或说明性文字。

02

DP填空

1.C++代码

一个排列组合问题，题目要求用递归实现。答案如下：

returnf(a – 1, b, c, n – 1) + f(a, b – 1, c, n – 1) + f(a, b, c – 1, n – 1);;

2.Java代码

2017蓝桥杯Java类的第5题也是“字母组串”，这里附上答案。

publicclass_05字母组串 {

// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。

staticintf( inta, intb, intc, intn) {

if(a < 0|| b < 0|| c < 0) return0;

if(n == 0) return1;

returnf(a – 1, b, c, n – 1) + f(a, b – 1, c, n – 1) + f(a, b, c – 1, n – 1); //填空

}

publicstaticvoidmain(String[] args){

System.out.println(f( 1, 1, 1, 2));

System.out.println(f( 1, 2, 3, 3));

}

}

03

母函数

对于排列组合问题，经典的解法是母函数。用母函数处理组合问题，较为直接。

参考本篇参考书籍 《算法竞赛入门到进阶》173页“指数型母函数”，书上的例题 hdu 1521 和这题“字母组串”几乎一样。

下面图片为所涉及到的书中内容贴图：

04

参考书籍

《算法竞赛入门到进阶》

ISBN：978-7-302-52915-6

罗勇军 郭卫斌 编著

定价：59.80元

05

精彩文章回顾