Noip初赛问题求解专题.ppt
LETS MAKE THINGS SIMPLE AND COOL,从离散数学 解析 问题求解,By Dirak,嵊州市城关中学 宋子健,CONTEST,一览,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,2,目 标 排列组合和基础原理：排列，组合，鸽巢，容斥 浅谈常见模型：Catalan，全错位 数学建模：排序问题 演练：习题,Combinatorial,SIMPLE AND COOL,离散数学,3,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,名词解释：离散数学即组合数学，一般研究图论、代数结构、数理逻辑等离散对象，所谓离散即不连续。排列数P(n,m)：从n个数中取m个数进行排列，所可能取得的情况种数。计算公式：引申：m个数的全排列种数为m！组合数C(n,m)：从n个数中取m个数所可能的情况种数计算公式：引申：C(n,m)=c(n,n-m),4,离散数学,Combinatorial,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,SIMPLE AND COOL,容斥原理 用韦恩图表示为右图。A、B、C为三个独立的集合，得：即：将所有元素合并，再去掉重复计算的部分，即为总共的元素个数。,Combinatorial,鸽巢原理 也称抽屉原理。有n个鸽巢和(kn+1)只鸽子，将鸽子放进鸽巢，则至少有一个鸽巢有(k+1)只及以上的鸽子。可用反证法证明。实际问题中的鸽子和鸽巢往往要抽象得多，常需要根据题意自己构造。,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,5,离散数学,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,Catalan数 设有一(n+2)边形（只考虑凸多边形），则可以画出(n-1)条不相交的对角线将其分割成n个三角形，设所有可能的情况种数为，且定义。先以一条边为底边，显然该边所在的三角形会把n边形分成两个部分（如图是一种可能的情况），设左边有(k+2)条边，则右边有(n+2)-(k+2)-1=(n-k-1)条边。根据乘法原理，这样可能的情况数为 由于k的大小可以从0变化到n-1，得：,6,常见模型,MODEL,SIMPLE AND COOL,MODEL,数列 即著名的Catalan数列。用生成函数的知识可得它的通项公式：常见Catalan应用：由1和-1各n个组成的数列 满足对于任一正整数k,该数列可能种数n个元素的出栈顺序可能数 有n个节点的二叉树可能形态数,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,7,8,常见模型,MODEL,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,全错位排列 有1n号信箱和1n号邮件，每一封邮件都没有放进所对应的信箱，求放邮件的可能情况种数。利用容斥原理：得通项公式：利用递推法：,MATH MODELING,【例1】对于一个有5个元素的数组，最少需要几次比较才能保证数组有序？【答案】7次【分析】由于原题的解析太(看)繁(不)琐(懂)，我们引入决策树的概念来解决题目。我们对元素进行比较时只有两个结果：a=b或a26，因此深度为6次或更少的决策树叶子节点没有120个，不能确定排列顺序。故答案为7次。对于n个元素的排列，需要比较 次,数学建模,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,9,MATH MODELING,【例2】将数组8,23,4,16,77,-5,53,100中的元素从小到大排列，至少需要交换几次？【答案】5次【分析】排列后的数组为-5,4,8,16,23,53,77,100。发现元素位置的变化如图：,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,10,数学建模,11,数学建模,MATH MODELING,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,我们画一个有向图，从初始状态位置上的数向排列后位置上的数引一条有向边。发现形成了几个环（包括自指的节点）。如果要在最少次数内排序，显然两个环中的元素交换位置是没有意义的（因为肯定还要换回来），因此只需要将各个环交换好顺序即可。显然一个包含k个元素的环排序需要交换(k-1)次，所以总共要交换5次。对于N个元素的数组，设形成n个环，第i个环有ki个元素。则需要交换：(k1-1)+(k2-1)+(kn-1)=N-n 次。,EXPERIENCE,撒经验,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,SIMPLE AND COOL,12,EXERSICE,SIMPLE AND COOL,WWW.SBJSHWK.COM|+1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,习题,13,在圆周上有7个点，在任两个点之间连一条弦，假设任三条弦不交于一点。问把7边形分成几个三角形定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成 另一个字符这三种操作。将字符串 A 变成字符串 B 的最少操作步数，称为字 符串 A 到字符串 B 的编辑距离。字符串ABCDEFG到字符串BADECG的 编辑距离为_。III.在 NOI 期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。在第十八桌，有 5 名大陆选手和 5 名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么，这一桌共有_种不同的就坐方案。注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。IV.现有80枚硬币，其中有一枚假币，重量较轻，给你一个天平，最少需要称量几次才能找出假币？,14,送学习资料哦，祝早日转Vijos/C+,SIMPLE AND COOL,WWW.SBJSHWK.COM|Q+:1813571145|OYSB STREET 12345,OYSB IS MADE IN CHINA,PROGRESS SOON!,THANKS FOR LISTENING,LETS MAKE THINGS SIMPLE AND COOL,
