数据结构测试1 on 2019.9.24

末蓝、 2023-06-04 08:53 12阅读 0赞

**T1 union**

**![1596060-20191001002033638-1646776840.png][]**

**一开始我被这个题目带进去了，以为真的是并查集，但实际上此题与并查集毫无半毛钱关系。**

**其实我们可以先离线建好所有的图，然后把建边的时间作为他们的边权。因为两个点什么时候联通取决于它们路径上的点最晚的链接时间，也就是最大边权。而题目明摆了是一棵树，所有考虑树剖维护边权和查询最大值。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int nxt,to,val;
    }edge[maxn*3];
    int head[maxn],cnt;
    int n,m,x,y;
    int w[maxn],dep[maxn],fa[maxn],size[maxn],son[maxn];
    void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    void dfs1(int x,int f){
        size[x]=1;
        fa[x]=f;
        dep[x]=dep[f]+1;
        int maxson=-1;
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[x]) continue;
            w[v]=edge[i].val;
            dfs1(v,x);
            size[x]+=size[v];
            if(size[v]>maxson){
                maxson=size[v];
                son[x]=v;
            }
        }
    }
    int top[maxn],id[maxn],in;
    int val[maxn];
    void dfs2(int x,int topf){
        top[x]=topf;
        id[x]=++in;
        val[id[x]]=w[x];
        if(!son[x]) return;
        dfs2(son[x],topf);
        for(int i=head[x];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[x]||v==son[x]) continue;
            dfs2(v,v);
        }
    }
    struct node2{
        int l,r,mx;
    }tree[maxn*4];
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r;
        if(l==r){
            tree[now].mx=val[l];
            return;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);
    }
    int query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].mx;
        int ans=0;
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) ans=max(ans,query(now<<1,l,r));
        if(r>mid) ans=max(ans,query(now<<1|1,l,r));
        return ans;
    }
    int link(int x,int y){
        if(x==y) return 0;
        int ans=0;
        while(top[x]!=top[y]){
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans=max(ans,query(1,id[top[x]],id[x]));
            x=fa[top[x]];
        }
        if(dep[x]<dep[y]) swap(x,y);
        ans=max(ans,query(1,id[y]+1,id[x]));
        return ans;
    }
    int main(){
        freopen("union.in","r",stdin);
        freopen("union.out","w",stdout); 
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            add(x,y,i);add(y,x,i);
        }    
        dfs1(1,0);
        dfs2(1,1);
        build(1,1,n);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            printf("%d\n",link(x,y));
        }
        return 0;
    }

**T2 lcs**

**![1596060-20191001003030693-347874233.png][]**

**题目非常显然，但是1e5的数据范围肯定没法像原来那样n方的去dp，于是我们必须将它用某种数据结构维护来优化为log的复杂度，显然想到树状数组。其实树状数组求lcs简单好写，跑的还非常快。**

**树状数组都知道可以求lis，但怎么把它转化为求lcs的问题呢？肯定是离散化啊！先将第一个序列离散为一个单调递增的序列，然后根据第一个序列上每一位的哈希值又离散化第二个序列，这个时候我们发现，由于第一个序列已经是有序的了，我们将第二个序列离散化后最长单调递增的序列那么肯定就是lcs了。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//离散化，转化为树状数组求lis的问题 
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+7;
    int dp[maxn];
    int n;
    int a[maxn];
    int c[maxn];
    int b[maxn];
    int lis[maxn];
    int lis1[maxn];
    int lowbit(int x){
        return x&(-x);
    }
    void modify(int x,int v){
        while(x<=n){
            c[x]=max(c[x],v);
            x+=lowbit(x);
        }
    }
    int query(int x){
        int ans=0;
        while(x){
            ans=max(ans,c[x]);
            x-=lowbit(x);
        }
        return ans;
    }
    int ans;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            lis[a[i]]=i;//映射，离散化 
        } 
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            lis1[i]=lis[b[i]];
        } 
        for(int i=1;i<=n;i++){
            dp[i]=query(lis1[i])+1;
            modify(lis1[i],dp[i]);
        }
        for(int i=1;i<=n;i++) ans=max(dp[i],ans);
        printf("%d\n",ans);
        return 0;
    }

**T3 files**

**![1596060-20191001003226117-937008742.png][]**

![1596060-20191001003302508-583409513.png][]

**stl+模拟文件操作即可**

转载于:https://www.cnblogs.com/LJB666/p/11614625.html

[1596060-20191001002033638-1646776840.png]: /images/20230601/9308ccd171b94157a40125d144576422.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/5142f2f948e344d2a6733561daecdd41.png
[1596060-20191001003030693-347874233.png]: /images/20230601/1ab74502874e441c8e3def5610c06fa2.png
[1596060-20191001003226117-937008742.png]: /images/20230601/e520dc66df9f47acb15117927fc2ff08.png
[1596060-20191001003302508-583409513.png]: /images/20230601/8117c82e805141c38c6fd1b7283e381f.png