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

前面的碎碎念：
题目比较简单，比赛主要还是考验手速和准确率。但是个人不太适应这种函数式编程，而且牛客的函数式编程还不像力扣那样提供在线运行功能，所以也不能进行输出Debug调试。

题解部分：

A-找卧底
要求时间复杂度O(n)，空间复杂度O(1)，乍一看没什么想法。后来仔细读题发现前n个人选的数字是1-n的一个全排列，因此我们把所有数字相加后，减去(1+2+...+n)，就是多出来的那个数字了。
时间复杂度：O(n)。
代码部分：

class Solution {
public:
    /**
     *
     * @param n int整型
     * @param a int整型vector
     * @return int整型
     */
    int search(int n, vector<int>& a) {
        int i,ans;
        long long s=0;
        for(i=0;i<a.size();i++)s+=a[i];
        ans=s-(1+(long long)n)*n/2;
        return ans;
    }
};

B-父子情深
以x为根的子树，其所有结点的DFS序一定是一段连续的区间，因此我们先处理出DFS序，然后对于每个询问，使用差分数组对其子树对应区间进行区间加操作。询问结束后，我们利用差分数组得到DFS序的值，然后把每个DFS序的值再映射回对应结点就行了。
时间复杂度：O(n+q)。
代码部分：

/**
 * struct Point {
 *  int x;
 *  int y;
 * };
 */

class Solution {
public:
    /**
     * 从 1 到 n 每个结点的权值。
     * @param n int整型
     * @param Edge Point类vector (u, v) 集合
     * @param q int整型
     * @param Query Point类vector Point.x 为题中 r, Point.y为题中 v
     * @return long长整型vector
     */
    long S[100005]={0},ans[100005];
    int Left[100005],Right[100005],V[100005],t=0;
    vector<int>R[100005];
    void DFS(int x,int pre)
    {
        int i,j;
        Left[x]=++t,V[t]=x;
        for(i=0;i<R[x].size();i++)
        {
            j=R[x][i];
            if(j!=pre)DFS(j,x);
        }
        Right[x]=t;
    }
    vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {
        vector<long>Ans;
        Point p;
        int i,l,r;
        for(i=0;i<Edge.size();i++)
        {
            p=Edge[i];
            R[p.x].push_back(p.y),R[p.y].push_back(p.x);
        }
        DFS(1,0);
        for(i=0;i<q;i++)
        {
            p=Query[i];
            l=Left[p.x],r=Right[p.x];
            S[l]+=p.y,S[r+1]-=p.y;
        }
        for(i=1;i<=n;i++)S[i]+=S[i-1],ans[V[i]]=S[i];
        for(i=1;i<=n;i++)Ans.push_back(ans[i]);
        return Ans;
    }
};

C-旋转跳跃
对于这m对(x,y)，我们就让x结点与y结点连一条边，其n个结点会形成若干个连通块，连通块内所有结点的值属于同一个集合。因此我们可以利用并查集处理出每个结点对应的集合(连通块)编号，再使用一个vector容器把各个结点的值存入对应的集合。我们对每个集合进行排序，然后贪心的从集合里取数字即可。具体操作为用变量i从n遍历到1，令ans[i]为i号结点属于的集合里的最大值，然后再把此最大值从该集合中删除。
时间复杂度：O(m+nlog(n))。
代码部分：

/**
 * struct Point {
 *  int x;
 *  int y;
 * };
 */

class Solution {
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型
     * @param m int整型
     * @param perm int整型vector
     * @param Pair Point类vector
     * @return int整型vector
     */
    int V[100005],ans[100005];
    int find(int a)
    {
        if(V[a]==a)return a;
        return V[a]=find(V[a]);
    }
    vector<int>R[100005];
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        int i,j,a,b;
        Point p;
        vector<int>Ans;
        for(i=1;i<=n;i++)V[i]=i;
        for(i=0;i<m;i++)
        {
            p=Pair[i];
            a=find(p.x),b=find(p.y);
            if(a!=b)V[a]=b;
        }
        for(i=1;i<=n;i++)a=find(i),R[a].push_back(perm[i-1]);
        for(i=1;i<=n;i++)sort(R[i].begin(),R[i].end());
        for(i=n;i>=1;i--)
        {
            a=find(i),j=R[a].size();
            ans[i]=R[a][j-1],R[a].pop_back();
        }
        for(i=1;i<=n;i++)Ans.push_back(ans[i]);
        return Ans;
    }
};

完结撒花，若有疏漏之处，还望大佬轻喷。