【2019.9.17】Za

Za

yyb Fibonacci的性质

  1. \(gcd(f[i],f[i+1])=1\)

    证明

    \(gcd(f[i],f[i+1])\)
    \(=gcd(f[i+1]-f[i],f[i])\)
    \(=gcd(f[i-1],f[i])\)
    \(=....\)
    \(=gcd(f[1],f[2])=1)\)

  2. \(f[m+n]=f[m−1]f[n]+f[m]f[n+1]f[m+n]=f[m−1]f[n]+f[m]f[n+1]\)

  3. \(gcd(f[n+m],f[n])=gcd(f[n],f[m])gcd(f[n+m],f[n])=gcd(f[n],f[m])\)
    由上面式子得到
    \(gcd(f[n+m]=f[m−1]f[n]+f[m]f[n+1],f[n])gcd(f[n+m]=f[m−1]f[n]+f[m]f[n+1],f[n])\)
    \(=gcd(f[n+1]f[m],f[n])=gcd(f[n+1]f[m],f[n])\)
    \(=gcd(f[n+1],f[n])∗gcd(f[m],f[n])=gcd(f[n+1],f[n])∗gcd(f[m],f[n])\)
    \(=1∗gcd(f[m],f[n])=1∗gcd(f[m],f[n])\)
    \(=gcd(f[m],f[n])\)

  4. \(gcd(f[n],f[n+m])=f[gcd(n,n+m)]gcd(f[n],f[n+m])=f[gcd(n,n+m)]\)
    证明
    \(gcd(f[n],f[n+m])gcd(f[n],f[n+m])\)
    \(=gcd(f[n],f[n+m]%f[m])=gcd(f[n],f[n+m]%f[m])\)
    \(=gcd(f[n],f[m])=gcd(f[n],f[m])\)
    \(=gcd(f[n],f[(n+m)%n])=gcd(f[n],f[(n+m)%n])\)
    这是辗转相除的形式
    所以,最后有
    \(gcd(f[n],f[n+m])gcd(f[n],f[n+m])\)
    \(=gcd(f[0],f[gcd(n,n+m)])=gcd(f[0],f[gcd(n,n+m)])\)
    \(=f[gcd(n,n+m)]\)

图论基础

(一些现在知道但不太清楚(?)or确定的

简单路径:simple path,是每条边只经过了一次的路径。
简单回路:图的定点序列中,除了起点和终点相同外,其余顶点不重复的回路。
图连通:如果无向图 中任意两个节点连通,称其为是连通的。
强连通:有向图 强连通是指, 中任意两个节点连通。
弱连通:有向图 弱连通是指, 中的所有边替换为无向边后, 为连通图。
点连通度:一张图的点连通度的大小等于最小点割集的大小。
边连通度:一张图的边连通度的大小等于最小边割集的大小。
点割集:设图\(G=<V,E>\),若存在 \(V'\subset V\)且\(V'\not=\oslash\),使得\(p(G-V')>p(G)\),而对于任意的\(V"\subset V'\),均有\(p(G-V')=p(G)\),则称 \(V'\)是\(G\)的点割集。特别地,若\(V'\)是\(G\)的点割集,且\(V'\)是单元集,即\(V'=\{v\}\),则称\(v\)为 割点

(\(p(G)\)表示图\(G\)的连通分支(连通块)的个数)

边割集:设图\(G=<V,E>\),\(E'\subset E\)且\(E'\not=\oslash\),使得\(ps(G-E')>p(G)\),而对于任意的\(E''\subset E'\),均有\(p(G-E'')=p(G)\),则称\(E'\) 是\(G\)的边割集(或简称为割集)。特别地,若\(E'\)是\(G\)的边割集,且\(E'\)是单元集,即\(E'=\{e\}\),则称\(e\)为桥。

( \(p(G)\)表示图 G 的连通分支(连通块)的个数)

子图:选取一个节点的子集和边的子集构成的图。

生成子图:选取的子图的节点和原图一样。
导出子图:选取一个节点的子集,再选取这些节点相关联的边的集合构成的图。
边导出子图:选取一个边的子集,再选取这些边相关联的节点的集合,构成的图。
连通子图:(一个无向图的)连通的子图。
连通分量:(一个无向图的)极大的连通子图。
【注】:极大是指添加任何节点或者边后都不再满足。

树基础

有根二叉树(rooted binary tree) :每个结点最多只有两个儿子(子结点)的有根树称为二叉树。常常对两个子结点的顺序加以区分,分别称之为左子结点和右子结点。
大多数情况下, 二叉树 一词均指有根二叉树。
完整二叉树(full/proper binary tree) :每个结点的子结点数量均为 0 或者 2 的二叉树。换言之,每个结点或者是树叶,或者左右子树均非空。
完全二叉树(complete binary tree) :只有最下面两层结点的度数可以小于 2,且最下面一层的结点都集中在该层最左边的连续位置上。
完美二叉树(perfect binary tree) :所有叶结点的深度均相同的二叉树称为完美二叉树。

先序遍历:先访问根,再访问子节点。
中序遍历:先访问左子树,再访问根,再访问右子树。
后序遍历:先访问子节点,再访问根。
已知中序遍历和另外一个可以求第三个。

树的重心

定义:以树的重心为根时,所有的子树(不算整个树自身)的大小都不超过整个树大小的一半。
找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心。
删去重心后,生成的多棵树尽可能平衡。

性质:

  1. 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么他们的距离和一样。
  2. 把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两个树的重心的路径上。
  3. 在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离
  4. 一棵树最多有两个重心,且相邻。

求法:
树的重心可以通过简单的两次搜索求出。

  1. 第一遍搜索求出以每个节点为根的子树中结点数量\(sz_u\)
  2. 第二遍搜索找出使\(max_{v\in son(u)}\{n-sz_u,sz_v\}\)最小的节点
int ans,siz=inf;
void dfs(int u,int fa){
    sz[u]=1;
    int res=0;
    for(int i=head[u],v;i;i=e[i].nxt){
        if((v=e[i].v)==fa) continue;
        dfs(v,u),sz[u]+=sz[v];
        res=max(res,son[v]);
    }
    res=max(res,n-sz[u]);
    if(res<siz) ans=u,siz=res;
}

淀粉质点分治

学长:

淀粉质一般用于处理树上路径问题
淀粉质的本质是对整棵树进行重心分治
然后乱搞

选择重心作为当前分治点,将整棵树分开,各个子树互不影响,再递归到子树中进行分治,所有分治点构成一棵树
why重心?
考虑分治时的问题规模,只有选择重心时,才能使得子问题的规模尽量小,重心的每个子树大小都不会超过 n/2 , 即每次递归问题规模至少减一半,只用递归log层

inline void findrt(int x,int fa){//找重心
    siz[x]=1; bst[x]=0;
    for(rg int i=hd[x];i!=-1;i=e[i].nt){
        int v=e[i].v; if(v == fa || vis[v]) continue;
        findrt(v,x); siz[x]+=siz[v];
        bst[x]=max(bst[x],siz[v]);
    }
    bst[x]=max(bst[x],S-siz[x]);
    if(bst[x] < bst[rt] || rt == 0) rt=x;
}

假设你已经找出了重心,该怎么做 ?

暴力啊

考虑统计所有经过当前重心且在当前分治范围内的路径\((u,v)\)都可以看作\((u,S)+(S,v)\)
题目要求统计长为k的路径,我们可以硬枚举两条边,统计进一个全局数组中,然后继续分治,这样做的话对于一条路径,只会在其经过的最高分治点被统计,O(n^2)

好像统计了一些不该统计的东西 ?

这样会统计到来自于同一子树的两条路径,并不合法,
考虑在每次分治一棵子树前,先减掉这棵树内不合法的情况,同样O(n^2)

照着学长代码打的模板

#include<bits/stdc++.h>
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;

const int N=1e4+5;
int k[10000005];
int n,m,dis[N],vis[N],rt,sz[N],bst[N],S,tt,q[N];
template <class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int tot,head[N];
struct edge{int v,w,nxt;}e[N<<1];
inline void add(int u,int v,int w){
    e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}

inline void findrt(int u,int fa){
    sz[u]=1,bst[u]=0;
    for(int i=head[u],v;i;i=e[i].nxt){
        if(vis[v=e[i].v]||v==fa) continue;
        findrt(v,u),sz[u]+=sz[v];
        bst[u]=Max(bst[u],sz[v]);
    }
    bst[u]=Max(bst[u],S-sz[u]);
    if(bst[u]<bst[rt]||!rt) rt=u;
}
inline void getdis(int u,int fa){
    q[++tt]=dis[u];
    for(int i=head[u],v;i;i=e[i].nxt){
        if(vis[v=e[i].v]||v==fa) continue;
        dis[v]=dis[u]+e[i].w,getdis(v,u);
    }
}

inline void deal(int u,int la,int fl){
    dis[u]=la,tt=0,getdis(u,0);
    for(int i=1;i<=tt;++i)
        for(int j=1;j<=tt;++j)
            k[q[i]+q[j]]+=fl;
}

inline void getans(int u){
    vis[u]=1,deal(u,0,1);
    for(int i=head[u],v;i;i=e[i].nxt){
        if(vis[v=e[i].v]) continue;
        deal(v,e[i].w,-1);
        rt=0,S=sz[v],findrt(v,u);
        getans(rt);
    }
}

int main(){
    freopen("in.txt","r",stdin);
    rd(n),rd(m);
    for(int i=1,u,v,w;i<n;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);
    S=n,findrt(1,0);
    getans(rt);
    for(int i=1,x;i<=m;++i){
        rd(x);
        if(k[x]>0) puts("AYE");
        else puts("NAY");
    }
    return 0;
}

kruskal

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5,M=5e5+5,inf=0x3f3f3f3f;
int n,m;
ll ans=0;
template<class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}
struct edge{
    int u,v,w;
    bool operator<(const edge&X)const{return w<X.w;}
}e[M];
int f[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void kruskal(){
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1,u,v;i<=m;++i)
        if(find(u=e[i].u)!=find(v=e[i].v)) f[f[u]]=f[v],ans+=e[i].w;
}

int main(){
    rd(n),rd(m);
    for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),e[i]=(edge){u,v,w};
    sort(e+1,e+m+1);
    kruskal();
    printf("%lld",ans);
    return 0;
}

prim

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int>pii;
priority_queue<pii,vector<pii>,greater<pii> >q;
const int N=2e5+5,M=5e5+5,inf=0x3f3f3f3f;
int n,m;
ll ans=0;
template<class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

int head[N],tot=0;
struct edge{int v,w,nxt;}e[M<<1];
void add(int u,int v,int w){
    e[++tot]=(edge){v,w,head[u]},head[u]=tot;
}

int dis[N],vis[N];
void prim(){
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    q.push(make_pair(dis[1]=0,1));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        ans+=dis[u],vis[u]=1;
        for(int i=head[u],v,w;i;i=e[i].nxt)
        if(!vis[v=e[i].v]&&dis[v]>(w=e[i].w))
        dis[v]=w,q.push(make_pair(dis[v],v));
    }
}

int main(){
    rd(n),rd(m);
    for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);
    prim();
    printf("%lld",ans);
    return 0;
}
上一篇:正则表达式(java)规则大全


下一篇:正则表达式