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个连通分量的 方案算一下对应的权值即可。

什么?你什么都不会?

? 做数数题全都靠信仰。

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


推荐相关:

竞赛题选讲(一)

竞赛题选讲(一)_学科竞赛_小学教育_教育专区。年 级 六年级 刘大占 学 科 奥数 版 本 内容标题 编稿老师 竞赛题选讲(一) 【本讲教育信息】一. 教学内容...


习题选讲

习题选讲_理学_高等教育_教育专区。运筹作业习题1.6 (1)解 1:大 M 法 在上述线性规划问题中分别减去剩余变量 x4 , x6 , x8 , 再加上人工变量 x5 , x7 ...


微机原理期末考试习题选讲

微机原理期末考试习题选讲_工学_高等教育_教育专区。江苏大学 微机原理期末考试...CX 设置字符计数器 CX=0 AGAIN:MOV AL,[SI] CMP AL,'$' JZ DONE 取...


数学史选讲测试题及其答案

数学史选讲测试题及其答案一、选择题。(共 12 小题,每题 5 分,共 60 分) 1.《周髀算经》和( )是我国古代两部重要的数学著作。 A.《孙子算经》 B....


10数学杂题选讲

10数学杂题选讲_数学_小学教育_教育专区。10 综合问题 例 1. 题 把 20 分成几个自然数(不能相同)的和,再求出这些数的乘积,并且要使得到的 乘积尽可能大,...


2016年精妙试题选讲

2016年精妙试题选讲_初三数学_数学_初中教育_教育专区。重点中学保送生辅导资料 2016 年精妙试题选讲(一) 1.如图,在矩形 ABCD 中,AB=6,以点 B 为直角顶点作...


应用题选讲

应用题选讲_数学_小学教育_教育专区。应用题选讲 应用题联系实际,生动地反映了现实世界的数量关系,能否从具体问题中归纳出数 量关系,反映了一个人分析问题、解决...


课后主要习题选讲

课后主要习题选讲_理学_高等教育_教育专区。《金融市场学》课后习题选讲 习题三...这样第(1)题的收益 率分别变为-16.67%、-3.33%和 10.00%。 Y 则要满足...


C++习题选讲

C​+​+​习​题​选​讲 暂无评价|0人阅读|0次下载|举报文档VC++语言程序设计 一、选择题 1.(2001 年秋)下面四个选项中,均不能作为用户标识符...


《几何证明选讲》习题附答案

《几何证明选讲》习题附答案_数学_高中教育_教育专区。《几何证明选讲》习题一、选择题 1. 若三角形三边上的高为 a、b、c , 这三边长分别为 6、4、3, ...

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