noip初赛问题解析

@洛谷有题

注:
选择排序、快速排序、希尔排序、堆排序不稳定
冒泡排序、插入排序、归并排序、基数排序稳定

一些数学问题的解答

  • 决策树: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=0i1dpjdpij1
    通项 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=(i1)(dpi1+dpi2)
    假设当前点 1 1 1选择了 k k k,然后 k k k选择了1,那么相当于剩下 i − 2 i-2 i2个数的错排
    k k k选择了非1的 p p p,相当于1选择了 p p p,把 k k k扔掉,那么相当于剩下 i − 1 i-1 i1个数的错排

  • 涂色
    在这里插入图片描述
    如图,有 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(mm1dpn2+mm2dpn1)
    当前格子可以有 m m m中选择,讨论相邻的两个格子
    颜色相同,相当于 n − 2 n-2 n2的情况,但是方案数更改一下
    颜色不同,相当于 n − 1 n-1 n1的情况

  • 算两次
    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=S01,这个结论可以用在很多题目里

  • 最少相邻交换排序,火柴排队,答案为逆序对数

  • 最少任意交换排序,每个点的入度为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 2C3212=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)ni=1n[i(n+1i)]
然后,代几个值进去,发现 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.50+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(n1)=y(m1)(x,y)使
所以令 D = [ n − 1 , m − 1 ] D=[n-1,m-1] D=[n1,m1],则 x = D n − 1 , y = D m − 1 x=\frac{D}{n-1},y=\frac{D}{m-1} x=n1D,y=m1D
然后讨论

  • x 奇 y 奇 x奇y奇 xy,输出 ( n , m ) (n,m) (n,m)
  • x 奇 y 偶 x奇y偶 xy,输出 ( n , 1 ) (n,1) (n,1)
  • x 偶 y 奇 x偶y奇 xy,输出 ( 1 , m ) (1,m) (1,m)
  • x 偶 y 偶 x偶y偶 xy,输出 ( 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 1n方格方案数
对当前第一格的颜色进行讨论

  • 白色,第二格可以任意涂色,方案数为 f ( n − 1 ) f(n-1) f(n1)
  • 黑色,第二个只能白色,第三个可以任意涂色,方案数为 f ( n − 2 ) f(n-2) f(n2)

所以, f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n1)+f(n2)
边界, 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+33510016767+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 109876/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(n1)]+[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)=n1n+f(1)+f(2)+...+f(n1)
边界, 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

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值