· 6/6
火星人 prefix
好神奇的一道题。
先回忆一下做这个题的时候都出现了哪些问题。
- 首先是一些比较无脑的错误，比如传参的时候传错了，或者是分裂的时候左右点传反了
- 然后就是分析的分裂左右子树的条件错了的问题
- 最后就是这个\(hash\)的问题了
哈希的问题挺神奇，就是建点的时候要更新他那个哈希值，因为后面可能会直接调用就不会再更新了。
然后阶段性总结一下平衡树：
- 平衡树维护的是线性区间的数的操作和统计
- 可以像线段树那样维护一段值域，这一定是连续的，因为他会内部进行一个排序。
- 因为父亲节点不是一个抽象出来的代表一个区间的节点，而是一个具体的节点，所以要维护相应的区间的东西的话还需要一定的抽象能力
- 相较于线段树，平衡树可以完成维护较大的值域、插入、删除等操作，并且可以支持由下到上更新，也就是“上传标记”
- 平衡树常数较大
· 6/7
星系探索
做这个题的教训就是：会正确分析时间复杂度真的很重要。
以为暴力求排名很费时间，导致浪费了两个小时瞎想。
概率与期望
- 概率：某事发生的可能在总可能中的占比
\(p[A]\) : \(A\)的概率
\(p[AB]\) : \(AB\)同时发生的概率
\(p[A|B]\) : 在\(B\)发生时\(A\)的概率
全概率公式：
条件概率：
由上可推
贝叶斯公式：
- 期望：一个函数在不同情况下的取值的“调和值”
\(E[f[x]]=\sum_i f[B_i]*p[B_i]\)
妈耶我这个调和值的比喻实在是太恰当了
这个“调和值”就说明了期望的性质实际上跟权值是差不多的
期望的逆推
理解了好半天才明白的。
每一分钟从M个球中随便选出一个球涂成红色并放回，无论所选的球是不是红色。求将所有球涂成红色的时间的期望值。
可以设\(E[x]\)表示还有\(x\)个球时所需要的期望时间，则有\(E[M]=0\)，要求的就是\(E[0]\)。
把每一个\(E[i]\)拆开来看，他有\(i/M\)的概率更新到\(E[i]\)，又有\(1-i/M\)的概率更新到\(E[i+1]\)。
然后这么逆着推，就有了一种分解期望的方法：\(E[ 更新E[i]的部分 ]\) 和 \(E[ 更新E[i+1]的部分 ]\)。
然后分别计算，两边的权值分别从\(E[i]\)和\(E[i+1]\)逆推回来，再乘上相应的概率，就有：
这么一个神奇的式子。
概率是什么玩意
太难啦
· 6/8
聪聪和可可
给出一个\(n\)个结点的无向图，其中\(A\)在\(M（mouse）\)点，\(B\)在\(C(cat)\)点，\(A\)每次向周围或本节点等概率移动一格，而\(B\)每次向靠近\(A\)的方向移动两格，在每分钟内\(B\)先走\(A\)再走，求\(B\)抓住\(A\)所用的期望时间。
首先看到\(n<=1000\)就考虑二维\(dp\)嘛
然后就知道居然还可以暴力地求出点与点之间的最短距离
打了一个\(dijistra\)之后被邢老师点拨之后发现\(bfs\)更快
第一次把\(dp\)转移式子推正确了
没想到最后还被选择编号较小的点背刺了一刀
守卫者的挑战
\(n\)次挑战，每次挑战有\(p_i\)的概率成功，成功后可以获得一个碎片或者一个有一定容量的背包，只有至少胜利\(L\)次并且所有得到的碎片都能用背包装下才算做胜利。求胜利的概率。
注意，因为最多只能获得\(200\)个碎片，所以获得的背包大于\(200\)的部分直接就不要了。实际容量只是\(-200\)到\(200\)，再都加上个\(200\)就能用数组解决该问题了。
蚯蚓排队和这个有异曲同工之妙，都是用不着那么多的东西。
· 6/9
早上过来突然发现自己有了查看oi名字的权限？！
列队春游
有\(n\)个小朋友距离为一地站成一排，每个小朋友的视野为他到左边第一个身高大于等于他的小朋友的距离（特别地，第一个小朋友的视野为\(1\)）。给出\(n\)个小朋友的身高，他们随机站，求视野总和的期望。
首先列式子，然后可以发现一个肥肠厉害的转化：
对于每个小朋友而言，设一个\(p[i]\)表示这个小朋友视野为\(i\)的概率。
然后要算的就变成了视野大于等于\(i\)的概率。
那么设一个\(k\)表示比当前这个小朋友高或者等高的人数。
则：
然后对这个式子就可以展开，然后进行一系列的变化，然后就推出了这个式子：
可以推一推，需要用到这个式子：
闲思
正如同那个排队一样，小的在前，大的在后，这是利益最大化；小的在后，大的在前，这是绝对公平。
· 6/10
今天居然真的没有比赛，我哭死
关于dijistra
这两种写法都是正确的：
while(!que.empty()){
int y=que.top().second,cs=que.top().first;
que.pop();
if(dis[x][y]<cs) continue;
for(int i=pre[y];i;i=ed[i].next){
int z=ed[i].e;
if(dis[x][z]>dis[x][y]+w[y][z]){
dis[x][z]=dis[x][y]+w[y][z];
que.push(make_pair(dis[x][z],z));
}
}
}
while(!que.empty()){
int y=que.top().second,cs=que.top().first;
que.pop();
if(vi[y]) continue;
vi[y]=1;
for(int i=pre[y];i;i=ed[i].next){
int z=ed[i].e;
if(dis[x][z]>dis[x][y]+w[y][z]){
dis[x][z]=dis[x][y]+w[y][z];
que.push(make_pair(dis[x][z],z));
}
}
}
其原因就在于每个都保证了当前得到的点的存入队列的dis的确是正确的。
而所以这么写是不对的
while(!que.empty()){
int y=que.top().second,cs=que.top().first;
que.pop();
for(int i=pre[y];i;i=ed[i].next){
int z=ed[i].e;
if(dis[x][z]>dis[x][y]+w[y][z]){
dis[x][z]=dis[x][y]+w[y][z];
if(!vi[z]){
que.push(make_pair(dis[x][z],z));
vi[z]=1;
}
}
}
}
这么写直接就排序错了，输出的不是按真实值排名的点，蓝白点思想出大问题。