欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-14 11:21:49
...

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

牛牛今天和大家玩了一个新游戏,除了牛牛以外还有n个人参加游戏,现在这n个人中的每个人从[1,n]中选择一个数字,保证选出的数字均不重复。牛牛作为第n+1个人,充当卧底的角色,要求卧底从1到n中选择一个数字,现在将n+1个数字重新打乱顺序,请找出卧底选择的数字是多少。
牛客编程巅峰赛S1第3场 - 黄金&钻石
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
来源:牛客网
牛客编程巅峰赛S1第3场 - 黄金&钻石
牛客编程巅峰赛S1第3场 - 黄金&钻石
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
牛客编程巅峰赛S1第3场 - 黄金&钻石
牛客编程巅峰赛S1第3场 - 黄金&钻石
题意:
就是他给定的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;
    }
};
相关标签: 2020牛客巅峰赛