【题目记录】——2021牛客暑期多校训练营7

桃扇骨 2022-09-04 09:48 100阅读 0赞

### 文章目录 ###

*  F xay loves trees 树+思维
 *  H xay loves count 思维 数学
 *  I xay loves or 思维+数学

题目集地址 [2021牛客暑期多校训练营7][2021_7]  
这次题目集做了H和I题

# F xay loves trees 树+思维 #

题目地址[F xay loves trees][]  
题意：给你两棵树，每棵树都给出了n个点n-1条边，你需要找到一个最大的点集合\{1,2,⋯,n\}，满足

在第一棵树中满足集合中的任意两点之间都满足祖先和子节点的关系。  
在第二棵树中，则一定不存在上述关系。

思路：本题做法比较多，但思路都是先跑一边第二棵树的dfs序  
那么为什么要跑dfs序呢？

dfs序中，若某个点为根节点的话，那么它一定比它的所有子树先跑dfs，那么所有的子树dfs序中的编号都大于它，那么我们可以记录每棵树作为根节点，它的子节点个数为szi

然后，以它这棵树编号i为起点，i+szi 就是它的子节点中编号最大的，而且i→i+szi这段都是连续的，且都是i的子树。  
然后，我们可以用线段树或者一些stl，通过维护dfs序来维护以i为根节点，所有子树的信息。  
跑完之后，我们考虑本题该怎么处理祖先和子节点的关系。  
可以想到，我们肯定是现在通过用dfs跑第一棵树，跑每一条链(一棵树中，每一条树链都满足，祖先和子节点都是有关联的)，然后更新第二棵树的dfs序中的信息判断是否满足答案即可。  
那么本题可以通过线段树维护第二棵树上每个点的最大值信息，通过遍历第一棵树的每一条链，遍历到某个点时，把该点在第二棵树上所有子树的sum也加1，那么，当根节点的sum为1的时候表示第二棵树中不存在某条链中有两个点。  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    
    #define pb push_back
    #define mid ((l + r) >> 1)
    #define lsn (u << 1)
    #define rsn (u << 1 | 1)
    using namespace std;
    typedef vector<int> vi;
    
    const int N = 3e5+6;
    int n;
    vi g1[N],g2[N];
    
    int in[N],out[N], cnt;
    int sum[N << 2],laz[N << 2];//线段树
    
    int stk[N];
    int hh,tt;
    int ans;
    
    void up(int u) { 
        sum[u] = max(sum[lsn],sum[rsn]);
    }
    
    void down(int u,int l,int r) { 
        if(laz[u]) { 
            sum[lsn] += laz[u];
            sum[rsn] += laz[u];
            laz[lsn] += laz[u];
            laz[rsn] += laz[u];
            laz[u] = 0;
        }
    }
    void build(int u = 1,int l = 1,int r = n) { 
        sum[u] = laz[u] = 0;
        if(l == r) { 
            return;
        }
        build(lsn,l,mid);
        build(rsn,mid + 1,r);
    }
    
    void update(int L,int R,int v,int u = 1,int l = 1,int r = n) { 
        if(L > r || l > R) return;
        if(L <= l && R >= r) { 
            sum[u] += v;
            laz[u] += v;
            return;
        }
        down(u,l,r);
        if(L <= mid) update(L,R,v,lsn,l,mid);
        if(R > mid) update(L,R,v,rsn,mid + 1,r);
        up(u);
    }
    
    void dfs1(int u,int fa) { //遍历第二棵树的dfs序
        in[u] = ++ cnt;//记录u点入栈的时刻
        for(auto it : g2[u]) { 
            if(it == fa) continue;
            dfs1(it,u);
        }
        out[u] = cnt;//记录u点出栈时刻
    }
    
    void dfs2(int u,int fa) { 
        int now = -1;
        stk[++ tt] = u;
        // 更新以u为根节点所有子树的信息
        update(in[u],out[u],1);
    
        if(sum[1] == 1) { 
            ans = max(ans, tt - hh + 1);
        }else if(tt - hh + 1 > ans){ 
            now = stk[hh ++];
            update(in[now],out[now],-1);
        }
    
        for(auto it : g1[u]) { 
            if(it == fa) continue;
            dfs2(it,u);
        }
        // 回溯
        if(now != -1) { 
            update(in[now],out[now],1);
            stk[-- hh] = now;
        }
        update(in[u],out[u],-1);
        tt --; // 重要，这样后面的父节点中的儿子之间就一定无关联
    }
    
    void init(int k){ 
        cnt = 0;
        for(int i = 1;i <= k;i ++) g1[i].clear(),g2[i].clear();
    }
    
    void solve(){ 
    
        cin >> n;
        build();
        for(int i = 1;i < n;i ++) { 
            int a,b;
            cin >> a >> b;
            g1[a].pb(b);
            g1[b].pb(a);
        }
        for(int i = 1;i < n;i ++) { 
            int a,b;
            cin >> a >> b;
            g2[a].pb(b);
            g2[b].pb(a);
        }
        dfs1(1,0); // 找到第二棵树的dfs序
        hh = 0,tt = -1;
        ans = 0;
        dfs2(1,0);
        cout << ans << endl;
        init(n);
    }
    int main()
    { 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
        int t;
        cin >> t;
        while(t--)
        { 
            solve();
        }
        return 0;
    }

# H xay loves count 思维 数学 #

题目地址[H xay loves count][]  
题意：给出一组序列，问存在多少对三元组(i,j,k)满足ai×ai=ak.  
思路：就是遍历，我们当时想的有点复杂了，附上逆十字大佬的代码，简单明了，因为只有一个测试用例，只需要一次性将全部i，j遍历一次就行了。

#include<bits/stdc++.h>//附逆十字大佬的代码
    using namespace std;
    const int N=1000005;
    int n,x,a[N];
    int main()
    { 
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&x),++a[x];
        long long ans=0;
        for (int i=1;i<N;i++)
            for (int j=1;j*i<N;j++)
                ans+=1ll*a[i]*a[j]*a[i*j];
        cout<<ans<<endl;
    }

# I xay loves or 思维+数学 #

题目地址[I xay loves or][]  
题意：给出x和s，问有多少个y使得，x|y=s  
思路：如果x不是s的一个子集，即(x&s)!=x那么就无解。  
假设x上有n个1，答案为 2 n 2^n 2n，注意答案可能超int，还有就是x=s时候需要特判，因为y不能为零  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    ll qpow(ll a, ll n){ 
    	ll ans = 1;
    	while(n){ 
    		if(n&1)
    		{ 
    			ans *= a;
    		}
    		a *= a;
    		n >>= 1;
    	}
    	return ans;
    }
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        ll x,s;
        scanf("%lld%lld",&x,&s);
        if((x&s)!=x)
        { 
            printf("0\n");
        }
        else
        { 
            bitset<32> b(x);
            if(x == s)
            { 
                printf("%lld\n",qpow(2,b.count())-1);
            }
            else
            { 
                printf("%lld\n",qpow(2,b.count()));
            }
        }
        return 0;
    }

我在看题解的时候发现有人直接遍历就过了？？？？？

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    
    using namespace std;
    
    int main(){ 
    	int x,s,y=0;
    	cin>>x>>s;
    	for(int i=1;i<=s;i++)
    		if((x|i)==s)
    			y++;
    	cout<<y<<endl;
    	return 0;
    }

[2021_7]: https://ac.nowcoder.com/acm/contest/11258
[F xay loves trees]: https://ac.nowcoder.com/acm/contest/11258/F
[H xay loves count]: https://ac.nowcoder.com/acm/contest/11258/H
[I xay loves or]: https://ac.nowcoder.com/acm/contest/11258/I