Blog E

路漫漫其修远兮,吾将上下而求索。

Probability and Computing 第七章笔记

突然发现,上次发博客还是上次了,因此,我打算打算一下,简单写个笔记记录一下这章内容。 Notation $r^t_{i,j}$: 从i开始走,t时刻恰好第一次到j的概率 $h_{i,j}$: 从i开始走,第一次到j的期望步数 Definition 略 Classification of States 连通性 accessible: $\exist n,\text{ s.t.} P^n_{i,j}>0$ communicate: i,j 双向联通 若整个链是一个 communicating class / 对应的图强连通,则称其 irreducible...

Probability and Computing 第五章作业题

题目 模拟代码(第二问) bool f[MXN]; #define ls(x) ((x) << 1) #define rs(x) (((x) << 1) | 1) #define bro(x) ((x) ^ 1) #define fa(x) ((x) >> 1) queue<ll> q; ll n, cnt; ll chk(ll r) { ll cnt = (ll)f[r] + f[ls(r)] + f[rs(r)]; if (cnt == 2) { if (!f[r]) return r; ...

Probability and Computing 第四章笔记

Moment Generating Functions \[M_X(t)=\mathbb{E}[e^{tX}]\] 性质 $M_X^{(n)}(0)=\mathbb{E}[X^n]$ X,Y 独立,则 $M_{X+Y}(t)=M_X(t)M_Y(t)$ Chernoff Bounds 根据上述生成函数和马尔可夫不等式 可以得到: $\Pr(X\ge a)\le \min_{t>0}\frac{\mathbb{E}[e^tX]}{e^{ta}}$ $\Pr(X\le a)\le \min_{t<0}\frac{\mathbb{E}[e^tX]...

Probability and Computing 第三章笔记

Markov’s Inequality 若 X 恒大于0,则: \[\Pr(x\ge a)\le \frac{\mathbb{E}[x]}a\] Moments 定义 kth moment of a random variable X is $\mathbb{E}[x^k]$ variance $\mathrm{Var}[X]=\mathbb{E}[X^2]-(\mathbb{E}[X])^2$ covariance $\mathrm{Cov}(X,Y)=\mathrm{E}[(X-\mathrm{E}[X])(Y-\mathrm{E}[Y])]$ 定理 \(\...

Probability and Computing 第二章笔记

Linearity of Expectations (不要求独立) \[\mathbb{E}[\sum X_i]=\sum \mathbb{E}[X_i]\] 琴生不等式 $f(x)$为凸函数,则$\mathbb{E}[f(x)]>f(\mathbb{E}[x])$,利用泰勒展开证明即可. binomial random variable \(\Pr(X=j)=\binom n j p^j (1-p)^{n-j}\) 性质 $\mathbb{E}[X]=np$ 应用 考虑一个函数 S.每次调用它,S 都会递归调用 X 次自己.其中 X 是二项式概率分布的变量...

Probability and Computing 第一章笔记

最近看 Probability and Computing, 在此记录一些重要结论和有趣算法. Polynomial Identities 多项式次数为d,则x在[0,100d]随机取值,仅有$\frac{1}{100}$概率错误(根据代数基本定理,f-g最多有d个根). 一些基本定义和引理: 概率定义 容斥原理 事件的独立性 条件概率 $\Pr(E|F)=\frac{\Pr(E\cap F)}{\Pr(F)}$ Veryfying Matrix Multiplication 给定三个方阵 A,B,C 快速验证 $A\times B=C$? 随机算法 随机...

并查集随机合并的复杂度

一把洛阳铲

似乎好久没有写博客了,其实写了一个EC-final游记,但是不太想发 今天来挖个坟,这是一年前我发的帖子关于并查集随机合并复杂度正确性,当时帖子底下有许多或对或错的感性证明。 在写带撤销并查集的时候,因为路径压缩只能保证均摊复杂度。所以往往需要写按秩合并,而这种随机合并的写法可以让你省去几秒钟的思考,省去几行代码,减少一点数组操作,增加一些常数。 今天又写了一个带撤销并查集的题,用到了这个写法。又想了想这种合并方法,似乎可以严谨证明,就写一下,以后可以放心这么写不被卡了。 注意:下文的证明基于以下这种先find再比较rnd的写法!别的写法可能被卡,详见上面帖子中我的回复 int...

2022ICPC沈阳区域赛游记

活学活用,论“批归一化”在算法竞赛中的运用

热身赛 rank 2,大概是 rp 全都给热身赛了吧。。。(虽然热身赛是纯拼手速和想题速度) 感觉这场区域赛区分度极低,四题有一百多队,五题有二十多队,而区分了不少队的 A 题也没啥思维含量,本来是个好想好写的问题,结果出题人生硬地加了一个单点,让代码变的繁琐不少。而除了这五题之外的题都比较有难度,做出来的不多。 最后五题 rank 27,金牌靠后,发挥略低于预期,不过也没啥影响。 上来发现 15 秒就有人过了 D,于是让 wky 看看 D, 在 6 分钟签到成功。 然后又发现 C 过了好多人,于是我就开了 C,简单分析发现 $l$ 和 $r$ 一定有一个卡着某一个 $A_i...

2021ICPC济南区域赛VP记录

打的还行

和破壁人及 wky VP 了去年的济南区域赛。最后排第 8,虽然离前 3 还有不少距离,但至少发挥没有之前两次 ICPC 预选赛那么拉跨。这次签到题很少,并且 E 题连写带调弄了一个多小时,差点都以为要寄了。感觉有几道题目很有意思,故记录一下思路。 (前面有两队是打星参加的) E 下文约定记号 $G_i=\{j\mid(i,j)\text{ is a magic link}\}$ 观察到 M 的大小比较蹊跷,于是猜想有 $O(NM)$ 做法。首先不考虑题目所求,想一下如何在不删点的情况下计算总分数。 考虑如下的一个交叉产生的代价如何计算: 凑了一阵均摊复杂度之后,可...

ICPC第一场网络预选赛游寄

CCPC被禁赛,只能打ICPC了

按照之前的开题顺序,我开中间四题。然后就发现 F 题是之前 HDU 的原题,然而是个重量级的数论,上次我们就没过。 读着题的时候,破壁人就说 L 很签,上机写了一会,又突然说假了。 于是我就上去签 H,在 17 分钟过了。这个 H 的题面就非常灵性,让我更深刻的理解了 CCPC “比赛中不能打开头文件”的规则。 H 题面: 啪的一下,很快呀 wky 就说 C 也是签到,遂在 22 min 通过。此时,由于我们手速飞快,排名在第五,这也是整场比赛排名最高的时候。 于是我开了 G,wky 开始构造 D。过了一会,wky 想出一个构造,于是开写,然而样例挂了。于是我就胡了一个 $...

icon