牛客编程巅峰赛S1第3场 - 黄金&钻石

A-找卧底
链接：https://ac.nowcoder.com/acm/contest/6383/A
来源：牛客网

牛牛今天和大家玩了一个新游戏，除了牛牛以外还有n个人参加游戏，现在这n个人中的每个人从[1,n]中选择一个数字，保证选出的数字均不重复。牛牛作为第n+1个人，充当卧底的角色，要求卧底从1到n中选择一个数字，现在将n+1个数字重新打乱顺序，请找出卧底选择的数字是多少。

C++
用x数组标记是否以及出现过，再次出现就直接输出结果

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
     int x[100005];
    int search(int n, vector<int>& a) {
        // write code here
        memset(x,0,sizeof(x));
        for(int i=0;i<a.size();i++)
        {
            if(x[a[i]])return a[i];
            x[a[i]]=1;
        }
    }
};

B-父子情深
链接：https://ac.nowcoder.com/acm/contest/6383/B
来源：牛客网


C++:
题意 树上修改，修改当前点和他的子树，然后输出结果。

就模拟这个过程，从当前节点遍历他的所有节点然后累加值。

class Solution
{
public:
    long a[100050];
    vector<int>G[100050];
    void dfs(int x,int f)
    {
        for (int i = 0; i < G[x].size(); ++i)
        {
            int y=G[x][i];
            if (y!=f)
            {
                a[y] += a[x];
                dfs(y,x);
            }
        }
    }
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query)
    {
        int x,y;
        for (int i = 0; i < n-1; ++i)
        {
            x = Edge[i].x;
            y = Edge[i].y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        for (int i = 0; i < q; ++i)
            a[Query[i].x] += Query[i].y;
        dfs(1,-1);
        vector<long>Ans;
        Ans.clear();
        for (int i = 1; i <= n; ++i)
            Ans.push_back(a[i]);
        return Ans;
    }
};

C-旋转跳跃
https://ac.nowcoder.com/acm/contest/6383/C


题意：
就是他给定的m对（x，y）的值可以互相互换，求字典序最小的排序。
题解:
把可以互换的值利用并查集连接起来，这样他们可以互相转换，把每个节点存在他们的祖宗里，然后从小到大输出结果。
C++

class Solution
{
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型
     * @param m int整型
     * @param perm int整型vector
     * @param Pair Point类vector
     * @return int整型vector
     */
    int f[100005];
    int find(int x)
    {
        if(f[x]==x)
            return x;
        else
        {
            f[x]=find(f[x]);
            return f[x];
        }
    }
    void merge(int x,int y)
    {
        int t1=find(x);
        int t2=find(y);
        if(t2!=t1)
        {
            f[t2]=t1;
        }
    }
    int num[100005];
        vector<int>ans;
        vector<int>vet[100005];
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair)
    {
        // write code here
        for(int i=1; i<=n; i++)
        {
            f[i]=i;
        }
        for(int i=0; i<m; i++)
        {
            merge(Pair[i].x,Pair[i].y);
        }

        for(int i=1; i<=n; i++)
        {
            int ff=find(i);
            vet[ff].push_back(perm[i-1]);
        }
        for(int i=1; i<=n; i++)
        {
            sort(vet[i].begin(),vet[i].end());
        }
        for(int i=1; i<=n; i++)
        {
            int ff=find(i);
            ans.push_back(vet[ff][num[ff]++]);
        }
        return ans;
    }
};