noip初赛问题解析

@洛谷有题

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

一些数学问题的解答

• 决策树：5个元素，至少几次比较让数组有序？
  一共有$5!$中大小关系，建立一棵决策二叉树，每个点往下引出两个儿子，表示比较一次出现两种不同的大小情况。一棵深度为$k+1$的满二叉树有$2^k$个叶子结点，进行了$k$次比较，每个叶子结点表示一种不同的大小关系，当$2^k>n!$时，能保证有序，对于此题，$2^7>5!$，所以答案是7

• 卡特兰数：$n$个结点的二叉树有几种？
  $d{p}_i={\sum }_{j=0}^{i-1}d{p}_j\ast d{p}_{i-j-1}$
  通项$d{p}_i=\frac{C_{2n}^n}{n+1}$

• 错排
  $d{p}_i=(i-1)(d{p}_{i-1}+d{p}_{i-2})$
  假设当前点$1$选择了$k$，然后$k$选择了1，那么相当于剩下$i-2$个数的错排
  若$k$选择了非1的$p$，相当于1选择了$p$，把$k$扔掉，那么相当于剩下$i-1$个数的错排

• 涂色
  
  如图，有$n$个空格，用$m$种颜色，相邻颜色不能相同，求方案数
  $d{p}_n=m(\frac{m-1}{m}d{p}_{n-2}+\frac{m-2}{m}d{p}_{n-1})$
  当前格子可以有$m$中选择，讨论相邻的两个格子
  颜色相同，相当于$n-2$的情况，但是方案数更改一下
  颜色不同，相当于$n-1$的情况

• 算两次
  $S$为二叉树结点总数，$S_{0/1/2}$为有0/1/2个儿子的结点个数
  $S=S_0+S_1+S_2=S_1+2S_2+1$
  $S_2=S_0-1$，这个结论可以用在很多题目里

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

• 最少任意交换排序，每个点的入度为1，出度为1，看成一张图由几个环组成，答案为环大小-1然后加起来

noip2019

若4个数字都不一样，则$4!=24$
若有2个一样，$aabc,aacb,abac,acab,abca,acba,baac,caab,baca,cabc,bcaa,cbaa$
则$2\ast C_3^2\ast 12=72$
若1188，1881,1818,8811,8118,8181，则6
24+72+6=102

备选数字是01869
第三空只能是018，且%3后为012
第一空可以5个里面任选一个
第二空可以5个里面任选一个
第三空随之确定，且必定合理
后两空也确定了
5*5=25

noip2018

微元法（会微积分的请走开）
把线段分成$n$等分，期望长度是$$\frac{{\sum }_{i=1}^n[i\ast (n+1-i)]}{\frac{n(n+1)}{2}\ast n}$$
然后，代几个值进去，发现$n$越大，答案越接近$\frac{1}{3}$

令$E$摸到第一个蓝球之前摸到的红球个数
$$E=0.5\ast 0+0.5\ast (1+E)$$
$$解得E=1$$
所以$D$

用一种集合的思想，先假设$a<b$，条件等价于$a$的1的位是$b$的1的位的子集
那么对于每一个$a$，设有$k$个0，那么有$2^k$个$b$满足
然后把所有的$2^k$暴力加起来，因为一开始$a<b$所以答案$\ast 2$
然后这样的话$a=b$的情况我又会多算一遍，所以再减去32
答案为$454$

noip2017

组合题，先给每个班分一个名额，相当于在11个名额10个空隙中插3块板
答案为$C_{10}^3$

直接求通项，答案为B

几何意义，小球弹弹弹
数学意义，$$x(n-1)=y(m-1)，找出最小的(x,y)使等式成立$$
所以令$D=[n-1,m-1]$，则$x=\frac{D}{n-1},y=\frac{D}{m-1}$
然后讨论

• $x奇y奇$，输出$(n,m)$
• $x奇y偶$，输出$(n,1)$
• $x偶y奇$，输出$(1,m)$
• $x偶y偶$，输出$(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=9B$

连续3年这道题目我都错了，ABC

设$f(n)$为$1\ast n$方格方案数
对当前第一格的颜色进行讨论

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

所以，$f(n)=f(n-1)+f(n-2)$
边界，$f(0)=1,f(1)=2$
推得$f(8)=55$

noip2015

容斥
$[\frac{2015}{4}]=503,[\frac{2015}{5}]=403,[\frac{2015}{6}]=335$
$[\frac{2015}{20}]=100,[\frac{2015}{12}]=167,[\frac{2015}{30}]=67$
$[\frac{2015}{60}]=33$
答案为$2015-(503+403+335-100-167-67+33)=1075$

经典卡特兰数，$10\ast 9\ast 8\ast 7\ast 6/5/4/3/2/1/(5+1)=42$

noip2013

期望dp（貌似是这么叫的）
$f(n)$表示在n的时候平均一共跳$f(n)$次
当前跳一次，可能落到前面的任何一个地方
$f(n)=\frac{[1+f(1)]+[1+f(2)]+...+[1+f(n-1)]+[1+f(n)]}{n}$
即$f(n)=\frac{n+f(1)+f(2)+...+f(n-1)}{n-1}$
边界,$f(1)=0$，推得$f(5)=\frac{37}{12}$

noip2012

三个数的取值有$2^3$种情况，每一种取值情况对应2个不同的可能答案，如果必定能构造出一个表达式使得每一种取值情况对应到一种答案，那么最多有$2^8=256$种

树形dp
$f[u][0]表示不选当前结点的方案数，f[u][1]表示选当前结点的方案数$
v表示u的儿子
$f[u][0]={\prod }_{(f[v][0]+f[v][1])}$
$f[u][1]={\prod }_{f[v][0]}$
u结点总方案数为$f[u][0]+f[u][1]$
初始化，叶子节点的f都为1
答案为5536