tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

计数题选讲


简单的数数题选讲
xudyh

? 题目全部来自TC。

DevuAndBeautifulSubstrings
? 一个串是beautiful的当且仅当相邻字母两两 不同。 ? 一个二进制串的beauty level定义为beauty level为beautiful子串个数。 ? 给定n和cnt,求长度为n的beau

ty level为 cnt的二进制串个数。 ? n<=50 ? "0001"的beauty level为5。 ? TCO15 1C 1000pts

solution
? 我从未见过如此简单的千分题。 ? 将串奇数位置反一下就变成相同字母子串 个数。 ? dpi,j表示前i个字母beauty level为j的方案。 ? 枚举最后一段长度。

PerfectSquare
? 有一个n*n的矩阵,要选一些数。 ? 要求每行每列选的数都是奇数,并且这些 数的乘积是完全平方数。 ? n<=20,数字大小不超过10^9。 ? SRM 620 800pts

solution
? ? ? ? ? xi,j表示选或不选。 每行每列选奇数个可以列出方程。 乘积为完全平方数对每个质因子列方程。 求方程组解的个数。 高斯消元+bitset优化。

SquareOfSquareMatrix
? 求n*n的01矩阵A数量,其中某些位置已经 填上了1,要求A*A是零矩阵。 ? n<=500。 ? SRM 644 900pts

solution
? 看成一个有向图,不存在从一个点走两步 到另一个点。 ? 也就是不存在一个点既有出边又有入边。 ? 假设有p个点已经连了出边,q个点已经连 了入边,已经连了m条边。 ? 枚举剩下点中连出边的点个数。

AquaparkPuzzle
? 有|c|个景点,第i个的代价为ci。 ? 共有k天,每天可以游览总代价不超过m的 子集。 ? 问每个景点至少被访问两次的方案数。 ? |c|<=11,k<=10^6。 ? SRM 645 900pts

solution
? ? ? ? 大大大大大大暴力! 首先枚举访问不超过1次的子集,进行容斥。 那么仅考虑这些不超过1次的景点即可。 假设有n个,考虑各种暴力算法。

solution 1
? 暴力子集卷积倍增,时间复杂度O(3^nlog k) ? 老年选手的最佳选择。 ? 太麻烦的我都不会做。

solution 2
? 如果有特别的子集卷积和多项式乘方技巧 能做到O(2^n n^2)。

solution 3
? ? ? ? 仅考虑非空子集。 令dpi,S表示选了i个非空子集,并为S的方案。 再考虑放空集的方案。 时间复杂度O(3^n n)。

PermutationCounts
? 求1到n排列个数满足当且仅当p在pos数组 中,有pk<pk+1。 ? n<=106,pos中数的个数不超过2000。 ? n=5,pos={3} ? {3,2,1,5,4},{4,2,1,5,3},{4,3,1,5,2},{4,3,2,5,1 },{5,2,1,4,3},{5,3,1,4,2},{5,3,2,4,1},{5,4,1,3, 2},{5,4,2,3,1} ? SRM 656 500pts

solution
? ? ? ? pos将数列划分成了若干段,要求每段递减。 比如pos={3},那么有p1>p2>p3,p4>p5。 同时要求p3<p4。 如果不考虑这个限制,那么假设序列被划 分成x1,x2,...,xt,那么方案就相当于将n个数 划分成t个集合,第i个集合大小为xi。 ? 那么方案数为n!/(x1)!(x2)!...(xt)!。

solution
? 容斥这些pk<pk+1的限制。 ? 如果不满足就有pk>pk+1,也就是相邻两段被 合并起来。 ? n=6,pos={1,3}时,答案就是6!/1!/2!/3!6!/3!/3!-6!/1!/5!+6!/6!。 ? 最后被划分成j块对答案贡献为(-1)|pos|+j+1。

solution
? 提出n!,使用dp计算。 ? dpi做完1到i后的权值。 ? 为了方便,将0和n加入到pos中。

? 最后乘上n!。

TwoEntrances
? 有一个n个房间的房子形成树结构,并且房子有两 个入口s1,s2。 ? 有n个家具标号为0到n-1,要放入对应的房间中。 ? 一个房间被放入家具就不能继续通过。 ? 问有多少种可行的顺序。 ? n<=3000

? 可行的顺序为{3,2,1,0},{3,2,0,1},{3,0,2,1},{0,3,2,1} ? SRM 654 850pts

solution
? ? ? ? ? ? 考虑倒着移除家具。 首先考虑一个入口的情况。 如果两棵子树大小为s1,s2,方案为p1,p2。 那么合并后的方案数为 。 于是可以dp,令dpv表示子树v的方案数。 更一般的有方案数为 ,sizev表示 v子树大小。

solution
? 考虑两个入口之间的路径,那么任何状态 下剩下的子树是连续的。 ? 记dpl,r表示当前剩下的是第l个到第r个子树。 ? 考虑当前拿掉l,将第l个子树的方案和dpl+1,r 的方案合并,r同理。

Fragile
? 求n个点的有标号图k个桥的图个数。 ? n<=50。 ? n=3,k=2

? SRM 648 850pts

首先膜一发r老师
? Finally, a combinatoric 850-pointer was waiting for challengers. The following comment by [[rng_58]] explained the reason for the unusually low point value: "well, for me it's like standard 500." Unfortunately, only five coders were able to solve this standard 500. ? 500分题你问我什么水平?

solution
? 大致思路,首先只要考虑n个点k条桥的连 通图的个数,不连通只要背包背一下。 ? 首先求出n个点连通图个数。 ? 任意图减去不连通的图个数。 ? 枚举最小点所在连通块的大小然后算一下。 ? 然后考虑k>=1的情况算一下。 ? 然后从连通图中减去就得到了k=0的答案。

如果你有Petr老爷的计数底力
? 写个五六次的dp,然后打表。 ? 大概dp[a][b][c]表示a个点,b个桥,c个连 通块。 ? 然后枚举1号点所在的双连通块,然后枚举 剩下的点构成了多少个连通块多少个桥。 ? 然后算一算就算出来了。

? 然而更有可能是发现没过大样例。。。 ? 然后爆零了。。。

如果你有rng_58老师的智商
? 考虑固定一条边为桥,然后分成两个部分。

如果你有lyrically大爷的姿势水平
? 一个n个点的有标号的图,有s个大小分别 为m1,m2,...,ms的连通分量。 ? 连s-1条边让它连通的方案数为 。 ? 然后求一求将n个点划分成s个连通分量的 方案算一下对应的权值即可。

什么?你什么都不会?

? 做数数题全都靠信仰。

? 祝大爷们省选虐场开心^_^。。。


推荐相关:

理财计算题目选讲

如果将这三个地区的债券混合在一起,其平均价格为( A ) 如果将这三个地区的债券混合在一起,其平均价格为( (A)133.3 )(B)215 )(C)150 )(D)180 ) 1...


化学计算题选讲二(第31题)

化学计算题选讲二(第 31 题) 化学计算题选讲 1.在实验室中,氮氧化物废气 氮氧化物废气(主要成分 NO2 和 NO)可以用 NaOH 溶液来吸收 溶液来吸收,以除去这...


理财计算题目选讲

理财计算题目选讲 14页 1财富值 投资计算题目 暂无评价 1页 1财富值 理财计算...根据案例,回答下列问 题: 1.本例中上官夫妇的退休基金需求折现至退休时约为(...


圆中计算问题中考题选讲

圆中计算问题中考题选讲_从业资格考试_资格考试/认证_教育专区。一.教学内容: 圆中计算问题中考题选讲 二. 教学重点: 1. 求阴影部分的面积。 2. 解决实际...


理财计算题目选讲

? ? ? 79.87 1.08 1.082 1.0810 某债券面值 100 元,票面利率 5%,每年付息一次,距下一付息 日还有 160 天,每年计息日按 365 天计算,则其应计利息为...


圆中计算问题中考题选讲

圆中计算问题中考题选讲圆中计算问题中考题选讲隐藏>> 一.教学内容: 圆中计算问题中考题选讲 二. 教学重点: 1. 求阴影部分的面积。 2. 解决实际问题。 【...


《数学分析选讲》_第一次作业计算题和证明题解答[1]

《数学分析选讲》_第一次作业计算题和证明题解答[1] 西南大学西南大学隐藏>> 三、计算题 1.求极限 lim (3x ? 6) 70 (8 x ? 5) 20 . x ? ?? (...


第十二讲 综合题选讲二

2数数与计数 7页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能...综合题选讲( 第十二讲 综合题选讲(二) 解综合题,除了要有牢固的解基本题的...


小学奥数培训例题——补充题选讲19小升初部分之二

小学奥数培训例题——补充题选讲19小升初部分之二_学科竞赛_小学教育_教育专区...Write the 2012 Chinese population in scientific notation.(科学计数法) 2. A...


2013级程序设计实用案例选讲考试题

2013级程序设计实用案例选讲考试题_从业资格考试_资格考试/认证_教育专区。2014-2015 学年第一学期程序设计实用案例选讲考试题 1.说明: 本试题满分为 100 分(代...

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