【2019.9.17】Za

2024-03-20 20:53:16

yyb Fibonacci的性质

\(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)\)
\(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]\)
\(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])\)
\(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）：所有叶结点的深度均相同的二叉树称为完美二叉树。

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

树的重心

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

性质：

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

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

第一遍搜索求出以每个节点为根的子树中结点数量\(sz_u\)
第二遍搜索找出使\(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;
}

码农公寓