From 657e8d2fa5e5d4e0d43a28dba3cfc0fd1d84f9c4 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Mon, 7 Oct 2019 22:39:57 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/math/quick-pow.md | 2 +- docs/search/index.md | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/docs/math/quick-pow.md b/docs/math/quick-pow.md index d5ef6746..d6975def 100644 --- a/docs/math/quick-pow.md +++ b/docs/math/quick-pow.md @@ -77,7 +77,7 @@ long long binpow(long long a, long long b) { } ``` -模板:[Luogu P1226](https://www.luogu.org/problemnew/show/P1226) +模板: [Luogu P1226](https://www.luogu.org/problemnew/show/P1226) ## 应用 diff --git a/docs/search/index.md b/docs/search/index.md index 95f2d3e5..1e4fe560 100644 --- a/docs/search/index.md +++ b/docs/search/index.md @@ -46,7 +46,7 @@ 所谓 **meet-in-middle** , 就是让 DFS 的状态在中间的时候碰面。我们知道,如果一个暴力 dfs 有 $K$ 个转移,那么它的时间复杂度(大多数情况)是 $O(K^N)$ 的。那我们就想,当 $N$ 到达一定程度时,TLE 会变成必然。 -例题 [「USACO09NOV」灯Lights](https://www.luogu.org/problemnew/show/P2962) +例题 [「USACO09NOV」灯 Lights](https://www.luogu.org/problemnew/show/P2962) 我们正常想,如果这道题暴力 DFS 找开关灯的状态,时间复杂度就是 $O(2^{n})$ , 显然超时。不过,如果我们用 **meet-in-middle** 的话,时间复杂度将会变为 $O(2^{n/2} \times 2)$ 而已。 **meet-in-middle** 就是让我们先找一半的状态,也就是 $1$ 到 $\mathrm{mid}$ 的状态,再找剩下的状态就可以了。我们把前半段的状态全部存储在 `map` 里面,然后在找后半段的状态的时候,先判断后半段是不是都合法,就可以判断上半段有没有配对的上半段使得整段合法。 -- 2.11.0