_WA自动机的blog

过期高中生。

发表于 更新于 分类于 阅读次数： Valine：
  1. 齐肯多夫定理：任意正整数可以被表示成若干个不连续的斐波那契数之和。
  2. 平面图的边数最多是3n-6.
  3. 树上一堆点的lca，就是它们dfs序最大和最小的两个节点的lca。
  4. 卡特兰数：
    \(\large C_1=1\)
    \(\large \forall n \geq 2, C_n=\sum_{i=1}^{n-1}C_i C_{n-i}=\binom {2n}{n}-\binom {2n}{n-1}\)
  5. 超级卡特兰数
    \(\large S_1=1\)
    \(\large \forall i \geq 2,S_i=S_{i-1}+\sum_{i=1}^{n-1}S_iS_{n-i}\)
    \(\large S_n=\sum_{i=1}^n \binom {n+i-1} {2i}C_i\)
    阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：

更新日志

2019.2.16

  • 修复Chtholly树代码中的错误
  • FFT板子更新为预处理单位复根的版本(多项式基本操作请移步多项式算法总结qwq)

2019.2.17

  • 新增NTT板子
阅读全文 »

发表于 阅读次数： Valine：

SAM为什么是神？在讨论这个问题之前，我们先讨论一下其他字符串数据结构相对于SAM究竟差在什么地方。

阅读全文 »

发表于 更新于 阅读次数： Valine：

鸽巢原理

  • 将\(n+1\)个球放入\(n\)个盒子，至少有一个盒子里有两个球

  • \(\large\mathrm{Ext.}\) 将\(\sum_{1\le k \le n}q_k-n+1\)个球放入n个盒子

    • 要么第一个盒子有至少\(q_1\)个
    • 要么第二个盒子有至少\(q_2\)个
    • 要么第三个盒子有至少\(q_3\)个
    • ...
    • 要么第\(n\)个盒子有至少\(q_n\)个
    • （上述条件至少满足一个）

平均值原理

对于\(n\)个变量\(x_1,x_2,...,x_n\)，最小值小于等于平均值，最大值大于等于平均值，当且仅当\(x_1=x_2=x_3=..=x_n\)取等

\(\text{Ramsey}\) 定理

\(6\)个人中，要么有\(3\)个人互相认识，要么有\(3\)个人互相不认识。

一般地，有：对于\(\forall n,m \in \mathbf{N^*}\)，存在一个\(N\),使得给\(K_N\)的边任意染色后，要么存在全为蓝色的\(K_m\)，要么存在全为红色的\(K_n\)。此\(N\)记为\(\mathrm{R}(n,m)\)。如\(\mathrm{R}(3,3)=6\)。

另外，该定理也可以推广到高维，但是好像没什么用。

二项式系数

组合恒等式

一行的和：

\[\sum_k \dbinom{n}{k}=2^n\]

分奇偶

\[\sum_k (-1)^n\dbinom{n}{k}=(1-1)^n=[n=0]\]

提取/吸收恒等式

\[\dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1} \Rightarrow m\dbinom{n}{m}=n\dbinom{n-1}{m-1}\]

组合意义：考虑每个元素被选出一次贡献为\(1\)，则大小为\(m\)的集合贡献为\(m\)。单独考虑每个元素，总的贡献为\(n\dbinom{n-1}{m-1}\)；考虑每个选出的集合，总的贡献为\(m\dbinom{n}{m}\)。二者应该相等。

上指标求和

\[\sum_{i\le n}\dbinom{i}{a}=\sum_{i\le n}\dbinom{i+1}{a+1}-\dbinom{i}{a+1}\]

平行求和法

\[\sum_{k\le n}\dbinom{r+k}{k}=\sum_{k\le n}\dbinom{r+k}{r}=\dbinom{r+n+1}{r+1}=\dbinom{r+n+1}{n}\]

发表于 更新于 阅读次数： Valine：

左偏树是一种最常用的可并堆。它除了满足堆性质（即根节点是整个子树中key值最小或最大的节点）之外，还有另外一个性质：该树是左偏的。顾名思义，对于每一个节点u，若既有左儿子ls又有右儿子rs，定义其“高度”\(\text{dis}(u)\)为到最近的叶子的距离，则\(\text{dis}(ls)\geq \text{dis}(rs)\)。直观理解就是左子树更深。

\(\textbf{Theorem 1.0}\)：对于节点个数为\(n\)的左偏树，其高度为\(\Theta(\lg n)\)。

  • \(\textbf{Proof}\)：对于一棵\(\text{dis}(u)=\text{h}\)的左偏树，节点最少时一定是满二叉树。即，对于左偏树，有：\(h \leq \log_2(n+1)\)

要实现左偏树，节点要记录以下信息：

1
2
3
4
struct Node
{
    int val,rt,ls,rs,dis;
}S[N];

左偏树最重要的操作（其实就是唯一的操作）是merge.下面实现函数\(\text{merge}(u,v)\)，功能为把u和v两棵左偏树（以下不区分节点和节点所代表的子树）合并，返回新树的根。

1
2
3
4
5
6
7
8
9
10
inline int Merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (S[x].val>S[y].val || (S[x].val==S[y].val && x>y)) swap(x,y); //保证x是最小的那个节点。
    S[x].rs=Merge(S[x].rs,y); //新树的根应为x。
    if (S[S[x].ls].dis<S[S[x].rs].dis) swap(S[x].ls,S[x].rs); //若右子树更深，交换左右子树，保持左偏性质
    S[S[x].ls].rt=S[S[x].rs].rt=x;
    S[x].dis=S[S[x].rs].dis+1;
    return x;
}

弹出堆顶元素时，记得要给堆顶节点的根重新赋值。因为如果不赋值的话，访问这个被删除元素并判断和其他节点连通性的时候会出现问题。\(\text{rt}(u)\neq \text{rt}(v)\)，判断错误。

完整代码如下（洛谷模板题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cassert>
#include <algorithm>

const int N=1e5+1000;

struct Node
{
    int val,rt,ls,rs,dis;
}S[N];

inline void swap(int &x,int &y){x^=y^=x^=y;}
inline int find(int x){return x==S[x].rt?x:S[x].rt=find(S[x].rt);}

inline int Merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (S[x].val>S[y].val || (S[x].val==S[y].val && x>y)) swap(x,y);
    S[x].rs=Merge(S[x].rs,y);
    if (S[S[x].ls].dis<S[S[x].rs].dis) swap(S[x].ls,S[x].rs);
    S[S[x].ls].rt=S[S[x].rs].rt=x;
    S[x].dis=S[S[x].rs].dis+1;
    return x;
}

inline void merge(int x,int y)
{
    if (S[x].val==-1 || S[y].val==-1) return;
    int u=find(x),v=find(y);
    if (u^v) S[u].rt=S[v].rt=Merge(u,v);
}

inline void poprt(int x)
{
    if (S[x].val==-1) return void(puts("-1"));
    x=find(x);
    printf("%d\n",S[x].val);
    S[x].val=-1;S[S[x].ls].rt=S[x].ls;S[S[x].rs].rt=S[x].rs;S[x].rt=Merge(S[x].ls,S[x].rs);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);S[0].dis=-1;
    for  (int i=1;i<=n;++i) scanf("%d",&S[i].val),S[i].rt=i;
    for (int i=1;i<=m;++i)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if (opt&1)
        {
            scanf("%d%d",&x,&y);
            merge(x,y);
        }
        else
        {
            scanf("%d",&x);
            poprt(x);
        }
    }
    // assert(0);
}

发表于 更新于 分类于 阅读次数： Valine：

辣鸡蒟蒻_WA自动机又出去集训辣！因为他太菜了不会语文，所以这篇游记写得很烂，请巨佬轻D...qaq.欢迎留言！

阅读全文 »