数据结构补充

2018/2/13,头有点晕emmmm…所以学一波数据结构,暂缓数论剩下的高深理论…

注意,这波数据结构是为了补充以前所不足的而撰写的,并无重头再来的意思.

并查集

要领

以前使用并查集多用于Kruskal的优化,现在要拓宽一下了.

并查集是不可能分割的,即只能合并,不可分割.

在牛客上听大佬讲课貌似存在可分割并查集,带权并查集.

现在拓宽下,并查集常用于判断加入一个点后是否会在原图上形成环.

或者判断有几个连通分量(通常是无向图),然后问你这些节点全部关联起来至少需要添加几条边.

实现前奏

首先是逻辑,并查集实现规则是一个点一个点入图时进行合并,即join,然后在合并时进行find,查找根节点是否相同,不同则将浅的树合并到深的树上,判断深浅通过每次合并时对rank进行操作,然后在一个优化是路径压缩,即如果a节点的最高根节点是c,则直接将a记录为c即可.

以上实现的前提是我们只需要逻辑上正确即可.

以题为马

HDU 1232
判断有多少个连通块,然后答案就是ans-1

#include<bits/stdc++.h>

using namespace std;

struct DisjointSet{
    vector<int> father,rank;
    int Num;
    DisjointSet(int n):father(n),rank(n),Num(n){
        for(int i=1;i<n;++i){
            father[i]=i;
        }
    }

    int find(int v){
        return father[v]=father[v]==v?v:find(father[v]);
    }

    void merge(int x,int y){
        int a=find(x),b=find(y);
        if(rank[a]<rank[b]){
            father[a]=b;
        }else{
            father[b]=a;
            if(rank[a]==rank[b]){
                ++rank[a];
            }
        }
    }

    int getCnum(){
        int ans=0;
        for(int i=1;i<Num;++i){
            if(father[i]==i) ans++;
        }
        return ans-1;
    }
};

int main(){
    int m,n;

    while(scanf("%d",&n) && n){
        DisjointSet ds(n+1);
        int s,t;
        scanf("%d",&m);
        for(int i=0;i<m;++i){
            scanf("%d %d",&s,&t);
            ds.merge(s,t);
        }
        printf("%d\n",ds.getCnum());
    }
    return 0;
}

单调栈

线段树区间更新和查询

POJ 3468

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000*4;
typedef long long LL;
int N,Q;
LL lazy[maxn];
LL sum[maxn];
LL tree[maxn];
LL a[maxn];

void build(int p,int l,int r){
    if(l==r){tree[p]=a[l];return;}
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p]=tree[p<<1]+tree[p<<1|1];
}

void PushDown(int p,int m){
    if(lazy[p]){
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        sum[p<<1]+=(m-(m>>1))*lazy[p];
        sum[p<<1|1]+=(m>>1)*lazy[p];
        lazy[p]=0;
    }
}

void update(int p,int l,int r,int c,int L,int R){
    if(L<=l && r<=R){
        lazy[p]+=c;
        sum[p]+=(LL)(r-l+1)*c;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,c,L,R);
    if(R>mid) update(p<<1|1,mid+1,r,c,L,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

LL Query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return sum[p];
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=Query(p<<1,l,mid,L,R);
    if(R>mid) ret+=Query(p<<1|1,mid+1,r,L,R);
    return ret;
}

LL find(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return tree[p];
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=find(p<<1,l,mid,L,R);
    if(R>mid) ret+=find(p<<1|1,mid+1,r,L,R);
    return ret;
}

int main(){
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;++i) scanf("%lld",&a[i]);
    build(1,1,N);
    char op;
    int l,r,c;
    while(Q--){
        cin>>op;
        if(op=='Q'){
            scanf("%d%d",&l,&r);
            printf("%lld\n",Query(1,1,N,l,r)+find(1,1,N,l,r));
        }else if(op=='C'){
            scanf("%d%d%d",&l,&r,&c);
            update(1,1,N,c,l,r);
        }
    }
    return 0;
}

ccf 2017前四题

第一题官网挂掉了.第五题感觉可以用最大流搞搞.
类型:
第一题:贪心
第二题:链表(我用STL里的list实现的)
第三题:中等模拟?
第四题:并查集+最小堆优化Kruskal
题目连接: **要登录和会员 ** http://118.190.20.162/home.page

github: :earth_africa:CCF 2017-3 前四题

第一题:

#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int N,K;
    while(~scanf("%d%d",&N,&K)){
        int ans=0,d,n=0;
        for(int i=0;i<N;++i){
            scanf("%d",&d);
            n+=d;
            if(n>=K){
                n=0;
                ans++;
            }
        }
        if(n)ans++;
        printf("%d\n",ans);
    }
    return 0;
}

第二题:

#include<bits/stdc++.h>
using namespace std;

int N,M;
int I,J;

list<int> li;

int main(){
    while(~scanf("%d%d",&N,&M)){
        li.clear();
        for(int i=1;i<=N;++i){
            li.push_back(i);
        }
        for(int i=1;i<=M;++i){
            scanf("%d%d",&I,&J);
            if(J==0)continue;
            list<int>::iterator it,it2;
            for(it=li.begin();*it!=I;it++){}
            it2=it;
            int flag=J>0?1:-1;
            J=abs(J)+(flag>0?1:0);
            while(J){
                J--;
                flag>0?it++:it--;
            }
            li.insert(it,I);
            li.erase(it2);
        }
        list<int>::iterator it;
        it=li.begin();
        printf("%d",*it);
        it++;
        for(;it!=li.end();it++){
            printf(" %d",*it);
        }
        printf("\n");
    }
    return 0;
}

第三题:

#include<bits/stdc++.h>

#define BUF_SS 101

using namespace std;

char buf[101];
int pre=-1;

int check_hl(int st){
    char hr[100];
    string tip;
    int ind=st+1,cs=0,hs=0;
    while(buf[ind]!=']'){
        if(buf[ind]=='_'){
            tip+="<em>";
            ind++;
            while(buf[ind]!='_'){
                tip+=buf[ind];
                ind++;
            }
            tip+="</em>";
            ind++;
        }else{
            tip+=buf[ind];
            ind++;
        }
    }
    ind+=2;
    while(buf[ind]!=')'){
        hr[hs++]=buf[ind];
        ind++;
    }
    hr[hs]='\0';
    printf("<a href=\"%s\">",hr);
    cout<<tip<<"</a>";
    return ind-st;
}

int check_em(int st){
    int ind=st+1;
    printf("<em>");
    while(buf[ind]!='_'){
        if(buf[ind]=='['){
            int ed=check_hl(ind);
            ind+=(ed+1);
        }else{
            putchar(buf[ind]);
            ind++;
        }
    }
    printf("</em>");
    return ind-st;
}

void check_h(int sz){
    int n,r=0;
    char sts[20],ste[20];
    while(buf[r]=='#'){
        r++;
    }
    int s=r,e=sz-1;
    sprintf(sts,"<h%d>",r);
    sprintf(ste,"</h%d>",r);
    for(;buf[s]==' ';s++){}
    printf("%s",sts);
    for(int i=s;buf[i]!='\n';++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
    printf("%s\n",ste);
}

void check_u(int sz){
    if(pre!=2)printf("<ul>\n");
    int s=1,e=sz-1;
    for(;buf[s]==' ';s++){}
    printf("<li>");
    for(int i=s;buf[i]!='\n';++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
    printf("</li>\n");
}

void check_p(int sz){
    if(pre!=3)printf("<p>");
    if(pre==3)putchar('\n');
    for(int i=0;buf[i]!='\n' && i<sz;++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    while(fgets(buf,BUF_SS,stdin)){
        if(buf[0]=='\n'){
            if(pre==3){
                printf("</p>\n");
                pre=0;continue;
            }else if(pre==2){
                printf("</ul>\n");
                pre=0;continue;
            }
            continue;
        }
        int sz=strlen(buf);
        if(buf[0]=='#') check_h(sz),pre=1;
        else if(buf[0]=='*') check_u(sz),pre=2;
        else check_p(sz),pre=3;
    }
    if(pre==3)printf("</p>\n");
    if(pre==2)printf("</ul>\n");
    return 0;
}

写题的时候写了一组测试数据:
In[1]:

# Heading

## Sub-heading

Paragraphs are separated
by a blank line.

Text attributes _italic_.

Bullet list:

*      apples
* oranges
* pears

A _[NLJ6link616lins1](http://example.com)_.

[NLJ6_link_616_lins_1](http://example.com)

out[1]:

<h1>Heading</h1>
<h2>Sub-heading</h2>
<p>Paragraphs are separated
by a blank line.</p>
<p>Text attributes <em>italic</em>.</p>
<p>Bullet list:</p>
<ul>
<li>apples</li>
<li>oranges</li>
<li>pears</li>
</ul>
<p>A <em><a href="http://example.com">NLJ6link616lins1</a></em>.</p>
<p><a href="http://example.com">NLJ6<em>link</em>616<em>lins</em>1</a></p>

第四题:

#include<bits/stdc++.h>
using namespace std;
const int MAX_M=200000+10;
const int maxn=200000+10;
int N,M;
int A,B,C;

struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,from,to;
    bool operator<(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};

struct Kruskal{
    int n,m;///点数和边数
    vector<Edge> edges;///边表
    vector<int> G[maxn];///每个节点出发的边编号
    priority_queue<HeapNode> Q;

    ///并查集
    int fa[maxn];///父亲
    int ra[maxn];///高度
    ///init:初始化(点数)
    ///find_Root:查找树的根
    ///unite:合并x和y所属集合
    ///same:判断x和y是否是同一个集合
    void init(int n){
        this->n=n;
        for(int i=0;i<n;++i){
            fa[i]=i;
            ra[i]=0;
            G[i].clear();
        }
        edges.clear();
    }
    int find_Root(int x){
        if(fa[x]==x){
            return x;
        }else{
            return fa[x]=find_Root(fa[x]);
        }
    }
    void unite(int x,int y){
        x=find_Root(x);
        y=find_Root(y);
        if(x==y) return;

        if(ra[x]<ra[y]){
            fa[x]=y;
        }else{
            fa[y]=x;
        }
    }
    bool same(int x,int y){
        return find_Root(x)==find_Root(y);
    }

    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size()-1;
        G[from].push_back(m-1);
        Q.push((HeapNode){dist,from,to});
    }

    int kruskal(){
        HeapNode h;
        while(!Q.empty()){
            if(find_Root(N)==find_Root(1))break;
            h=Q.top();Q.pop();
            if(find_Root(h.from)==find_Root(h.to))continue;
            unite(h.from,h.to);
        }
        printf("%d\n",h. d);
    }
}K;

int main(){
    while(~scanf("%d%d",&N,&M)){
        K.init(N);
        for(int i=0;i<M;++i){
            scanf("%d%d%d",&A,&B,&C);
            K.AddEdge(A,B,C);
        }
        K.kruskal();
    }
    return 0;
}

POJ 3723

【类型】

并查集优化kruskal

【Tip】

并查集使得可以判断任意两点是否可归溯于同一点,藉此来判断若链接两点是否会形成一个环.

这道题的输入是两个人以及两个人之间的亲密关系,征募某个人的花费为10000-(已征募人中亲密关系和自己的最大值).

这里我们在每征募某个人a时,若使用了a,b的关系,就连一条a,b的边。

如果这个图中存在圈,则一定会出现矛盾(谁是第一个被征募的?).

所以这个图一定是森林.

把人看做顶点.关系看做边,则这个问题就可以转化为求解无向图中的最大权森林问题(即亲密度之和最大),最大权森林问题可以通过把所有边权取反来求最小生成树.

【Code】

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int MAX_N=60000;
struct edge{
    int u,v,cost;
};

bool comp(const edge& e1,const edge& e2){
    return e1.cost<e2.cost;
}

edge es[MAX_N];
int V,E;//顶点数和边数

//并查集
int par[MAX_N];//父亲
int rank[MAX_N];//树的高度

void init_union_find(int n){
    for(int i=0;i<n;++i){
        par[i]=i;
        rank[i]=0;
    }
}

//查询树的根
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

//合并x和y所属集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;

    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

//判断x和y是否属于同一个集合
bool same(int x,int y){
    return find(x)==find(y);
}

int kruskal(){
    sort(es,es+E,comp);
    int res=0;
    init_union_find(V);
    for(int i=0;i<E;++i){
        edge e=es[i];
        if(!same(e.u,e.v)){
            unite(e.u,e.v);
            res+=e.cost;
        }
    }
    return res;
}

int main(){
    int N;
    scanf(“%d”,&N);
    while(N–){
        int B,G,R;
        scanf(“%d%d%d”,&G,&B,&R);
        V=G+B;
        E=R;
        for(int i=0;i<R;++i){
            int a,b,c;
            scanf(“%d%d%d”,&a,&b,&c);
            es[i]=(edge){a,G+b,-c};
        }
        printf(“%d\n”,10000*(V)+kruskal());
    }

    return 0;
}

POJ 1182

【类型】

并查集

【Code】

#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=150000+10;
int N,K;
int T[MAX_N],X[MAX_N],Y[MAX_N];

//并查集
int par[MAX_N];//父亲
int rank[MAX_N];//树的高度

void init(int n){
    for(int i=0;i<n;++i){
        par[i]=i;
        rank[i]=0;
    }
}

//查询树的根
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

//合并x和y所属集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;

    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
}

//判断x和y是否属于同一个集合
bool same(int x,int y){
    return find(x)==find(y);
}

void solve(){
    //初始化并查集
    //元素X,X+N,X+2N分别代表X-A,X-B,X-C
    init(N*3);
    int ans=0;
    for(int i=0;i<K;++i){
        int t=T[i];
        int x=X[i]-1,y=Y[i]-1;//将x,y转换为从下标为0开始编号的号码

        if(x<0||x>=N||y<0||y>=N){//不满足条件2
            ans++;
            continue;
        }

        if(t==1){
            if(same(x,y+N)||same(x,y+2*N)){
                ans++;
            }else{
                unite(x,y);
                unite(x+N,y+N);
                unite(x+2*N,y+2*N);
            }
        }else{
            if(same(x,y) || same(x,y+2*N)){
                ans++;
            }else{
                unite(x,y+N);
                unite(x+N,y+2*N);
                unite(x+2*N,y);
            }
        }
    }
    printf(“%d\n”,ans);
}

int main(){
    scanf(“%d%d”,&N,&K);
    for(int i=0;i<K;++i){
        scanf(“%d%d%d”,&T[i],&X[i],&Y[i]);
    }
    solve();
    return 0;
}