注:
选择排序、快速排序、希尔排序、堆排序不稳定
冒泡排序、插入排序、归并排序、基数排序稳定
一些数学问题的解答
-
决策树:5个元素,至少几次比较让数组有序?
一共有 5 ! 5! 5!中大小关系,建立一棵决策二叉树,每个点往下引出两个儿子,表示比较一次出现两种不同的大小情况。一棵深度为 k + 1 k+1 k+1的满二叉树有 2 k 2^k 2k个叶子结点,进行了 k k k次比较,每个叶子结点表示一种不同的大小关系,当 2 k > n ! 2^k>n! 2k>n!时,能保证有序,对于此题, 2 7 > 5 ! 2^7>5! 27>5!,所以答案是7 -
卡特兰数: n n n个结点的二叉树有几种?
d p i = ∑ j = 0 i − 1 d p j ∗ d p i − j − 1 dp_i=\sum_{j=0}^{i-1}dp_j*dp_{i-j-1} dpi=∑j=0i−1dpj∗dpi−j−1
通项 d p i = C 2 n n n + 1 dp_i=\frac{C_{2n}^{n}}{n+1} dpi=n+1C2nn -
错排
d p i = ( i − 1 ) ( d p i − 1 + d p i − 2 ) dp_{i}=(i-1)(dp_{i-1}+dp_{i-2}) dpi=(i−1)(dpi−1+dpi−2)
假设当前点 1 1 1选择了 k k k,然后 k k k选择了1,那么相当于剩下 i − 2 i-2 i−2个数的错排
若 k k k选择了非1的 p p p,相当于1选择了 p p p,把 k k k扔掉,那么相当于剩下 i − 1 i-1 i−1个数的错排 -
涂色
如图,有 n n n个空格,用 m m m种颜色,相邻颜色不能相同,求方案数
d p n = m ( m − 1 m d p n − 2 + m − 2 m d p n − 1 ) dp_n=m(\frac{m-1}{m}dp_{n-2}+\frac{m-2}{m}dp_{n-1}) dpn=m(mm−1dpn−2+mm−2dpn−1)
当前格子可以有 m m m中选择,讨论相邻的两个格子
颜色相同,相当于 n − 2 n-2 n−2的情况,但是方案数更改一下
颜色不同,相当于 n − 1 n-1 n−1的情况 -
算两次
S S S为二叉树结点总数, S 0 / 1 / 2 S_{0/1/2} S0/1/2为有0/1/2个儿子的结点个数
S = S 0 + S 1 + S 2 = S 1 + 2 S 2 + 1 S=S_0+S_1+S_2=S_1+2S_2+1 S=S0+S1+S2=S1+2S2+1
S 2 = S 0 − 1 S_2=S_0-1 S2=S0−1,这个结论可以用在很多题目里 -
最少相邻交换排序,火柴排队,答案为逆序对数
-
最少任意交换排序,每个点的入度为1,出度为1,看成一张图由几个环组成,答案为环大小-1然后加起来
noip2019
若4个数字都不一样,则
4
!
=
24
4!=24
4!=24
若有2个一样,
a
a
b
c
,
a
a
c
b
,
a
b
a
c
,
a
c
a
b
,
a
b
c
a
,
a
c
b
a
,
b
a
a
c
,
c
a
a
b
,
b
a
c
a
,
c
a
b
c
,
b
c
a
a
,
c
b
a
a
aabc,aacb,abac,acab,abca,acba,baac,caab,baca,cabc,bcaa,cbaa
aabc,aacb,abac,acab,abca,acba,baac,caab,baca,cabc,bcaa,cbaa
则
2
∗
C
3
2
∗
12
=
72
2*C_3^2*12=72
2∗C32∗12=72
若1188,1881,1818,8811,8118,8181,则6
24+72+6=102
备选数字是01869
第三空只能是018,且%3后为012
第一空可以5个里面任选一个
第二空可以5个里面任选一个
第三空随之确定,且必定合理
后两空也确定了
5*5=25
noip2018
微元法(会微积分的请走开)
把线段分成
n
n
n等分,期望长度是
∑
i
=
1
n
[
i
∗
(
n
+
1
−
i
)
]
n
(
n
+
1
)
2
∗
n
\frac{\sum_{i=1}^{n}[i*(n+1-i)]}{\frac{n(n+1)}{2}*n}
2n(n+1)∗n∑i=1n[i∗(n+1−i)]
然后,代几个值进去,发现
n
n
n越大,答案越接近
1
3
\frac{1}{3}
31
令
E
E
E摸到第一个蓝球之前摸到的红球个数
E
=
0.5
∗
0
+
0.5
∗
(
1
+
E
)
E=0.5*0+0.5*(1+E)
E=0.5∗0+0.5∗(1+E)
解
得
E
=
1
解得E=1
解得E=1
所以
D
D
D
用一种集合的思想,先假设
a
<
b
a<b
a<b,条件等价于
a
a
a的1的位是
b
b
b的1的位的子集
那么对于每一个
a
a
a,设有
k
k
k个0,那么有
2
k
2^k
2k个
b
b
b满足
然后把所有的
2
k
2^k
2k暴力加起来,因为一开始
a
<
b
a<b
a<b所以答案
∗
2
*2
∗2
然后这样的话
a
=
b
a=b
a=b的情况我又会多算一遍,所以再减去32
答案为
454
454
454
noip2017
组合题,先给每个班分一个名额,相当于在11个名额10个空隙中插3块板
答案为
C
10
3
C_{10}^{3}
C103
直接求通项,答案为B
几何意义,小球弹弹弹
数学意义,
x
(
n
−
1
)
=
y
(
m
−
1
)
,
找
出
最
小
的
(
x
,
y
)
使
等
式
成
立
x(n-1)=y(m-1),找出最小的(x,y)使等式成立
x(n−1)=y(m−1),找出最小的(x,y)使等式成立
所以令
D
=
[
n
−
1
,
m
−
1
]
D=[n-1,m-1]
D=[n−1,m−1],则
x
=
D
n
−
1
,
y
=
D
m
−
1
x=\frac{D}{n-1},y=\frac{D}{m-1}
x=n−1D,y=m−1D
然后讨论
- x 奇 y 奇 x奇y奇 x奇y奇,输出 ( n , m ) (n,m) (n,m)
- x 奇 y 偶 x奇y偶 x奇y偶,输出 ( n , 1 ) (n,1) (n,1)
- x 偶 y 奇 x偶y奇 x偶y奇,输出 ( 1 , m ) (1,m) (1,m)
- x 偶 y 偶 x偶y偶 x偶y偶,输出 ( 1 , 1 ) (1,1) (1,1)
首先一眼望出第一空为4,然后暴力第二空,首先对每条边编号
枚举出可行的方案为
{2,3,4}{2,4,7,8}{8,9,10,11}{8,10,11,12}{4,5,8,11}{9,13,15}{12,13,15}{9,13,16}{12,13,16},共九种
noip2016
主要是这题有个坑,非联通,所以是
8
+
1
=
9
B
8+1=9B
8+1=9B
连续3年这道题目我都错了,ABC
设
f
(
n
)
f(n)
f(n)为
1
∗
n
1*n
1∗n方格方案数
对当前第一格的颜色进行讨论
- 白色,第二格可以任意涂色,方案数为 f ( n − 1 ) f(n-1) f(n−1)
- 黑色,第二个只能白色,第三个可以任意涂色,方案数为 f ( n − 2 ) f(n-2) f(n−2)
所以,
f
(
n
)
=
f
(
n
−
1
)
+
f
(
n
−
2
)
f(n)=f(n-1)+f(n-2)
f(n)=f(n−1)+f(n−2)
边界,
f
(
0
)
=
1
,
f
(
1
)
=
2
f(0)=1,f(1)=2
f(0)=1,f(1)=2
推得
f
(
8
)
=
55
f(8)=55
f(8)=55
noip2015
容斥
[
2015
4
]
=
503
,
[
2015
5
]
=
403
,
[
2015
6
]
=
335
[\frac{2015}{4}]=503, [\frac{2015}{5}]=403, [\frac{2015}{6}]=335
[42015]=503,[52015]=403,[62015]=335
[
2015
20
]
=
100
,
[
2015
12
]
=
167
,
[
2015
30
]
=
67
[\frac{2015}{20}]=100,[\frac{2015}{12}]=167,[\frac{2015}{30}]=67
[202015]=100,[122015]=167,[302015]=67
[
2015
60
]
=
33
[\frac{2015}{60}]=33
[602015]=33
答案为
2015
−
(
503
+
403
+
335
−
100
−
167
−
67
+
33
)
=
1075
2015-(503+403+335-100-167-67+33)=1075
2015−(503+403+335−100−167−67+33)=1075
经典卡特兰数,
10
∗
9
∗
8
∗
7
∗
6
/
5
/
4
/
3
/
2
/
1
/
(
5
+
1
)
=
42
10*9*8*7*6/5/4/3/2/1/(5+1)=42
10∗9∗8∗7∗6/5/4/3/2/1/(5+1)=42
noip2013
期望dp(貌似是这么叫的)
f
(
n
)
f(n)
f(n)表示在n的时候平均一共跳
f
(
n
)
f(n)
f(n)次
当前跳一次,可能落到前面的任何一个地方
f
(
n
)
=
[
1
+
f
(
1
)
]
+
[
1
+
f
(
2
)
]
+
.
.
.
+
[
1
+
f
(
n
−
1
)
]
+
[
1
+
f
(
n
)
]
n
f(n)=\frac{[1+f(1)]+[1+f(2)]+...+[1+f(n-1)]+[1+f(n)]}{n}
f(n)=n[1+f(1)]+[1+f(2)]+...+[1+f(n−1)]+[1+f(n)]
即
f
(
n
)
=
n
+
f
(
1
)
+
f
(
2
)
+
.
.
.
+
f
(
n
−
1
)
n
−
1
f(n)=\frac{n+f(1)+f(2)+...+f(n-1)}{n-1}
f(n)=n−1n+f(1)+f(2)+...+f(n−1)
边界,
f
(
1
)
=
0
f(1)=0
f(1)=0,推得
f
(
5
)
=
37
12
f(5)=\frac{37}{12}
f(5)=1237
noip2012
三个数的取值有
2
3
2^3
23种情况,每一种取值情况对应2个不同的可能答案,如果必定能构造出一个表达式使得每一种取值情况对应到一种答案,那么最多有
2
8
=
256
2^8=256
28=256种
树形dp
f
[
u
]
[
0
]
表
示
不
选
当
前
结
点
的
方
案
数
,
f
[
u
]
[
1
]
表
示
选
当
前
结
点
的
方
案
数
f[u][0]表示不选当前结点的方案数,f[u][1]表示选当前结点的方案数
f[u][0]表示不选当前结点的方案数,f[u][1]表示选当前结点的方案数
v表示u的儿子
f
[
u
]
[
0
]
=
∏
(
f
[
v
]
[
0
]
+
f
[
v
]
[
1
]
)
f[u][0]=\prod_{(f[v][0]+f[v][1])}
f[u][0]=∏(f[v][0]+f[v][1])
f
[
u
]
[
1
]
=
∏
f
[
v
]
[
0
]
f[u][1]=\prod_{f[v][0]}
f[u][1]=∏f[v][0]
u结点总方案数为
f
[
u
]
[
0
]
+
f
[
u
]
[
1
]
f[u][0]+f[u][1]
f[u][0]+f[u][1]
初始化,叶子节点的f都为1
答案为5536