[BZOJ 2733][HNOI2012]永无乡

我这题竟然很早就做了……

求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树,那就需要启发式合并了。

继续阅读

[BZOJ 2054]疯狂的馒头

秒,秒啊……

很容易想到线段树,但是在[tex]N=10^6,M=10^7[/tex]的情况下,线段树肯定会TLE。

考虑修改,我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作,然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……

考虑并查集!每个节点修改完后将其父亲改为下一个点,这样的话被修改的地方就可以轻松跳过了。

注意一个细节,第[tex]N[/tex]个馒头被染色后,其父亲会被修改为[tex]N+1[/tex],所以说并查集实际上要开[tex]N+1[/tex]!

代码:

/**************************************************************
    Problem: 2054
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2476 ms
    Memory:39796 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
    if(P[x]==x)
        return x;
    else
        return P[x]=find_set(P[x]);
}
inline void init_set(){
    register int i;
    for(i=1;i<=(n+1);i++)
        P[i]=i;
}
int buf[20];
inline void PutInt(int x){
    register int i,p=0;
    if(x==0){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
int main(){
    int m,p,q;
    register int i,j,l,r,k=0;
    bool OK=false;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    init_set();
    for(i=m;i>=1;i--){
        l=(((i%n)*(p%n))%n+q%n)%n+1;
        r=(((i%n)*(q%n))%n+p%n)%n+1;
        if(l>r)
            swap(l,r);
        for(j=find_set(l);j<=r;j=find_set(j)){
            Color[j]=i;
            P[j]=j+1;
            k++;
            if(k==n){
                OK=true;
                break;
            }
        }
        if(OK)
            break;
    }
    for(i=1;i<=n;i++)
        PutInt(Color[i]);
    return 0;
}

[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线

这两个题是一样的啊……

让路径上最大值最小当然要玩瓶颈路,瓶颈路需要MST,然后Kruskal求MST时最小边不是不可控的!也就是说我们可以控制最小边,从而求出符合要求的生成树,然后凿出瓶颈路。

所以我们可以直接枚举最小边,然后Kruskal求生成树,之后求瓶颈路。至于是否有解,第一遍Kruskal(第一遍求的其实是MST)之后看看是否联通即可。

不过这个题求瓶颈路个人建议用BFS而不是DFS,且不谈BFS效率高还不易炸堆栈段(尽管这个题没有炸堆栈段的隐患),DFS本身细节就很多,容易错。

代码:

/**************************************************************
    Problem: 1050
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3588 ms
    Memory:1172 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
const int maxn=501,maxm=10001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define CUS_REP(i,u,v) for(i=(u);i<(v);i++)
#define REP_G(i,u) for(i=first[u];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
int n;
int S,T;
 
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int G_cnt=0;
inline void Add_Edge(int u,int v,int d){
    G_cnt++;
    next[G_cnt]=first[u];
    first[u]=G_cnt;
    to[G_cnt]=v;
    dist[G_cnt]=d;
}
inline void Clear_Graph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    G_cnt=0;
}
 
// BFS
bitset<maxn> vis;
struct Node{
    int x,maxv,minv;
};
pii BFS(){
    register int a,b,i;
    queue<Node> Q;
    Node tt;
    Q.push((Node){S,-1,0x7fffffff});
    vis[S]=true;
    while(!Q.empty()){
        tt=Q.front();
        Q.pop();
        if(tt.x==T)
            return make_pair(tt.maxv,tt.minv);
        REP_G(i,tt.x){
            if(!vis[to[i]]){
                vis[to[i]]=true;
                Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])});
            }
        }
    }
}
 
// BINGCHA Set
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    CL_ARR(rank,0);
}
 
// MST
struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
vector<Edge> E;
bool OK=false;
pii ans;
void MST(int x){
    register int i,a,b,cnt=0;
    pii que;
    register double jia,yi;
    Clear_Graph();
    init_set();
    CUS_REP(i,x,E.size()){
        if(!is_same(E[i].u,E[i].v)){
            Add_Edge(E[i].u,E[i].v,E[i].d);
            Add_Edge(E[i].v,E[i].u,E[i].d);
            cnt++;
            union_set(E[i].u,E[i].v);
            if(cnt==n-1)
                break;
        }
    }
    if(is_same(S,T)){
        OK=true;
    }else{
        return;
    }
    vis.reset();
    que=BFS();
    a=que.first;
    b=que.second;
    jia=((double)a)/((double)b);
    yi=(double(ans.first))/(double(ans.second));
    if(jia<yi){
        ans.first=a;
        ans.second=b;
    }
}
 
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main(){
    int m;
    register int i,u,v,d;
    n=readint();
    m=readint();
    REP(i,m){
        u=readint();
        v=readint();
        d=readint();
        E.push_back((Edge){u,v,d});
    }
    S=readint();
    T=readint();
    sort(E.begin(),E.end());
    ans.first=0x7fffffff;
    ans.second=1;
    REP(i,m){
        MST(i);
        if(!OK){
            if(!i){
                puts("IMPOSSIBLE");
                return 0;
            }else{
                break;
            }
        }
    }
    d=gcd(ans.first,ans.second);
    ans.first/=d;
    ans.second/=d;
    if(ans.second==1)
        printf("%d\n",ans.first);
    else
        printf("%d/%d\n",ans.first,ans.second);
    return 0;
}

[洛谷 P1967]货车运输

倍增LCA经典题……

这题的做法就是求最大生成树,然后用倍增LCA法求瓶颈路……

注意一下,两点不连通时输出-1(其实这个用并查集判断不就行了……)!!!

代码:

继续阅读

[BZOJ 1370]团伙

哎……做了这题,我才敢说我真的会了点并查集

这是道很经典,很有意思的并查集题目

其实也不难,每个点记录敌人集合然后乱搞即可

代码:

继续阅读

[BZOJ 1015]星球大战

这道题到现在才A……

其实……离线处理并不像我想的那样变态……

需要注意的是,离线处理过程中,在将被删除的点加入时,联通分量数可能增加(其他一个点都连不了)

代码:

继续阅读

[BZOJ 4195]程序自动分析

看起来是道并查集水题……

可i和j最高可达1000000000,直接开个数组放注定会MLE,怎么办?

注意n最高为1000000,所以每组数据中出现的i和j最多会有2000000种,所以我们可以把i和j“映射”为不大于2000000的整数,这样就能避免MLE了!

这种技术,就是离散化

同时注意防卡常!

代码:

继续阅读