From e97ca5f48404b857c44e4a5efebfbb2acd51897e Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Thu, 19 Nov 2020 21:25:59 -0500 Subject: [PATCH] style: format markdown files with remark-lint --- docs/misc/rand-technique.md | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/docs/misc/rand-technique.md b/docs/misc/rand-technique.md index 7344c9de..ef8e0709 100644 --- a/docs/misc/rand-technique.md +++ b/docs/misc/rand-technique.md @@ -33,7 +33,7 @@ author: Ir1d, partychicken, ouuan, Marcythm, TianyiQ 这样做,单次的正确率是 $\big(\frac 23\big)^n$ 。将算法重复运行 $-\big(\frac 32\big)^n\log \epsilon$ 次,只要有一次得到解就输出,这样即可保证 $1-\epsilon$ 的正确率。(详见后文中“自然常数的使用”和“抽奖问题”) -**回顾** :本题中“解空间”就是集合 $\{R,G,B\}^n$ ,我们每次通过随机施加限制来在一个缩小的范围内搜寻“目标解”——即合法的染色方案。 + **回顾** :本题中“解空间”就是集合 $\{R,G,B\}^n$ ,我们每次通过随机施加限制来在一个缩小的范围内搜寻“目标解”——即合法的染色方案。 ### 例: [CodeChef SELEDGE](https://www.codechef.com/problems/SELEDGE) @@ -189,10 +189,9 @@ $$ - 因为只需考虑大小 $\geq \dfrac n3$ 的团,所以需要考虑的左侧团 $L$ 和 右侧团 $C_R$ 的数量也大大减少至约 $1.8\cdot 10^6$ 。 - 现在的瓶颈变成了求单侧的某一子集的权值和,因为这需要 $O\big(2^{|V_L|}+2^{|V_R|}\big)$ 的预处理。 - 解决方案:在 $V_L,V_R$ 内部再次折半;当查询一个子集的权值和时,将这个子集分成左右两半查询,再把答案相加。 -- 这样即可通过本题。 +- 这样即可通过本题。 - -**回顾** :一个随机的集合有着“在划分出的两半的数量差距不会太悬殊”这一性质,而我们通过随机划分获取了这个性质。 + **回顾** :一个随机的集合有着“在划分出的两半的数量差距不会太悬殊”这一性质,而我们通过随机划分获取了这个性质。 ## 随机化用于哈希 @@ -272,7 +271,7 @@ $$ 分析前者发生的概率: -- 观察:对于任意的 $A\neq B; A,B\leq N$ 和随机选取的质数 $Q\leq Q_{max}$ ,一定有: +- 观察:对于任意的 $A\neq B; A,B\leq N$ 和随机选取的质数 $Q\leq Q_{max}$ ,一定有: $$ \mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{\log N \log Q_{max}}{Q_{max}}\Big) -- 2.11.0