这场7题没啥难度，但之后是真的难开，补一道卡一道，本来是要补10题的，考虑难度和效果就改9题了。
A. Beta Go
待补，详见ZAwei的博客。
B. Build Roads
随机化。$n$较大时答案大概率为$n-1$，较小时暴力，注意$L=R$的情况。
C. Cat Virus
构造。考虑对题目增加限制：要求构造出来的必须是二叉树。当某点左子树答案为$A$，右子树答案为$B$，则该点子树的答案为$A\times B+1$，只有一个孩子的结点答案是孩子的答案$+1$，所以可以递归构造出$k$。
D. Dyson Box
签到。考虑重力向下，第$i$列高为$h_i$，答案就是
$有方块的位置数\times2+\sum_{i=1}^{n+1}|h_i-h_{i-1}|(h_{i+1}=0)$。
E. Evaluate Expression
F. Birthday Cake
字符串。hash老题了，考虑两个字符$a,b\ (len(a)\le len(b))$串拼接后合法的情况：
- $a,b$相同
- $b$的前$\frac{len(a)+len(b)}{2}$个字符是拼接后串的一半
$map$记录一下就行，小心被卡模数和自然溢出。
G. Grade Point Average
签到。
H. Adventurer’s Guild
签到。
I. Chemical Code
线段树。考虑当加入一个元素、数字、括号时产生的影响：
元素：相当于单点加，如果后继是数字则要：
- 减去数字的影响（区间除）
- 单点修改，加某个值
- 加上数字的影响（区间乘）
数字：相当于区间乘，如果前驱是括号则：
- 找到配对的另一个括号
- 将括号扩起的区间乘某个值
括号：如果后继是数字，处理方法和元素相同
但是，由于模数不是质数，这个区间除就很麻烦了（需要CRT）。但是考虑数字只有$1-9$，因此可以将复杂度$\times10$，懒标记永久化维护$1-9$在线段树上每个节点乘的次数，由于每次都是查询1到n，所以不用pushdown，常数还巨小。
1 |
|
J. Tuition Agent
K. Piggy Calculator
感觉很厉害，有时间就补。
L. Construction of 5G Base Station
概率dp。考虑用$f_{i,j}$表示$i$连到$j$位置的基站的概率，则有
$f_{i,j}=\frac{p_j}{1-\prod^{n}_{k=1}{(1-p_k)}}\prod_{i到k比j优先}(1-p_k)$
直观来理解，$p_j$下面那一串是$i$连遍所有基站都失败的概率，后面那一块就是$i$和优先于$j$的所有基站都匹配失败的概率。
【前置芝士1：一次试验为真的概率为$p$，如果失败会重复直到为真结束，则其期望结束次数为$\frac{1}{p}$】
（考虑等比数列求和 或 解方程：$E(x)=p\times0+(1-p)\times E(x)+1$即可证明）
设$E(x_i)$为匹配到基站$i$的人个数的期望，则有
$E(x_i)=\frac{p_i}{1-\prod^{n}_{k=1}{(1-p_k)}}\sum_{j=1}^{n}\prod_{j到k比i优先}(1-p_k)$
然后题解说，容易发现这东西后一块能用前缀和递推，（赛中感觉不可以递推就没搞，下次遇到这种最好打打草稿看看规律）
一顿操作能$O(n)$求出$i\in[1,n]$的$E(x_i)$，
（PS：这里$Hile$改了2h才过）
但是题目要求的是$E(\sum_{i=1}^{n}{x_i}^2)$，这时就要利用期望的线性性拆开了。
【前置芝士2：如果变量$X,Y$相互独立，则$E(X+Y)=E(X)+E(Y), E(XY)=E(X)E(Y)$】
$E(\sum_{i=1}^{n}x_i^2)=\sum_{i=1}^{n}E(x_i^2)$，
此时，对于每一个$E(x_i^2)$，$x_i$可以看作$n$个变量$y$之和，其中$y_i=1$表示第$i$个人连接了该基站，所以有
$E(x)=\sum_{i=1}^{n}E(y_i)$
原式可写为
$E((\sum_{i=1}^{n}y_i)^2)=(E(x))^2-\sum_{i=1}^{n}(E(y_i))^2+E(x)$
其中$\sum_{i=1}^n(E(y_i))^2$可以在求$E(x)$的过程中一起计算。
1 |
|
M. Matrix Problem
签到。