星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

玄学算法/精彩DS总结 Vasuku

posted on 2018-09-18 17:58:20 | under Summary |

$31.Complementary\ Graph$

一种BFS可以在 $O(m)$ 的复杂度遍历出它补图的连通块个数及大小。过程如下:

  1. 建立一个链表把所有点连起来,然后随便从链表中找一个点BFS。
  2. 对于当前队首,将所有链表里没有与它连边且未被 $visit$ 的点 $push$ 进队列,并将它们从链表中删除并标记为 $visited$ 。
  3. 重复此过程进行多次BFS直到链表为空。在删除一个点的时候就可以顺便统计信息了。

复杂度证明的话,一条边最多会被经过两次,所以显然是最坏 $O(m)$ 的。
对于多组询问,假设询问 $K=\sum k$ ,如果要把复杂度卡到 $O(m)$ ,至少需要运用到 $O(\sqrt{m})$ 个点构造一个完全图也就是 $O(\sqrt{m}^2)=O(m)$ 才能卡满,所以最多询问 $O(\frac{K}{\sqrt{m}})=O(\sqrt{m})$ 次(假设 $K,m$ 同阶),也就是说复杂度不会超过 $O(m\sqrt{m})$ 。
实现上,判断是否有连边可以开个哈希表,注意遍历这个点的边作标记复杂度是错误的。

$32.Segment\ Tree\ Dividing\&Conquering$

(时间)线段树分治是一种离线思想,是把处理目标的存在时间的区间映射到线段树上,再利用一个可撤销的数据结构进行整体地回答问题与处理影响。
狭义上来说,线段树分治是考虑左边对右边的贡献,与CDQ分治是相似的;广义上来说,线段树分治是考虑外部对内部的贡献。
也就是说,这和线段树没什么关系。
$LOJ\ 121$ 动态图连通性
就是 $link,cut$ ,判断连通性三个操作。 $n\le 5000,q\le 5\times 10^5$
考虑进行线段树分治,显然每条边的存在区间是可以弄出来的,最后没被 $cut$ 的边就一直到 $q$ 。
我们对每个线段树上的节点都开一个 $vector$ ,把每个存在区间都存到至多 $\log$ 个 $vector$ ,这样空间复杂度是 $O(q\log q)$ 。
在询问时我们对线段树 $dfs$ ,利用一个不带路径压缩的启发式合并 $dsu$ ,每次 $dfs$ 到一个区间就 $merge$ 两个点并把更新的部分压入 $stack$ ,然后 $dfs$ 回溯的时候就把它撤销。
实现上我们可以这么写:

    void merge(int x,int y)
    {
        if(x==y)return;
        if(dep[x]<dep[y])swap(x,y);
        fa[y]=x;
        s[++tp]=pi(y,dep[x]==dep[y]);
        if(dep[x]==dep[y])++dep[x];
    }
    int find(int x){return fa[x]^x?find(fa[x]):x;}
    void ruin(int x)
    {while(tp>x)dep[fa[s[tp].fi]]-=s[tp].se,fa[s[tp].fi]=s[tp].fi,--tp;}

这样就可以直接减掉这次 $merge$ 的贡献,无论是 $siz,dep$ 都可以写了。
如果 $dfs$ 到了叶子,我们可以看这个点是否有询问,有询问的话就查一下两个点。因为 $dfs$ 的顺序实际上是按时间升序,所以可以直接用一个指针直接扫过去就可以了。时间复杂度是 $O(q\log q+q\log q\log n)=O(q\log q\log n)$ 。
简单证明一下,栈内最多有 $O(q\log q)$ 个节点,加上并查集的复杂度是 $O(\log n)$ ,所以 $push$ 的均摊代价是 $O(\log n)$ ,总复杂度就是 $O(q\log q\log n)$ 。这好像是个经典的势能分析
$BZOJ\ 4025$ 二分图
给定每一条边的存在区间,判断在某个时刻(实际上原题是一个 $[x,x+1)$ ]的时间段但差不多)这个图是否是二分图。
好像有一个NOIP题(关押罪犯)有这么一个东西:
对于一条边把 $(x,y'),(x',y)$ 合并,如果 $(x,y)$ 在一个连通块就不合法了。
这个东西同样适用于二分图。如果 $(x,y)$ 在一个连通块里,意味着这个图就不是二分图,因为 $x,y$ 被某个反点固定在了二分图的一端,这个比较好理解。
实现和上道题几乎相同,但注意你合并的是 $(find(x),find(y')),(find(x'),find(y))$ 。
$[HAOI2017]$ 八纵八横

线段树分治傻题。
                                            ——zsyzsy

该篇博客因为不可预知的信息危害导致内容失踪。

$33.Cuboid\ Union$

求长方体并的方法貌似不少,但 $set+$ 扫描线的方法应该是最为方便的。
具体来说,如果你把一个点固定为原点建立三维直角坐标系,你可以发现,从后 $(y)$ 往前,以 $1$ 为长度单位把长方体切片的话,每一片的面积 $(x,z)$ 应该是不断增加的,且应该呈一个锯齿状——即从左到右各个组成的矩形高度单调不增。
所以我们可以用一个 $set<pair>$ 来维护当前切片的各个矩形的长和宽,因为是倒着插,所以实际上是一个添加的过程。
考虑当前切片比上一个切片增加的一个点 $(x,y)$ ,它增加的面积应该是把一些锯齿合成一个锯齿。
我们可以利用 $lower\_bound$ 找到第一个比它长的锯齿,为此应该添加 $(neko,0),(0,neko)$ 两个边界。
然后从右往左 $erase$ ,增加的面积除了第一块要特判一下,其他的都是原本的长乘上 $\Delta$ 高。
直到下一个矩形的高已经不小于它了就可以 $break+insert$ 了。在这其中已经更新好了答案。时间复杂度是 $O(n\log n)$ ,因为组成锯齿的矩形数量最多 $O(n)$ 个。
以上内容请务必画图理解。

$34.Tree\ Hash$

这里介绍一种还算有效的有根树哈希方法。
首先 $dfs$ ,把所有的 $Hash[v]$ 拿出来排序。
然后 $Hash[u]=siz[u]\sum_{i}Hash[v]p^i$ 。
但注意可能会出现小树同构的情况,就是两棵小树一样,计数题中可能会把两种同构情况算作一种方案,因此这里要注意一下。
为什么会在下面的上面呢,因为这原来是 $53.$ ,因为计算几何太长了就和它替换了一下。

$35.Hash$

是不是很意外我还不会 $Hash$ 啊 $qwq$
一般来说,如果要匹配两个字符串中的子串,要把它们统计一下哈希前缀和和次幂的前缀和(就是你哈希乘的是多少)。 匹配的时候,用

ht[r]-ht[l-1]*mpow[r-l+1]

两个子串的这个东西是相等的话,那就是相等的。

$36.Fuka\ Ben/Fukua\ Beng$

$\huge\texttt{肥}_{\small\texttt{泵}^{\large\texttt{话}}}^{\large\texttt{克}_{\tiny\texttt{的}^{\small\texttt{说}}}}$ $\huge\texttt{一}_{\small\texttt{都}^{\large\texttt{不}}}^{\large\texttt{句}_{\small\texttt{信}\large\texttt{得}}}$

1.搜索树上线段树合并
$Beng$ 哥非常热爱线段树合并。
2.“这个题有好多枝可以剪!”
“这题有好多枝可以剪!”——oyiya
“减什么枝?这题直接容斥就可以了。”——Beng
然后发现了这题不剪枝复杂度是错的。
“ $Faker\_Beng$ 啊,你怎么不剪枝啊?”
” $\cdots\cdots$ 这个题有好多枝可以剪!“
3.“平衡树挺好的啊?”
“ $Beng$ 哥,我想把范围出高一点,但是出高一点要用 $Splay\cdots\cdots$ ”——Shenwei
“平衡树挺好的啊?” ——Beng
4.“(代码长度)小的就是大的,大的就是小的!”
5.“A是不可能让你A的。”
“ $Beng$ 哥,你看看 $result$ ,这题有多少人A掉?”——Shenwei
“ $A$ 是不可能让你 $A$ 的。”——Beng
6.“ $10^7\times 500$ 怎么会爆(int)啊?!”

“这题答案可能到多少啊?”——Shenwei
“哎呀不会爆不会爆, $10^7\times 500,5e8$ 怎么会爆啊?!”——Beng
7.“NOIp2018之前的一些想法”
从前的我意气风发,现在的我迷茫无助。

停课让我安逸,让我觉得畏惧,甚至会出现一直颓废下去的恐怖想法,但必须要明白停课不是来搞颓的,而是真正的孤注一掷 。

了解我的人都知道我的高一有多么灰暗,在去年这个时候就一败涂地,甚至将要一蹶不振。但这或许是最后一次机会了,希望我能坚持到底。

以后我会把每天做了什么挂上来(向学 yyb 神犇学习!),以及每天考试挂分的原因放上来,及时总结方法,希望快点将状态调整过来,迎接挑战。

中秋之夜,还有 $46$ 天,加油!

希望各位能与我互相监督。分享我最近看的一本书中一句话与各位共勉!

长跑的目的不是更快,而是更强。 ------《强风吹拂》

8.僵硬 $Fake$
“弱肉强食 $\cdots\cdots$ ”——Shenwei
“我好弱的。”——Beng

“怎么说咧,无话可说。”——Shenwei
“肖大佬强得无话可说。”——Beng
9.当 $Faker$ 被问“你有没有 $A$ 一道题”且他已经 $A$ 时
“哎我都是抄(肖大佬)的。”/“大同小异大同小异。”——Beng
10.“你没改说明你不屑于改”
“肖大佬你肯定改了这道题”( $fkb$ 指向一道 $zzq\ slide$ 里的神仙题)——Beng
“那要是我没改怎么办咧?”——Shenwei
“你没改说明你不屑于改。”——Beng
11.云玩家的嘲讽
“ $I\ Wanna$ 不随便玩。”
12 $Fake\ Beng$ 最爱的三样东西
线段树合并、后缀自动机、 $bitset$ 。
“直接线段树合并”——Beng
“哎别用 $SA$ ,用 $SAM$ 就可以了”——Beng
“你就用 $\_find\_first,\_find\_next$ 优化一下这个过程”——Beng
13.成独分子
(盯着成都市第七中学的 $OIerDb$ )原来成都和四川是一起算的名额啊!——Beng
14.传统艺能
$Faker\_Beng$ 热衷于 $OIerDb$ ,并每天都要用它来 $orz$ 机房的人和机房外的人。
15.对拍
拍一拍有助于身心健康。——Beng

$37.Tournament$

其实竞赛图的题我做得非常非常少。
$Landau's\ Theorem$
兰道定理指的是, $$\sum_{i=1}^nd_i\ge\binom{i}{2}$$ $d_i$ 指的是出度从小到大的排序序列,且 $i=n$ 时两边取等号。
证明其实比较简单,竞赛图的任意点集都满足 $\sum_{i\in S}d_i\ge\binom{\vert S\vert}{2}$ ,这个比较显然,点集内的任意两个点都给予了1的贡献。
而且一个简单完全图的边数就是 $\binom{n}{2}$ ,竞赛图的度数和也是如此,所以定理本身是比较简单的。考虑 $$\binom{n}{2}=\sum_{i=0}^{n-1}i\le n\times \max(a_i)$$ ,这也意味着当给定出度序列时,点个数的大小是 $O(\max(a_i))$ 的,其实最大也就是 $2\max(a_i)+1$ ,简单地推一下就好了。
依靠这个,我们可以作出限制,进行操作。

$38.Derangement$

之所以要写这一篇主要是因为 $zhou888$ 太神了,加上 $Beng$ 哥博客又写得不清不楚,于是就开一下坑。
经典的错排问题指的是求有多少个排列 $\{p_i\}$ 满足 $\forall i,p_i\neq i$ 。我们稍微将它扩展一下,就是存在一个排列 $\{s_i\}$ ,求有多少个排列满足 $\forall i,p_i\neq s_i$ 。

1. $O(n)$ 递推

很经典的式子。
$$f[n]=(n-1)(f[n-2]+f[n-1])$$
考虑一下这个式子的意义,我们新填一个数 $x$ ,首先这个数不会填到被限制的位置,然后被占了位置的那个数(这个数指的是被限制不能填 $x$ 填的那个位置的对应的数 $y$ ,下文中用 $lim[x]$ 表示x不能填到 $lim[x]$ 这个位置)如果填到限制自己的位置,那么其它数就可以直接错排,这样的方案数就是 $f[n-2]$ ;否则你可以理解成使 $lim[y]=lim[x]$ ,然后 $n-1$ 个数继续错排,方案数是 $f[n-1]$ 。

2. $O(n)$ 容斥

这个相对来说倒是更好理解。
$$\sum_{i=0}^n(-1)^i\frac{n!}{i!}$$
简单来说,我们枚举有几个位置放在原位,其它位置随便乱排。
应该可以感性理解这个东西,所以我们就当它是对的

3.继续扩展

我们考虑这样一个问题:其中的 $k$ 个数可以不满足限制。
我们可以用一个 $O(nk)$ 的 $DP$ 解决问题。
令 $dp[i][j]$ 表示填了前 $i$ 个数,其中有 $j$ 个数可以不满足限制的方案数。
首先 $j=0$ 的情况和错排一模一样,直接转移:
$$dp[i][0]=(i-1)(dp[i-2][0]+dp[i-1][0])$$ 然后我们考虑 $j>0$ 的情况: $$dp[i][j]=dp[i-1][j-1]+dp[i][j-1]$$
这个式子怎么理解呢?
首先 $dp[i-1][j-1]$ 比较好理解,就是这个数 $x$ 就填在 $lim[x]$ 上,那就是其它的 $i-1$ 个数去排;如果这个数不填在那个位置,不就相当于这 $i$ 个数只有 $j-1$ 个可以不满足限制的数了?那就是那一部分排列的方案数,加起来就可以了。

4.变得更快

这部分是用来应付毒瘤出题人的。
注意到,如果把 $i,j$ 交换,那么这个 $j>0$ 的转移是与组合数的递推一模一样的形式。
那么我们只要 $O(n)$ 处理出 $j=0$ 的情况,也就是这个奇怪的转了一下的杨辉三角的第一行,大概就可以用一个组合数直接算出答案了。因为没有实现很虚啊不知道怎么写
不过这总结也差不多了吧,或许也有更优秀的实现方式 $(O(1)?)$ ,欢迎联系我这小蒟蒻x
【话说感觉现在写总结越来越长越来越喜欢分阶段了啊