牛客编程巅峰赛S2第10场 - 钻石&王者 题解

A题：
作者成功地把所有的错误做法都试了一遍。
因为数只能往后移，所以在当前数后面有比它小的数的时候，这个数肯定要往后移，不然的话就没有机会往后移了。
所以，我们只要维护一个后缀最小值即可。
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int wwork(int n, vector<int>& a) {
        int s=a.back(),ans=0;
        for(int i=n-2;i>=0;i--){
            if(a[i]>s)ans++;
            else s=a[i];
        }
        return ans;
    }
};

时间复杂度 O(n)

B题：
把表打出来后，通过手算或用OEIS找到规律即可。
规律就是 f[i]=i+f[i/2]*2 (i/2向下取整)
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    long long calc(int x){
        if(x==1)return 1;
        return x+calc(x/2)*2;
    }
    long long Sum(int n){
        return calc(n);
    }
};

时间复杂度 O(log n)

C题：
逐位处理。因为 ,所以可以枚举位数k从0到20进行处理。
我们定义，当两个点之间的路径第k位都为1时，就称这两个点之间可以抵达。
如果两条边相连点x,y，若p[x]和p[y]在二进制表示下的第k位都为1，那么说明x可以抵达的任何点都可以可以抵达y可以抵达的任何点，所以用并查集维护集合。
然后求出每个集合的大小，用siz来表示。
最后对于同一个集合内的任何点，他们之间都可以相互抵达，进行计算即可。注意要特殊处理路径为单个点的情况
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 点的个数
     * @param u int整型vector 每条边的起点
     * @param v int整型vector 每条边的终点
     * @param p int整型vector 每个点的价值
     * @return long长整型
     */
    long long fa[100010],siz[100010],v[100010];
    int get(int x){
        if(x==fa[x])return x;
        return fa[x]=get(fa[x]);
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        long long ans=0,s=1;
        for(int k=0;k<=20;k++){
            for(int i=0;i<n;i++){
                fa[i]=i;
                siz[i]=0;
            }
            for(int i=0;i<n-1;i++)
                if(p[u[i]]>>k&1&&p[v[i]]>>k&1){
                    int x=get(u[i]),y=get(v[i]);
                    if(x==y)continue;
                    fa[x]=y;
                }
            for(int i=0;i<n;i++)
                siz[get(i)]++;
            for(int i=0;i<n;i++)
                if(fa[i]==i&&p[i]>>k&1)ans=ans+(siz[i]+1)*siz[i]/2*s;
            s=s*2;
        }
        return ans;
    }
};

时间复杂度 O(n log n)