tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 数学 >>

曹钦翔


组合计数与动态规划
北京大学哲学系 曹钦翔

组合计数问题的特征
组合计数是计数问题的一个子类 大量适用于最优化问题的分析手段不适 用与组合计数类问题

组合计数问题的特征
A、B是两个集合
已知A,B中元素的最大值,求A∪B的最大值。 已知A,B中元素的和,求A∪B中的元素的和。

组合计数问题的特征
A、B是两个集合
最大值:可以直接求解 和:不可以直接求解

组合计数问题的特征
组合计数问题相比一般计数问题,答案 范围通常很大,通常不适用基于枚举的 算法 组合计数问题的解答可能会用到一些组 合数学的原理和公式 动态规划是组合计数问题最常见的解决 方案

组合计数问题的特征

组合计数公式1 组合计数公式
在1,2,3,…,n中选出m个,方案总数为:

C

m n

组合计数公式2 组合计数公式
将1,2,3,…,n中分为k组,每组依次包含 a1,a2,…,ak个数(a1+a2+…+ak=n), 方案总数为:

n! a1!?a 2 !?... ? a k !

组合计数公式2 组合计数公式
公式推导:
先将n个数排成一列,总方案数为n! 选第1~a1个数形成第一组,因此他们之间的 顺序是无关的,故总方案数除以a1! 选第(a1+1)~(a1+a2)个数形成第二组,因此 他们之间的顺序是无关的,故总方案数除以 a2! ……依此类推

组合计数公式2 组合计数公式
将1,2,3,…,n中分为k组,每组依次包含 a1,a2,…,ak个数(a1+a2+…+ak=n), 方案总数为:

C ?C
a1 n

a2 n ? a1

? ... ? C

ak n ? a1 ? a 2 ...? a k ?1

组合计数公式2 组合计数公式
公式推导:
先从n个数中选出a1个数形成第一组,方案 数为:组合数C(n,a1)。 再从剩余的n-a1个数中选出a2个数形成第二 组,方案数为:组合数C(n-a1,a2)。 ……依此类推

组合计数公式3 组合计数公式
略:等价于公式1

组合计数公式4 组合计数公式
公式推导:
设ti=si+(i-1),即:
t1=s1 t2=s2+1 t3=s3+2 … tm=sm+(m-1)

所以:1≤t1<t2<…<tm≤n+m-1。

组合计数公式5 组合计数公式
公式推导:
设si=x1+x2+…+xi,即:
s1=x1 s2=x1+x2 s3=x1+x2+x3 … sm=x1+x2+…+xm

所以:1≤s1<s2<…<sm-1<sm=n。

组合计数公式6~8 组合计数公式
请同学们自行推导。

取余数运算的实现
由于组合计数问题的答案通常比较大, 题目中往往要求选手输出“答案除以某 个数p之后取余数”的结果。 p通常是一个质数,但也有例外。 组合计数过程中,如果涉及除法运算, 那么在“取余数”的实现会比较复杂。

取余数运算的实现
涉及加减、乘、除运算,但保证除数与 p互质
利用求数论倒数进行除法运算,即:
a/b 与 a * b-1 同余

求数论倒数可以在O(p)-O(1)的在线算法, 以及每次运算O(logp)的算法。

取余数运算的实现
只涉及乘、除运算,p为质数
把每个数X写成下面形式:
X = Y * pn 其中Y与p互质

取余数运算的实现
其他的一些情形:
只涉及乘、除运算,p为合数 涉及加减乘除运算,但是除法运算只有一 次

取余数运算的实现
补充:数论倒数b-1的三种求法
利用拓展欧几里得算法求“b*b-1+p*k=1” 的一组整数解 当p是质数时,借助公式b-1=bp-2利用快速 幂算法求解 当p是质数时,借助“找一个p的原根g”做 预处理

计数公式的基本算法
乘方的计算
补充:如何高效的求出1+x+x2+…+xn

组合数的计算

组合计数例题
请同学们踊跃发言

组合计数例题1 组合计数例题
搭积木的方案计数。
只允许使用横向放置长度不超过k的长长条 形积木,但每一种积木数量不限 只允许在一个1*w底座上进行搭建 每一块积木必须放置在整数位置 每一块积木下方的每一个位置都必须有其 他积木或者为底座 搭建的高度不得超过h

组合计数例题1 组合计数例题

组合计数例题1 组合计数例题
f[i]表示:
积木连接成一条长为i的长条的方案总数

预处理:
f[i] = f[i-1] + f[i-2] + … + f[i-k]

dp[i][j]表示:
底座长为j,高度出超过i的方案总数

组合计数例题1 组合计数例题
状态转移方程:
dp[i][j] = dp[i-1][j] * f[j] + dp[i-1][j-1] * f[j-1] * dp[i][0] + dp[i-1][j-2] * f[j-2] * dp[i][1] +… + dp[i-1][0] * f[0] * dp[i][j-1]

组合计数例题2 组合计数例题
现在有n个正方体积木,边长分别是 a[1],a[2]…a[n]。 要把他们搭成一座塔(从下到上排成一 列),使得所有相邻的两个积木,上方 的积木的边长不能比下方的加上D还要 大。 输入所有积木的边长,问:有多少种不 同的搭建方案。

组合计数例题3 组合计数例题
n人参加一次信息学竞赛,共有m道题。 现在比赛已经结束,评分正在进行中
对于已经结束评测的试题,已知每名考生 这道题的答案是否正确。 对于未结束评测的试题,只知道每名考生 是否提交答案。

每个题分数固定,提交正确的答案的考 生可以得到这一题的分数。

组合计数例题3 组合计数例题
根据获得的总分进行排名
总分越高排名越靠前 总分相同时编号较小的考生排名靠前

这n人中,排名最靠前的s人将获得候选 资格 而这s人中将通过最终的科学委员会面 试选出其中的t人。

组合计数例题3 组合计数例题
输入当前的评测信息,包括:
每道题每名选手是否提交 已经评测的试题,每名选手是否正确 每道题的分值

问最终的t人代表队共有多少种组队的 可能。

组合计数例题3 组合计数例题
思考:
对于固定的t个人,问这t人是否有可能组 成最终的代表队

组合计数例题3 组合计数例题
思考:
对于固定的t个人,问这t人是否有可能组 成最终的代表队

答:
这t人按照最高可能得分计算,其他人按照 最低可能得分计算。

组合计数例题3 组合计数例题
按所有人的最高可能得分排序 设I是t人中的得分最低者,前i-1人中
有r人,他们即使按照最低得分计算,得分 也比I高 有i-t人,没有入选最终的t人代表队 以上两部分的交集不应该超过s-t人

组合计数例题4 组合计数例题
共有n种颜色的“車”放在X*Y的棋盘 上
每种“車”分别有s[1],s[2],…,s[n]枚

问有多少种不同的放置“車”的方式, 使得任意两枚不同颜色的“車”都不能 相互攻击 X,Y<=30,n<=10

组合计数例题5 组合计数例题
有n张双面卡片,
在每一张的正面已经写上了1到n,顺序不 定,但是每个数必须恰好被写一次。 在每一张的反面也已经写上了1到n ,也必 须每个数恰好被写一次。

组合计数例题5 组合计数例题
输入每张卡片正反面写的数 问,如果任意安排卡片的顺序,且任意 选择每张卡片是正面向上还是反面向上, 那么,将这n张牌排成一列,依次将朝 上的一面的数读出得到的长度为n的数 列,共有多少种不同的可能。

组合计数例题6 组合计数例题
输入n,D,L,U。 问:一个长度为n的字符串,如果只由 数码、大小写字母组成,那么有多少种 不同的这样的字符串,其中至少有D个 数码、L个小写字母、U个大写字母? n,D,L,U<=200000

组合计数例题7 组合计数例题
共有n个瞬时事件和m个延时事件。即, 每个瞬时事件会在某个时刻发生,每个 延时事件会在某个时间开始,然后又在 之后的某个时间结束。 问:共有多少种不同事件发生的顺序。

组合计数例题8 组合计数例题
初始时,序列为:0,1,2,…,n-1。 可以执行的操作有n-1个,分别为:
交换第1、2项 交换第2、3项 … 交换第n-1、n项

已知这n-1个操作每个恰好执行了一次。

组合计数例题8 组合计数例题
输入最终的序列 问为了达到这种目标序列,共有多少种 不同的操作顺序


推荐相关:

曹钦翔授课资料_图文.ppt

曹钦翔授课资料 - 决策分析与单调性 北京大学哲学系 曹钦翔 2009年2月4日 决策分析与单调性 北京大学哲学系 曹钦翔 关键字 单调性 2009年2月4日 分析 决策分析...

曹钦翔+线性规划与网络流_图文.ppt

曹钦翔+线性规划与网络流 - 线性规划与网络流 北京大学 曹钦翔 一. 网络流模

2012年noi冬令营曹钦翔讲稿.ppt

2012年noi冬令营曹钦翔讲稿 - 组合计数与动态规划 北京大学哲学系 曹钦翔 组合计数问题的特征 ? ? 组合计数是计数问题的一个子类 大量适用于最优化问题的分析手段不...

曹钦翔 无向图问题选讲.ppt

曹钦翔 无向图问题选讲 - APIO2011 无向图问题选讲 北京大学哲学系 曹钦翔 题外话 ? 欢迎在RENREN添加“曹钦翔@OI”为好友并 留言交流OI问题。 http://...

APIO'2011_无向图问题选讲_曹钦翔.ppt

APIO'2011_无向图问题选讲_曹钦翔_IT/计算机_专业资料。APIO2011 无向图问题选讲 北京大学哲学系 曹钦翔 题外话 ? 欢迎在RENREN添加“曹钦翔@OI”为好友并 留言...

算法合集之《从“k倍动态减法游戏”出发探究一类组合游....ppt

从“k倍动态减法游戏”出发 探究一类组合游戏问题上海市上海中学 曹钦翔 指导教师

数据结构的提炼与压缩.ppt

2012年noi冬令营曹钦翔讲稿... 40页 2财富值 2012年noi冬令营

曹钦翔wc2012组合计数与动态规划_图文.ppt

曹钦翔wc2012组合计数与动态规划 - 组合计数问题的特征 ? ? 组合计数是

第7章线性规划问题与网络流.ppt

第8章 线性规划与网络流... 15页 免费 第八章线性规划与网络流 59页 1下载券 曹钦翔+线性规划与网络流... 51页 免费 8线性规划与网络流 46页 1下载券喜...

2009 中国数学奥林匹克获奖名单.pdf

2009 中国数学奥林匹克获奖名单 - 2009 中国数学奥林匹克获奖名单 一等奖 姓名 庄梓铨 曹钦翔 陈家豪 郑凡 卢焕然 李超陈麟 章博宇 林博徐泽 韦东奕 曾驭龙 ...

无穷图的桥.ppt

无穷图的桥 - 2011年国家队选拔赛 第二试 年国家队选拔赛 无穷图的桥 北京大学哲学系 曹钦翔 无穷图的桥 分数分布: 30分:蒋中天、闫学灿 20分:周奕超等20...

从“k倍动态减法游戏”出发探究一类组合游戏问题_图文.ppt

从“k倍动态减法游戏”出发探究一类组合游戏问题 - 从“k 从“k倍动态减法游戏”出发 探究一类组合游戏问题 上海市上海中学 曹钦翔 指导教师: 指导教师:上海市...

noi论文分类.doc

《解析一类组合游戏》 2009 - 曹钦翔《从“k 倍动态减法游戏”出发探究一类

2008年上海市TI杯高二年级数学竞赛_图文.doc

曹钦翔 毛杰申 陆奕骞 陈晟伟 刘王赢伟 郭嘉骅 叶云飞 沈之默 李观群 朱靓妤

2008年上海市TI杯高二年级数学竞赛.doc

曹钦翔 毛杰申 陆奕骞 陈晟伟 刘赢 郭嘉骅 王伟 叶云飞 沈之默 李观群 朱靓

2008年上海市TI杯高二年级数学竞赛.pdf

曹钦翔 上海中学 2 毛杰申 市西中学 3 陆奕骞 控江中学 4 陈晟伟 控江中

2005年上海市青少年“白猫杯”应用化学与技能竞赛初中....xls

曹钦翔 王玮毅 张集川 何康 章少骏 施云川 包心宇 方元炜 哈元恺 二等奖(6

数据结构的提炼与压缩_图文.ppt

数据结构的提炼与压缩上海市上海中学 曹钦翔指导教师:上海市上海中学 毛黎莉 数据

NOI国家集训队论文分类(至2008)(摘抄自C博客).doc

《解析一类组合游戏》 2009 - 曹钦翔《从“k 倍动态减法游戏”出发探究一类

国家集训队论文分类整理.pdf

《解析一类组合游戏》 2009 - 曹钦翔《从“k 倍动态减法游戏”出发探究一类

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com