@suixinhita 2020-11-29T03:04:40.000000Z 字数 4740 阅读 455

连山程设复（预）习

ACM oi

首先先给自己写个目录好吧：

数据结构

主席树

struct data{
int ls,rs,cnt;
}t[N];
int root[N],pre[N],next[N],a[N],b[N],n,m,n_,cnt,v;
void insert(int l,int r,int a,int &b)
{
    b=++cnt;
    t[b]=t[a];///t[a]=t[b];
    t[b].cnt++;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(v<=mid) insert(l,mid,t[a].ls,t[b].ls);
    else insert(mid+1,r,t[a].rs,t[b].rs);
    }
//l r区间 a b时间
int get(int l,int r,int a,int b)
{
    if(r<v)return 0;
    if(l>=v)return t[b].cnt-t[a].cnt;
    int mid=(l+r)>>1;
    return get(l,mid,t[a].ls,t[b].ls)+get(mid+1,r,t[a].rs,t[b].rs);
}

树状数组（逆序对）

图论
- 树剖

高级不推荐算法，一般出现在 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;
}

查询修改（子树）

其实就是一个区间修改，因为无论怎么进行轻重划分，子树肯定是一个连续的序列。
- 计算几何
- 数论
- 字符串
- 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;
    }
}

其他杂七杂八的东西
- CDQ分治
- 平面图转对偶图
- 差分约束
差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成 $d[a]+w<=d[b]$ 时，我们求最长路。整理成 $d[a]+w>=d[b]$ 时，我们求最短路。当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。也就是开始各点不符合条件，后来通过减小变得符合了，所以一定是符合条件的最大值。既然是求最大值，并且是减小各点距离，也就是把各点由数轴的右侧向左侧拉，所以我们一定要选择一个最终在数轴最左侧的点，并初始化为 $0$ ，把所有正无穷的点拉近到符合不等式。最长路同理。最短路求的是最大值，最长路求的是最小值。
- 逆元
  费马小定理：假如 $p$ 是质数，且 $gcd(a,p)=1$ ，那么 $a(p-1)≡1（modp）$ 。即：假如 $a$ 是整数， $p$ 是质数，且 $a,p$ 互质(即两者只有一个公约数1)，那么 $a$ 的 $(p-1)$ 次方除以 $p$ 的余数恒等于 $1$ 。
  即快速幂：

ll quick_pow(ll x,ll k)
{
    ll an=1;
    for(ll i=k;i;i>>=1,x=x*x%B)
        if(i&1)    an=an*x%B;
    return an;
}

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

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

$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;
}

并查集

int find(int x)
{
    if(fa[x]==x)    return x;
    int an=find(fa[x]);
    off[x]=(off[x]+off[fa[x]])%m;
    return fa[x]=an;
}

网络流

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;
}

最小费用流

辛普森积分
先贴一个椭圆求面积的。

const double eps=1e-10;
double a,b,l,r;
double f(double x)
{
    return b*sqrt(1.0-(x*x)/(a*a));
}
double simp(double l,double r)
{
    return (f(l)+4*f((l+r)/2)+f(r))*(r-l)/6.0;
}
double simpson(double l,double r)
{
    double mid=(l+r)/2.0;
    double ans=simp(l,r);
    if(fabs(ans-simp(l,mid)-simp(mid,r))<eps)    return ans;
    else    return simpson(l,mid)+simpson(mid,r);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf%lf%lf%lf",&a,&b,&l,&r);
        double ans=simpson(l,r);
        printf("%0.3lf\n",ans*2);
    }
    return 0;
}

树上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];
}

连山程设复（预）习

内容目录