[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 3436]小K的农场

差分约束系统的可行性问题啊……

按照要求连边然后SPFA判负环即可。

代码:

/**************************************************************
    Problem: 3436
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9224 ms
    Memory:1488 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
 
int n;
namespace Graph{
    int first[maxn];
    int next[maxm],to[maxm];
    ll dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,ll d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
 
    bool inQueue[maxn];
    ll d[maxn];
    int cnt[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        REP(i,n){
            inQueue[i]=true;
            Q.push(i);
        }
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            GRAPH_REP(i,u){
                if(d[to[i]]>d[u]+dist[i]){
                    d[to[i]]=d[u]+dist[i];
                    if(!inQueue[to[i]]){
                        Q.push(to[i]);
                        inQueue[to[i]]=true;
                        if(++cnt[to[i]]>n)
                            return false;
                    }
                }
            }
        }
        return true;
    }
};
 
int main(){
    int m,opt,a,b,c;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&opt,&a,&b);
        if(opt==1){
            scanf("%d",&c);
            Graph::AddEdge(a,b,-c);
        }else{
            if(opt==2){
                scanf("%d",&c);
                Graph::AddEdge(b,a,c);
            }else{
                Graph::AddEdge(a,b,0);
                Graph::AddEdge(b,a,0);
            }
        }
    }
    if(Graph::SPFA())
        puts("Yes");
    else
        puts("No");
    return 0;
}

[BZOJ 2330]糖果

比较裸一些的差分约束系统题……话说好像第一次写SPFA最长路啊TAT

这个题1,3,5条件直接搞就可以。2,4条件要转化成有等于号的版本。

顺便说一些这题的坑点:

  1. 有一个点是一个十万个点的链。在从源点连的时候,如果正序连就会炸。倒着连就不会T。
  2. 有的点的2,4条件出现了[tex]a=b[/tex]的情况,要特判……
  3. 要开long long!

代码:

/**************************************************************
    Problem: 2330
    User: danihao123
    Language: C++
    Result: Accepted
    Time:356 ms
    Memory:7592 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(i,x) memset(i,x,sizeof(i))
const int maxn=100005,maxm=300005;
 
typedef long long ll;
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,ll d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int n;
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
ll SPFA(){
    register int i,u;
    register ll ans=0;
    queue<int> Q;
    CL_ARR(d,-1);
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        GRAPH_REP(i,u){
            if(d[u]>-1 && d[to[i]]<d[u]+dist[i]){
                d[to[i]]=d[u]+dist[i];
                if(!inQueue[to[i]]){
                    Q.push(to[i]);
                    inQueue[to[i]]=true;
                    if((++cnt[to[i]])>(n+1))
                        return -1;
                }
            }
        }
    }
    REP(i,n){
        ans+=d[i];
    }
    return ans;
}
 
int main(){
    register int i;
    int opt,u,v;
    int k;
    scanf("%d%d",&n,&k);
    REP(i,k){
        scanf("%d%d%d",&opt,&u,&v);
        if(opt==1){
            AddEdge(u,v,0);
            AddEdge(v,u,0);
        }else{
            if(opt==2){
                if(u==v){
                    puts("-1");
                    return 0;
                }
                AddEdge(u,v,1);
            }else{
                if(opt==3){
                    AddEdge(v,u,0);
                }else{
                    if(opt==4){
                        if(u==v){
                            puts("-1");
                        }
                        AddEdge(v,u,1);
                    }else{
                        AddEdge(u,v,0);
                    }
                }
            }
        }
    }
    for(i=n;i>=1;i--){
        AddEdge(0,i,1);
    }
    printf("%lld\n",SPFA());
    return 0;
}


[BZOJ 1013]球型空间产生器

不行不能颓了……线代其实刚起步……

注意每个点到球心的距离相同,距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex],那么我们先可以列出两个方程(假设[tex]n=2[/tex],不过此时事实上可以列三个,但出于方便讨论的目的便只列两个):

[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]

[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]

两方程作差,得:

[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]

整理,得:

[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]

对这种方法加以推广,便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。

代码:

/**************************************************************
    Problem: 1013
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1296 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
    register int i,j,k,r;
    register double f;
    for(i=1;i<=n;i++){
        r=i;
        for(j=i+1;j<=n;j++)
            if(fabs(A[j][i])>fabs(A[r][i]))
                r=j;
        if(r!=i)
            for(j=1;j<=(n+1);j++)
                swap(A[r][j],A[i][j]);
        for(k=i+1;k<=n;k++){
            f=A[k][i]/A[i][i];
            for(j=i;j<=n+1;j++)
                A[k][j]-=f*A[i][j];
        }
    }
    for(i=n;i>=1;i--){
        for(j=i+1;j<=n;j++)
            A[i][n+1]-=A[j][n+1]*A[i][j];
        A[i][n+1]/=A[i][i];
    }
}
int main(){
    register int i,j;
    bool flag=false;
    cin>>n;
    for(i=1;i<=(n+1);i++)
        for(j=1;j<=n;j++)
            cin>>M[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=(n+1);j++)
            A[i][j]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            A[i][j]=2*(M[i+1][j]-M[i][j]);
            A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
        }
    }
    Gause();
    for(i=1;i<=n;i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%.3f",A[i][n+1]);
    }
    putchar('\n');
    return 0;
}

[BZOJ 1477]青蛙的约会

设用时为[tex]t[/tex],则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。

整理变形得[tex](n-m)t+Lk=x-y[/tex]。

明显需要扩欧求解。注意此题有很多细节,可参见下代码:

/**************************************************************
    Problem: 1477
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1288 kb
****************************************************************/
 
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    if(!b)
        return a;
    else
        return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }else{
        exgcd(b,a%b,d,x,y);
        ll t=x;
        x=y;
        y=t-a/b*y;
    }
}
int main(){
    ll a,b,c,t,M,k;
    ll x,y,m,n,L;
    cin>>x>>y>>m>>n>>L;
    a=n-m;
    b=L;
    c=x-y;
    k=gcd(a,b);
    if(c%k!=0){
        cout<<"Impossible"<<endl;
        return 0;
    }
    a/=k;
    b/=k;
    c/=k;
    exgcd(a,b,k,t,M);
    t=(((c*t)%b)+b)%b;
    if(!t)
        t+=b;
    cout<<t<<endl;
    return 0;
}

[BZOJ 3224]普通平衡树

很好,这很interesting。

最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……

还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣!

代码:

/**************************************************************
    Problem: 3224
    User: danihao123
    Language: C++
    Result: Accepted
    Time:376 ms
    Memory:1880 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Node{
    Node *ch[2];
    int v;
    int r;
    int s;
    int cnt;
    Node(){
        v=s=cnt=0;
        r=-1;
        ch[0]=ch[1]=NULL;
    }
    Node(int key,Node *lc,Node *rc){
        v=key;
        r=rand();
        s=1;
        cnt=1;
        ch[0]=lc;
        ch[1]=rc;
    }
    void maintain(){
        s=ch[0]->s+ch[1]->s+cnt;
    }
};
struct Treap{
    Node *null,*root;
    Treap(){
        null=new Node();
        root=null;
    }
    void rotate(Node* &o,int d){
        Node* k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }
    void insert(Node* &o,int x){
        if(o==null){
            o=new Node(x,null,null);
        }else{
            if(o->v==x){
                o->cnt++;
                o->s++;
            }else{
                int d=x>(o->v);
                insert(o->ch[d],x);
                if(((o->ch[d])->r)>(o->r))
                    rotate(o,d^1);
            }
        }
        o->maintain();
    }
    void del(Node* &o,int x){
        if(o->v==x){
            if(o->cnt>1){
                o->cnt--;
                o->s--;
            }else{
                if(o->ch[0]==null){
                    Node *u=o;
                    o=o->ch[1];
                    delete u;
                }else{
                    if(o->ch[1]==null){
                        Node *u=o;
                        o=o->ch[0];
                        delete u;
                    }else{
                        int d=(o->ch[1]->r)>(o->ch[0]->r);
                        rotate(o,d^1);
                        del(o->ch[d^1],x);
                    }
                }
            }
        }else{
            int d=x>(o->v);
            del(o->ch[d],x);
        }
        if(o!=null)
            o->maintain();
    }
    int kth(Node *o,int k){
        if(k<=(o->ch[0]->s)){
            return kth(o->ch[0],k);
        }else{
            k-=o->ch[0]->s;
            if(k<=o->cnt)
                return o->v;
            else
                return kth(o->ch[1],k-(o->cnt));
        }
    }
    int rank(Node *o,int x){
        if(o==null)
            return 0;
        if(x<(o->v)){
            return rank(o->ch[0],x);
        }else{
            if(x==o->v)
                return o->ch[0]->s+1;
            else
                return o->ch[0]->s+o->cnt+rank(o->ch[1],x);
        }
    }
    int pre(int x){
        Node *cur=root;
        int ans=0;
        while(cur!=null){
            if(cur->v<x){
                ans=cur->v;
                cur=cur->ch[1];
            }else{
                cur=cur->ch[0];
            }
        }
        return ans;
    }
    int suc(int x){
        Node *cur=root;
        int ans=0;
        while(cur!=null){
            if(cur->v>x){
                ans=cur->v;
                cur=cur->ch[0];
            }else{
                cur=cur->ch[1];
            }
        }
        return ans;
    }
};
int main(){
    int n;
    int opt,x;
    Treap T;
    scanf("%d",&n);
    srand(20020601);
    while(n--){
        scanf("%d%d",&opt,&x);
        if(opt==1){
            T.insert(T.root,x);
        }else{
            if(opt==2){
                T.del(T.root,x);
            }else{
                if(opt==3){
                    printf("%d\n",T.rank(T.root,x));
                }else{
                    if(opt==4){
                        printf("%d\n",T.kth(T.root,x));
                    }else{
                        if(opt==5){
                            printf("%d\n",T.pre(x));
                        }else{
                            printf("%d\n",T.suc(x));
                        }
                    }
                }
            }
        }
    }
    return 0;
}


[BZOJ 1196]公路修建问题

挺简单的二分答案题……然而到现在才A

思路很明显,直接二分最终答案。那么判定如何做呢?

假设判定谓词为[tex]C(x)[/tex],那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边(当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响)。然后白边加的不够[tex]k[/tex]谓词就是假了。

然后再考虑黑边,接下来的事情就很简单了。

代码:

/**************************************************************
    Problem: 1196
    User: danihao123
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
 
struct Edge{
    int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
    return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
    return x.d2<y.d2;
}
 
int n;
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline 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;
    memset(rank,0,sizeof(rank));
}
 
int k,m;
Edge E[maxm];
inline bool check(int x){
    register int i,first_cnt=0,cnt=0;
    init_set();
    sort(E,E+m,cmp1);
    REP(i,m){
        if(E[i].d1>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                first_cnt++;
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1){
            return true;
        }
    }
    if(first_cnt<k)
        return false;
    sort(E,E+m,cmp2);
    REP(i,m){
        if(E[i].d2>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1)
            return true;
    }
    return false;
}
int main(){
    register int i,L=1,M,R=0;
    scanf("%d%d%d",&n,&k,&m);
    m--;
    REP(i,m){
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
        R=max(R,E[i].d1);
    }
    R++;
    while(L<R){
        M=L+(R-L)/2;
        if(check(M))
            R=M;
        else
            L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

 

[BZOJ 4326]运输计划

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的,有点吃不消,再加上会被卡常,咔嚓掉。

考虑二分答案。我们可以直接二分最终答案,那么如何验证?

假设验证谓词为[tex]C(t)[/tex],表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢?可以考虑树上差分,对于每次计划[tex](u,v)[/tex],我们求出其最近公共祖先[tex]L[/tex],然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一,对[tex]d[L][/tex]则减二。随后将d上标记上推,可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确:二分答案,树上差分验证,同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法,倍增也可。

代码:

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}

[BZOJ 1787]紧急集合

这个题需要一些脑洞。

给出任意三点,如果我们两两求LCA,肯定有两组相同,剩下那一组就是最优集合点了。为啥?画图理解一下吧……

代码:

/**************************************************************
    Problem: 1787
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4068 ms
    Memory:80900 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define TWO_POW(n) (1<<(n))
 
const int maxn=500001,maxm=1000001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int d[maxn];
int dep[maxn];
int anc[maxn][32];
void dfs(int x,int father,int depth,int dis){
    d[x]=dis;
    anc[x][0]=father;
    dep[x]=depth;
    int i;
    GRAPH_REP(i,x){
        if(to[i]!=father)
            dfs(to[i],x,depth+1,dis+dist[i]);
    }
}
 
int n;
inline void InitLCA(){
    register int i,j;
    for(j=1;TWO_POW(j)<n;j++){
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                anc[i][j]=anc[anc[i][j-1]][j-1];
            }
        }
    }
}
 
int QueryLCA(int x,int y){
    register int j,log;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;TWO_POW(log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-TWO_POW(j)>=dep[y])
            x=anc[x][j];
    if(x==y)
        return y;
    for(j=log;j>=0;j--){
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            x=anc[x][j];
            y=anc[y][j];
        }
    }
    return anc[x][0];
}
inline int make_dis(int x,int y){
    return d[x]+d[y]-2*d[QueryLCA(x,y)];
}
 
int main(){
    int u,v,D;
    int x,y,z,QinDing;
    int m;
    register int i,j;
    scanf("%d%d",&n,&m);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        Add_Edge(u,v,1);
        Add_Edge(v,u,1);
    }
    memset(anc,-1,sizeof(anc));
    dfs(1,-1,0,0);
    InitLCA();
    REP(i,m){
        scanf("%d%d%d",&u,&v,&D);
        x=QueryLCA(u,v);
        y=QueryLCA(u,D);
        z=QueryLCA(v,D);
        if(x==y){
            QinDing=z;
        }else{
            if(x==z){
                QinDing=y;
            }else{
                QinDing=x;
            }
        }
        printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D));
    }
    return 0;
}

[BZOJ 1901]Dynamic Rankings

某傻逼的卡评记录

终于A了!

做了4个月了,终于A了!

这个题其实不难。只要用树状数组维护主席树即可。不过请注意,此题的实际数据范围远比10000大!

代码:

/**************************************************************
    Problem: 1901
    User: danihao123
    Language: C++
    Result: Accepted
    Time:540 ms
    Memory:32712 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=120051;
const int maxlogn=31;
const int maxnode=maxn*20;
 
// ChairTree
int sumv[maxnode];
int lc[maxnode],rc[maxnode];
int ct_cnt=0;
int build_tree(int L,int R){
    int ans=++ct_cnt;
    if(R>L){
        int M=L+(R-L)/2;
        lc[ans]=build_tree(L,M);
        rc[ans]=build_tree(M+1,R);
    }
    return ans;
}
int p,v;
int update(int o,int L,int R){
    int ans=++ct_cnt;
    sumv[ans]=sumv[o];
    lc[ans]=lc[o];
    rc[ans]=rc[o];
    if(R>L){
        int M=L+(R-L)/2;
        if(p<=M)
            lc[ans]=update(lc[ans],L,M);
        else
            rc[ans]=update(rc[ans],M+1,R);
    }
    sumv[ans]+=v;
    return ans;
}
int LT_siz,RT_siz;
int LT[maxlogn],RT[maxlogn];
int query(int L,int R,int k){
    if(L==R)
        return L;
    int i;
    int LT_ans=0,RT_ans=0,the_ans,M=L+(R-L)/2;
    for(i=1;i<=LT_siz;i++)
        LT_ans+=sumv[lc[LT[i]]];
    for(i=1;i<=RT_siz;i++)
        RT_ans+=sumv[lc[RT[i]]];
    the_ans=RT_ans-LT_ans;
    if(k<=the_ans){
        for(i=1;i<=LT_siz;i++)
            LT[i]=lc[LT[i]];
        for(i=1;i<=RT_siz;i++)
            RT[i]=lc[RT[i]];
        return query(L,M,k);
    }else{
        for(i=1;i<=LT_siz;i++)
            LT[i]=rc[LT[i]];
        for(i=1;i<=RT_siz;i++)
            RT[i]=rc[RT[i]];
        return query(M+1,R,k-the_ans);
    }
}
 
int rt[maxn];
int siz;
inline int lowbit(int x){
    return x&(-x);
}
int n;
void change(int pos,int value,int delta){
    p=value;
    v=delta;
    while(pos<=n){
        rt[pos]=update(rt[pos],1,siz);
        pos+=lowbit(pos);
    }
}
int get_ans(int l,int r,int k){
    int temp=l-1;
    LT_siz=RT_siz=0;
    while(temp>0){
        LT[++LT_siz]=rt[temp];
        temp-=lowbit(temp);
    }
    while(r>0){
        RT[++RT_siz]=rt[r];
        r-=lowbit(r);
    }
    return query(1,siz,k);
}
int pre[maxn];
int A[maxn],A2[maxn];
int real_siz=0;
void init_CT(){
    register int i,pos;
    sort(A2+1,A2+1+real_siz);
    siz=unique(A2+1,A2+1+real_siz)-A2-1;
    rt[0]=build_tree(1,siz);
    for(i=1;i<=n;i++)
        rt[i]=rt[0];
    for(i=1;i<=n;i++){
        pos=lower_bound(A2+1,A2+1+siz,pre[i])-A2;
        change(i,pos,1);
    }
}
inline int get_lsh(int x){
    return lower_bound(A2+1,A2+1+siz,x)-A2;
}
 
int Query[maxn][4];
int main(){
    int m,u,v,d;
    char buf[3];
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&pre[i]);
        A2[++real_siz]=pre[i];
    }
    for(i=1;i<=m;i++){
        scanf("%s%d%d",buf,&u,&v);
        Query[i][1]=u;
        Query[i][2]=v;
        if(buf[0]=='C'){
            Query[i][0]=1;
            A2[++real_siz]=v;
        }else{
            Query[i][0]=0;
            scanf("%d",&Query[i][3]);
        }
    }
    init_CT();
    for(i=1;i<=m;i++){
        if(Query[i][0]){
            change(Query[i][1],get_lsh(pre[Query[i][1]]),-1);
            pre[Query[i][1]]=Query[i][2];
            change(Query[i][1],get_lsh(Query[i][2]),1);
        }else{
            printf("%d\n",A2[get_ans(Query[i][1],Query[i][2],Query[i][3])]);
        }
    }
    return 0;
}