四连测Day1

题目：链接: https://pan.baidu.com/s/163ycV64ioy7uML7AvRDTGw 密码: p86i

T1:

倍增求LCA,minn数组记录最小值

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline long long read()

{

    long long f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return ans*f;

}

long long q,a[],fa[][],minn[][];

struct node{

    long long x;long long y;

    long long nex;

}ss[];

long long head[];

long long cnt=;

void add(long long a,long long b)

{

    ss[cnt].x=a,ss[cnt].y=b;

    ss[cnt].nex=head[a],head[a]=cnt++;

    return;

}

long long deep[];

void dfs(long long f,long long fath)

{

    deep[f]=deep[fath]+;

    minn[f][]=min(a[f],a[fath]);

    fa[f][]=fath;

    for(long long i=;(<<i)<=deep[f];i++) fa[f][i]=fa[fa[f][i-]][i-],minn[f][i]=min(minn[f][i-],minn[fa[f][i-]][i-]);

    for(long long i=head[f];i!=-;i=ss[i].nex)

        if(ss[i].y!=fath) dfs(ss[i].y,f);

}

long long n,m,s;

long long lca(long long u,long long v)

{

    long long sry=min(a[u],a[v]);

//    cout<<sry<<endl;

    if(deep[u]<deep[v]) swap(u,v);

    for(long long i=;i>=;i--)

        if(deep[u]-(<<i)>=deep[v]) sry=min(sry,minn[u][i]),u=fa[u][i];

//        cout<<sry<<" "<<u<<" "<<v<<endl;

    if(u==v) return sry;

    for(long long i=;i>=;i--)

    {

        if(fa[u][i]==fa[v][i]) continue;

        else

        {

            sry=min(sry,minn[u][i]),sry=min(sry,minn[v][i]);

            u=fa[u][i],v=fa[v][i];

        }

    }

//    cout<<fa[u][0]<<endl;

    return min(sry,a[fa[u][]]);

}

int main()

{

    memset(head,-,sizeof(head));

    n=read(),q=read();

    for(long long i=;i<=n;i++) a[i]=read();

    for(long long i=;i<n;i++)

    {

        long long u=read(),v=read();

        add(u,v),add(v,u);

    }

    dfs(,);

    for(long long i=;i<=q;i++)

    {

        long long u=read(),v=read();

        printf("%d\n",lca(u,v));

//        return 0;

    }

}/*

5 5

8 100 502 9 3

2 4

4 1

1 3

1 5

3 5

1 5

2 3

2 1

3 4

*/

T2:

桶排序，因为告诉你a[i]最大为1048575，异或和为a[i]^a[i+1]^……a[j]，拿sort会超时

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

int a[],x[];

int n,s[];

int main()

{

    n=read();int q=read();

    for(int i=;i<=n;i++) s[i]=read();

    for(int i=;i<=n;i++)

    {

        int sum=;

        for(int j=i;j<=n;j++) sum^=s[j],a[sum]++;

    }

    int cnt=;

    for(int i=;i<=;i++)

        while(a[i]!=) x[++cnt]=i,a[i]--;

    for(int i=;i<=q;i++)

    {

        int xx=read();

        printf("%d\n",x[xx]);

    }

}

T3:

先将每一个点想成一个区间，r[i]表示i的祖先节点所在区间的最右号，l同理，f为祖先，j=r[find(j)]+1表示因为j号节点的区间右侧为r[find(j)]，所以可得。

将边权从小到大排序，区间覆盖即可

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

using namespace std;

inline int read()

{

    int f=,ans=;char c;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

int n,m;

int f[],r[],l[];

int find(int x)

{

    if(f[x]==x) return x;

    return f[x]=find(f[x]);

}

struct node{

    int ll,rr,v;

}x[];

bool cmp(node xx,node yy)

{

    return xx.v<yy.v;

}

int ans,sum;

void merge(int x1,int x2)

{

    int t1=find(x1),t2=find(x2);

    f[t2]=t1;

    l[t1]=min(l[t1],l[t2]);

    r[t1]=max(r[t1],r[t2]);

}

int main()

{

    n=read(),m=read();

    for(int i=;i<=n;i++) f[i]=l[i]=r[i]=i;

    for(int i=;i<=m;i++)  x[i].ll=read(),x[i].rr=read(),x[i].v=read();

    sort(x+,x+m+,cmp);

    for(int i=;i<=m;i++)

    {

        int j=r[find(x[i].ll)]+;

        while(j<=x[i].rr)

        {

            ans++;

            sum+=x[i].v;

            merge(x[i].ll,j);

            j=r[find(j)]+;

        }

        if(ans==n-)

        {

            printf("%d\n",sum);

            return ;

        }

    }

    cout<<-;

}

/*

5 4

1 2 1

3 4 2

3 5 3

1 4 1

*/