10.25听课笔记

清北学堂 笔记

$n\lt 1e4$
由题目可以得出：每次最多打过$2$只怪兽。
三种方案
1. 枚举所有可能
2. 推个公式
令$f[i]$表示打完i只怪兽的概率。
所以只要求出$f[x-1]-f[x]$就是答案。问题就转换成了怎么求$f$（不一定挂掉）。
第一种可能：$f[i]=\sum_{j=1}^{i+1}a[j]\le m$
每次一定从两只怪兽中选一只怪兽来打才打得过。所以对于前$i$只怪兽，有$2^i$种方案数。对于后$n-i$只怪兽 有$(n-i)!$种。所以总的方案数是$2^i\times (n-i)!$，即$f[i]=\frac{2^i\times (n-i)!}{n!}$
第二种可能：$\sum_{j=1}^{i+1}a[i]\gt m$
如果$\sum_{j=2}^{i+1}\gt m$说明第$1$只一定打。
说明一定有一只怪兽不能打，枚举第$k$只不打，
如果第$k$只满足条件$\sum_{j=1}^{i+1}-a[k]\le m$进行如下讨论：
第$k-1$次战斗，每次还是两种可能。
第$k\sim i$次战斗，每次都有一种可能。$\frac{2^{k-1}\times (n-i)!}{n!}$
那所有的可能就是$\frac{2^{k-1}\times (n-i)!}{n!}$（所有满足条件的）
但是发现还是枚举$i$，枚举$k$的，所以继续优化。
可以发现一定一开始都是第一种可能，到某个$i$为止出现了第二种可能。令$x$表示第一次碰到了第二种可能，其后一定都是第二种可能。当$i=x$时，先求出满足条件的$k$，$O(n)$算出$f[i]$。
当$i$增减\sum_{j=1}^{i+1}a[j]$越来越大$\sum_{j=1}^{i+1}-a[k]$也越来越大，$m$不变，因而对$x$的要求也越来越大，所以$i$增加时，某些$x$就不符合条件了。随$i$的增减$2^{j-1}\times n!$是不变的，只有$(n-i)!)在改变，所以可以看做：$\frac{\sum_{j=0}^{i}2^j \times (n-i)!}{n!}$
随$i$的增加$\sum_{j=0}^{i}2^j$和$\frac{(n-i)!}{n!}$在变化，第二个很好维护，所以任务就是维护第一个。
因为$i$增加时有些$x$不符合条件，所以只要找出不符合条件的，从答案中减去就可以了。
使用小根堆，维护最小的$a[j]$每次弹出最小的，判断是否符合条件。
总复杂度$O(n\lg n)$

3.DP
$dp[i][j]$表示打完$i$只怪兽并且第$j$只没被打的概率。因为前$i$次选怪兽，一定是能量为$0\sim i$的这么$i+1$只怪兽中选$i$只。$dp[i][j]\rightarrow dp[i+1][j],dp[i+1][j+1]$。$O(n^2)$的时间复杂度。
如果$n\lt 1e6$。考虑压维，发现第二维很难压，第一维也很难压，所以说明$d$p无法通过压维进行优化。因而考虑其他做法。
那么考虑方案$2$

$2^15$枚举：打掉那些怪兽，把怪兽看做空地，看起点和终点是否在同一联通快，如果在，就捡起能捡起的所有的血瓶，所以剩下的就是判断中途能否不挂掉。（贪心可以过，枚举全排列会TLE）
令$f[i]$表示打$i$这个状态的怪兽，打完还有多少血。
枚举最后一只打的是什么，若是$j$。可以$f[i-2^j]$来更新$f[j]$。
若$f[i-2^j]$大于打$j$扣的血，就能打过，否则不能。若可以，加上附近能捡的所有血瓶。

举一个例子：
当$L$固定时，随着$R$的增加有以下三种情况
1. 形成了一段新的长度为1的区间（++）。
2. 把相邻的区间合并起来（--）
3. 从原来的一段中，延伸了一位（不变）。
计算出当$R=1,L=1$时的值。当$R$增加时，计算三段不同情况的$L$的分割点，对于每一段执行区间加或减操作，中间不管。线段树维护。
也就是说，随着$R$的增加，线段树中，第$i$个叶子记录当$L=i$时，标记$[L,R]$后能形成多少区间，随着$R$的增减，能得到三段区间，第一段加，第二段不变，第三段减。$O(n\log n)$
对于所有的$R$，计算存在多少叶子值$\le 2$，把个数累加进答案。$\log n$
因为所有的数都是正整数，所以可以用线段树维护最小值和最小值的个数，次小值和次小值的个数。