小Q的歌单（2018腾讯笔试题）

小灰灰 2022-05-17 22:27 395阅读 0赞

还在实习的我今天有同学问我了一道编程题说是2018年腾讯校招的笔试题（我只是个即将大四的菜逼-哈哈哈）

小Q的歌单：小Q有x首长度为A的不同歌和y首长度为B的歌，现在小Q想用这些歌组成一个总长度

正好为k的歌单，每首歌只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下问有多少种组合方式

输入描述：

每个输入包含一个测试用例

每个测试用例的第一行包含一个整数，表示歌单的总长度（当然得大于0咯）

接下来一行输入四个整数分别表示第一个歌的长度a和数量x，第二首歌的长度b和数量y，保证a!=b

输出描述：

输出一个整数，表示组成歌单的方法取模

\#include<stdio.h>

long long c\[105\]\[105\];

const int mod = 1000000007;//为什么要用100000007呢其实我也不是很清楚，这里可能只是需要一个很大很大的基数

void init()//建一个杨辉三角  至于为什么要建一个杨辉三角下面我会详细说明

\{

int i,j;

c\[0\]\[0\] = 1;

for(i=1;i<101;++i)

\{

c\[i\]\[0\]=1;

for(j=1;j<101;++j)

\{

c\[i\]\[j\]=(c\[i-1\]\[j-1\]+c\[i-1\]\[j\])%mod;

\}

\}

\}

int main()

\{

int k,a,b,x,y;

long long ans=0;

int i;

init();

scanf("%d",&k);

scanf("%d%d%d%d",&a,&x,&b,&y);2 3 3 3

for(i=0;i<x+1;++i)

\{

if(i\*a<k+1 && (k-i\*a)%b == 0 && (k-a\*i) / b < y+1)//判断组合

\{

ans=(ans + (c\[x\]\[i\]\*c\[y\]\[(k-a\*i)/b\]) % mod) % mod;//为什么是\*呢，因为是排列

break;//进入到if里其实就可以break了，这样避免往后的判断能降低时间复杂度，增加效率

\}

\}

printf("%lld\\n",ans);

return 0;

\}

下面讲一下杨辉三角的作用：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5

1 6 15 20 15

比如输入：

5 （总长度5）

3 4 5 6                   4个长度为3的A 6个长度为5的B

6 （六种组合方式）

ans=(ans + (c\[x\]\[i\]\*c\[y\]\[(k-a\*i)/b\]) % mod) % mod;

当i=0时If条件就已经成立c\[x\]\[0\]=1   (k-a\*i)/b=1（几个b可以组成）

c\[4\]\[0\]\*c\[6\]\[1\]=1\*6=6

因为啥呢4个长度为3的a（杨辉三角第四行）  6个长度为5的b（杨辉三角第6行）

下面是我在linux下测试的结果：

![70][]

如果还没理解自己再输入几个组合试试对比杨辉三角

方法相同自己理解吧！

[70]: /images/20220518/7664c2b3f6fb4bb79f30bde778d91dd3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，395人围观）

还没有评论，来说两句吧...

相关阅读

相关腾讯2020校招笔试题-小Q放假

腾讯2020校招笔试题题目 > 公司给小Q放了n天的假,他有个奇怪的习惯:不会连续两天工作或段炼 > > 只有当公司开业,小Q才能去工作, > > 只有当健身

偏执的太偏执、/ 2023年08月17日 17:39/ 0 赞/ 332 阅读

相关腾讯笔试题

1、请定义一个宏，比较两个数a、b的大小，不能使用大于、小于、if语句 2、如何输出源文件的标题和目前执行行的行数 3、两个数相乘，小数点后位数没有限制，请写一个高精度算法

青旅半醒/ 2023年05月21日 07:24/ 0 赞/ 159 阅读

相关腾讯公司c/c++笔试题

这部分的腾讯c/c++面试用的笔试题主要是c/c++、数据结构、简单算法、操作系统等方面的基础知识，方便去腾讯面试开发的同仁有所参考! 笔试题的题型好像

快来打我*/ 2022年08月23日 15:53/ 0 赞/ 412 阅读

相关腾讯2014年校园招聘笔试题记

这里记一下一个概率论的问题：考试的时候不会算，乱蒙的。回来算了一下，发现蒙错了。题：有A、B两个城市，人口比例为3:5。A城市的犯罪率为0.01%，B城市的犯罪率为0

客官°小女子只卖身不卖艺/ 2022年08月21日 05:37/ 0 赞/ 367 阅读

相关腾讯2018秋招笔试真题-小Q的歌单

小Q的歌单 > 【题目描述】小 Q 有 X 首长度为 A 的不同的歌和 Y 首长度为 B 的不同的歌，现在小 Q 想用这些歌组成一个 > 总长度正好为 K 的歌单，每

r囧r小猫/ 2022年05月19日 13:29/ 0 赞/ 430 阅读

相关小Q的歌单（2018腾讯笔试题）

还在实习的我今天有同学问我了一道编程题说是2018年腾讯校招的笔试题（我只是个即将大四的菜逼-哈哈哈）小Q的歌单：小Q有x首长度为A的不同歌和y首长度为B的歌，现在小Q想用

小灰灰/ 2022年05月17日 22:27/ 0 赞/ 396 阅读

相关腾讯2012实习生笔试题

一、单项选择题 1）给定3个int类型的正整数x，y，z，对如下4组表达式判断正确的选项（） Int a1=x+y-z; int b1=x\y/z; Int a2=x-

女爷i/ 2022年04月10日 08:12/ 0 赞/ 726 阅读

相关腾讯2018笔试题，小Q的歌单

【题目描述】小 Q 有 X 首长度为 A 的不同的歌和 Y 首长度为 B 的不同的歌，现在小 Q 想用这些歌组成一个总长度正好为 K 的歌单，每首歌最多只能在歌单中出现一次，

「爱情、让人受尽委屈。」/ 2022年03月31日 13:44/ 0 赞/ 416 阅读

相关腾讯，贪吃的小Q

题目描述小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最

怼烎@/ 2022年03月29日 14:30/ 0 赞/ 493 阅读

相关 2019 腾讯正式批笔试题题解

/ 一.n种硬币，求最少数量的硬币使得凑出1~m的面值【贪心】 input： 4 20 1 2 5 10 output：

以你之姓@/ 2021年12月17日 08:23/ 0 赞/ 604 阅读