初赛知识/数学知识自学笔记
2025-07-22 18:20:21
发布于:上海
一.组合数学与计数
参考来源:深入浅出程序设计竞赛(进阶篇)和百度
引入:
计数原理和排列组合.
计数原理是数学中用于解决排列组合问题的基本原理.
计数,即统计数字,统计有很多种方式;统计的数字也有很多种.
加法原理:如果做一件事有n种方式,第i种方式有种方法,那么做成这件事共有种不同的方法.
比如从家去图书馆,可以自己前往,也可以找人接送;这是两种方式.
而自己前往可以步行,骑车;找人接送可以是公交车,出租车,地铁.
那么从家去图书馆一共是五种方式.
乘法原理:如果做一件事有n个步骤,第i个步骤有种实现方法,那么做成这件事共有种方法.
比如说你早上起来,要搭配今天的服饰.
分为两步:选衣服,选裤子.
衣服有长袖的一款和短袖的一款;裤子有长裤和短裤.
那么一共有四种搭配方式.
排列数:从n个人中选出m个人站成一排.
那么一共有m个位置.
第一个位置有n个人可以站在上面,第二个有n-1个,接着是n-2......最后一个位置有n-m+1个.
然后就是乘法原理.
这一排人有m个位置,这m各位置分别有n,n-1,n-2...n-m+1中选择.
那么这一排共有种排列方式.
注:
组合数:从n个人中选出m个人.
组合数实际上是基于排列数的.其本身是去重过后的排列数.
举个例子,从3个数中选出2个的排列和组合.
发现组合有3种,排列有6种.
排列=所有组合的全排列
全排列:指从n个元素中任取n个元素,按照一定的顺序进行排列.
将其带进排列数公式,n个元素的全排列为
那么如果有x种组合,那么全排列=
反之=全排列/
章节一:集合与容斥原理
集合,简称集,集合内元素可为零.
一个由2,4两个构成的集合,可记作{2,4}.
集合拥有以下性质:
1.确定性,即任何事物是否属于该集合都应当有一个明确的定义.
2.无序性,即集合内的事物没有顺序区分.
3.互异性,即集合内不会出现两个相等的元素.
元素a属于集合A记作,反之则记作.
如果对于任何集合A内的元素,都保证,则称作A是B的子集,记作.
若集合A与B中的元素都能在对方的集合中找到,则称.
若一个集合中不存在任何元素,则称该集合为空集,记作.
一个集合内的元素个数称为该集合的大小.A集合的大小可记作
交集,并集,补集:
交集:如果集合C为集合A与集合B的交集,当且仅当时,且.
当,或.记作.
并集:如果集合C是集合A和集合B的并集,那么集合A与集合B的所有元素,集合C都有且只有.
记作
补集:如果集合C是集合A关于集合B的补集,那么集合C的元素是所有属于集合B但不属于集合A的元素.
这是深入浅出程序设计竞赛(进阶篇)在本小姐所有的对于集合与容斥原理的解释的集合(不包含题目解释)
然后就给出了第一道题目:P3197 越狱.
我看着简短的题面,没有什么思路,所以我就去看了这本书中对于此题给出的分析,大概是这样:
"因为n和m太大,所以猜测答案是一个与n和m有关的表达式.然而,如果想要直接求出所有可以开门的情况数量会很困难.此时不妨从补集的角度入手.xxxxxxxxxxxxxxxxxxxxxxxxxx"
这很奇怪,为什么会选择从补集的角度入手?
这里空空如也
有帮助,赞一个