NOIP复习

复习

图论

1. 拓扑
2. 最短路（差分约束）
3. 最小（次小生成树）
4. lca （倍增，树剖，dfs+rmq）
5. 强连通，割点，割桥
6. 二分图（匹配，染色）
7. 欧拉回路

拓扑

拓扑的作用是将一个图转化成一个序列，有以下几种用法：
· 判断一个序列是否存在（根据条件建图看能不能跑出来）
· 判断是否有环（能不能跑出来，能就没有，不能就有）
· 方便 dp 因为拓扑后没有后效性
· 其他

拓扑的实现

$bfs$ 的实现，队列里维护的是入度为 $0$ 的节点，在访问后将边删除，$bfs$ 访问的序列就是拓扑序，一个正常的拓扑序最后是会把所有的点更新为入度 $0$ 的。

while(!q.empty())
{
    int u=q.front();q.pop();ans[++cnt]='a'+u-1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(--in[v]==0)  q.push(v);
    }
}

最短路

spfa

最短路算法，在对负边的处理上有独到的方式，$dfs$ 判负环有奇效。
* 还可以用来搞差分约束，推公式，最大值用最长路，最小值最短路。
时间复杂度不稳

dfs判负环

bool dfs_spfa(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[v]>dis[u]+e[i].v)
        {
            dis[v]=dis[u]+e[i].v;
            if(vis[v])  return 0;
            if(!dfs_spfa(v))    return 0;
        //  else    return 0;
        }
    }
    vis[u]=0;
    return 1;
}

dij

负边不稳，时间稳。主要是重载。

struct  node
{
    int no,dis;
    friend bool operator < (node x,node y)
    {
        return x.dis>y.dis;
    }
};
int head[N];
int dis[N],n,m,s,gs;
void add(int fr,int to,int v)
{
    gs++,e[gs].to=to,e[gs].v=v,e[gs].next=head[fr],head[fr]=gs;
}
void dij()
{
    priority_queue<node>q;
    node ori;
    ori.dis=0,ori.no=s;
    q.push(ori);
    while(!q.empty())
    {
        node U=q.top();q.pop();
        int u=U.no;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].v)
            {
                dis[v]=dis[u]+e[i].v;
                node V;
                V.dis=dis[v],V.no=v;
                q.push(V);
            }
        }
    }
}

最小生成树

一个贪心算法，可以用来做许多事情。需要用到并查集，个别时候需要做到重建图。记得分开。

lca

树上dp，树上维护都需要用到，非常基础有用。比较稳妥的是倍增，然后比较狠的是树剖，不修改的是打死也不能写树剖的。

倍增

可以在里面嵌套 $dp$.

void add(int fr,int to)
{
    gs++;e[gs].to=to,e[gs].next=head[fr],head[fr]=gs;
    gs++;e[gs].to=fr,e[gs].next=head[to],head[to]=gs;
}
//双向边注意
int dep[N],fa[N];
bool vis[N];
void dfs(int u,int f)
{
    fa[u]=f;vis[u]=1;
    dep[u]=dep[f]+1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!vis[v]) dfs(v,u);
    }
}
int anc[20][N];
void init()
{
    for(int i=1;i<=n;++i)   anc[0][i]=fa[i];
    for(int i=1;i<=19;++i)
        for(int j=1;j<=n;++j)
            anc[i][j]=anc[i-1][anc[i-1][j]];
}
int query(int x,int y)
{
    if(dep[x]<dep[y])   swap(x,y);
    int len=dep[x]; /////////// 和RMQ不同的地方。 
    int lo=-1;
    while(len)  len>>=1,lo++;
    for(int i=lo;i>=0;--i)
        if(dep[anc[i][x]]>=dep[y])
            x=anc[i][x];
    if(x==y)    return x;/////
    for(int i=lo;i>=0;--i)
        if(anc[i][x]!=anc[i][y])    ///////和树剖一样 
            x=anc[i][x],y=anc[i][y];
    return fa[x];
}

树剖

高级不推荐算法，一般出现在 T3 除非 T1 已经 A 了，T2 出不来正解再尝试。主要是要保证线段树和查询的正确性。

两个dfs和查询修改的代码。

void dfs1(int u,int fat)
{
    fa[u]=fat;
    dep[u]=dep[fat]+1;
    size[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=fat)
        {
            dfs1(v,u);
            size[u]+=size[v];
            if(size[v]>size[son[u]])    son[u]=v;
        }
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    pos[u]=++cntp;
    if(son[u])  dfs2(son[u],tp);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=fa[u]&&v!=son[u])
            dfs2(v,v);
    }
}

查询修改（路径）

int max_(int x,int y)
{
    if(x==y)    return v[x];
    int f1=top[x];
    int f2=top[y],l,r;
    int ans=-inf;
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2]) 
        {
            swap(x,y);
            swap(f1,f2);
        }
        l=pos[f1],r=pos[x];
        ans=max(ans,T.query_max(l,r));
        x=fa[f1],f1=top[x];
    }
    if(dep[x]<dep[y])   swap(x,y);
    l=pos[y],r=pos[x];
    ans=max(ans,T.query_max(l,r));
    return ans;
}

查询修改（子树）

其实就是一个区间修改，因为无论怎么进行轻重划分，子树肯定是一个连续的序列。

强连通，割点，割桥

强连通是有向图中的，割点割桥是无向图的。
强连通栈里面是点，割点是边，割桥是点。
统一采用 tarjan

强连通

可能会用到缩点重建图，注意图要分开，缩点之后是个DAG，之后大多数会进行一个 dp 。单纯的强连通是太少见了。

void tarjan(int u)
{
    low[u]=dfn[u]=++time;
    instack[u]=1;stack[++top]=u;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else    if(instack[v])//****必须要判。 
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        int tmp,tot=0;
        cnt++;
        do
        {
            tmp=stack[top--];
            instack[tmp]=0;
            tot++;
        }while(tmp!=u);
        if(tot==1)  cnt--;
    }
}

割点

割点的话，注意维护的是边，割点和强连通是一个德行，但是需要判一些返祖情况，建议背一下代码。
注意要记录子结点数，存的是边，和返祖边的讨论。

void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++time;
    int son=0;/////
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            son++;
            stack[++top]=i;
            tarjan(v,u);
            if(low[v]>=dfn[u])
            {
                int tmp,tmp_u,tmp_v;
                cnt++;is_cut[u]=1;
                do
                {
                    tmp=stack[top--];
                    tmp_u=e[tmp].fr;
                    tmp_v=e[tmp].to;
                    if(belo[tmp_u]!=cnt)    belo[tmp_u]=cnt;
                    if(belo[tmp_v]!=cnt)    belo[tmp_v]=cnt;
                }while(tmp_u!=u||tmp_v!=v);
            }
            else    low[u]=min(low[u],low[v]);
        }
        else    if(fa!=v && dfn[v]<dfn[u])  
        {
            low[u]=min(low[u],dfn[v]);///注意这里的dfn，tarjan写dfn和low是一样的,但是这里可能遇到返祖的现象
            stack[++top]=i;
        }
    }   
    if(fa==0 && son<2)  is_cut[u]=0;//高级注意
}

二分图

主要考匹配和染色，匹配就写网络流，染色写dfs。
染色不会单独考，但是考的话一般是用来划分集合的，鉴于只能划分两个集合，其实应该是很好看出来的。

网络流dinic

主要是关注一下数据范围，网络流跑不了很大的数据，还有就是边一定要开够，尽量别开爆。

struct data{
    int to,next,f;
}e[M*M*2];////开边注意 
int head[N<<1],gs,n,m,e_;
void add(int fr,int to,int f)
{
    gs++,e[gs].to=to,e[gs].f=f,e[gs].next=head[fr],head[fr]=gs;
    gs++,e[gs].to=fr,e[gs].f=0,e[gs].next=head[to],head[to]=gs;
}
int now[N<<1],dis[N<<1],s,t;
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int> q;
    dis[s]=0;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].f)  
                dis[v]=dis[u]+1,q.push(v);
        }
    }
    if(dis[t]==-1)  return 0;
    return 1;
}
int dfs(int u,int f)
{
    if(u==t)    return f;
    int su=0,ff;
    for(int i=now[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[v]!=dis[u]+1)    continue;////////不是小是加1 
        ff=min(e[i].f,f);
        ff=dfs(v,ff);
        e[i].f-=ff,e[i^1].f+=ff;
        su+=ff;f-=ff;
        if(e[i].f)  now[u]=i;///当前弧的更新不要忘。
        if(su==f)   return su;//一个小优化 
    }
    if(su==0)   dis[u]=-1;
    return su;
}
int dinic()
{
    int an=0;
    while(bfs())
    {
        for(int i=s;i<=t;++i)   now[i]=head[i];
        an+=dfs(s,maxx);
    }
    return an;
}

数论

1. gcd , exgcd
2. 欧拉函数，素数筛
3. 快速幂，矩阵快速幂。（矩阵乘法加法逆元不一样，主要用来优化递推。）

gcd , exgcd

gcd

ll gcd(ll a,ll b)
{
    while(a%b)
    {
        ll t=b;
        b=a%b;
        a=t;
    }
    return b;
}

exgcd

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1,y=0;return a;}
    ll k=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return k;
}

欧拉函数和埃氏筛

埃氏筛

for(int i=2;i<=n;++i)
{
    if(!vis[i]) 
        prime[++cnt]=i,is_p[i]=1;
    for(int j=1;i*prime[j]<=n&&j<=cnt;++j)//主要是判定
        vis[i*prime[j]]=1;
}

欧拉函数

需要记住的3个规律

1.若$a$为质数, $phi[a]=a-1$;
2.若$a$为质数, $b mod a=0,phi[a*b]=phi[b]*a$
3.若$a,b$互质, $phi[a*b]=phi[a]*phi[b]$

意义是比它小的数里面与其互质个数。

void get_tab()
{
    for(int i=2;i<=n;++i)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j)
        {
            int f=i*prime[j];vis[f]=1;
            if(i%prime[j]==0)
            {
                phi[f]=phi[i]*prime[j];
                break;
            }
            else    phi[f]=phi[i]*(prime[j]-1);
        }
    }
}

矩阵快速幂

必须给一下矩阵乘法的使用方式————矩阵快速幂优化递推公式转移（注意这个递推公式是加号，只有乘法是不行的，而且一般情况下，转移矩阵是可以直接构造的。

给个例题，包括转移矩阵的构造。
转移公式如下：

$f[i][j]=f[i-1][j]+f[i-1][(j-1)$%$k]$

然后需要做的是构造 $n*n$ 的矩阵，然后在 每一个$j$ 和 $(j-1)$%$k$处变为 1.

给个板子。

struct mar{
    ll c[51][51];
    mar friend operator *(mar a,mar b)
    {
        mar y;
        for(int i=0;i<k_;++i)
            for(int j=0;j<k_;++j)
            {
                y.c[i][j]=0;
                for(int k=0;k<k_;++k)
                    (y.c[i][j]+=(a.c[i][k]*b.c[k][j]))%=p;
            }
        return y;
    }
};
mar quick_pow(mar x,ll c)
{
    mar an;
    memset(an.c,0,sizeof(an.c));
    for(int i=0;i<k_;++i)   an.c[i][i]=1;
    for(ll i=c;i;i>>=1,x=x*x)
        if(i&1)
            an=an*x;
    return an;
}

数据结构，没什么好说的，字典树注意一下建立新的节点。

其他的

二分

写成 $r-1 , l+1$ 形式。

离散化

直接复制出来，sort，二分查找。不会被同样的数卡掉。

KMP

话不多说，背吧。

void get_next(char c[],int cl)
{
    for(int i=2;i<=cl;++i)
    {
        int j=fail[i-1];///////////
        while(j&&c[i]!=c[j+1])  j=fail[j];
        if(c[i]==c[j+1])    j++;//////////
        fail[i]=j;
    }
}
void check(char f[],char c[],int fl,int cl)
{
    get_next(c,cl);
    int j=0;
    for(int i=1;i<=fl;++i)
    {               /////////不用找上一个字母的失配点 
        while(j&&f[i]!=c[j+1])  j=fail[j];
        if(f[i]==c[j+1])    j++;
        if(j==cl)   ans[++ans[0]]=i-cl+1;
    }
}

区间dp

先长度后端点，注意判断方式。

背包

注意成立条件就行了。