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

牛牛的路径和

https://ac.nowcoder.com/acm/contest/10167/C

王者场ABC题解

反思一下:简单题没想好就急着敲，浪费时间，难的题反而做的快，因为想好了后代码是不会出问题的。

所以还是要先想清楚过程确定没问题在敲代码，主要是想的时间。

A:奇怪的排序问题

想清楚每次操作的过程就好做了：

肯定是从高往低去处理，(因为无论你怎么动矮的，都不会让高的人往后走)

对于当前最高的人x，如果他不是最后面的一个，则需要花费1次把他移动到最后排。（且他原本的位置置为空）

如果他是当前最后排，则不需要移动。

处理过程注意维护空的位置即可。

const int M = 1e6 + 10;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int wwork(int n, vector<int>& v) {
        // write code here
        int r=n-1;
        int mp[1000007]={0}; 
        for(int i=0;i<n;i++){
            mp[v[i]-1]=i;
        }
        int nm=0;
        for(int i=n-1;i>=0;i--){

            while(r>=0 && v[r]==-1)r--;
        //    cout<<i<<" "<<mp[i]<<"  "<<r<<" "<<nm<<endl;
            if(mp[i]!=r)nm++,v[mp[i]]=-1;
            else{
                r--;
            }

        }
        return nm;
    }
};

B：XOR和
两种方法：

方法一：打表找规律（推荐这种，尤其是表很快就能打出来的题，能省去很多时间）
打表发现:

对于一个数x，其初始f[x]=0;

如果一个数x是1的倍数，则f[x]+=1,

如果一个数x是2的的倍数，则f[x]+=2;

如果一个数x是4的的倍数，则f[x]+=4;

如果一个数x是8的的倍数，则f[x]+=8;

…………

然后直接枚举2的次幂即可。

方法二：数学推导
设一个数n，其最低位的1在y上。

则n-1 ^ n = ((1<<y) -1 ); （因为高于y的位n和n-1都不变，低于y的位刚好是n为0，n-1为1）

比如一个数（二进制表示）

10100

其减一为：

10011

则10100^10011 = 11 = 3

然后就转化为方法一中的规律去枚举求解即可

typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */

long long Sum(int n) {
        // write code here
        ll sm=(1+n)*n/2;
        ll ans=0,nw=0;
        for(int i=0;i<31;i++){
            ll tp=1ll<<i;
            nw=tp;
            ans+=nw*(n/tp);
        }
        return ans;
    }
};

C：牛牛的路径和
枚举每一位，分开进行算贡献。

只考虑第i位，树上点权就只有0/1两种，我们求的是每个全1连通块内，路径个数nm，然后让nm*(1<<x)就是这个连通块的点在第i位上对答案的贡献了。

枚举所有位即可算出最终答案。

const int M = 1e5+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 点的个数
     * @param u int整型vector 每条边的起点
     * @param v int整型vector 每条边的终点
     * @param p int整型vector 每个点的价值
     * @return long长整型
     */

    int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
int a[M],vs[M];
long long nm;
void dfs(int x){
    vs[x]=1;
    nm++;
    for(int i=head[x];i;i=ee[i].nxt){
        int y=ee[i].to;
        if(vs[y]||a[y]==0)continue;
        dfs(y);
    }
}
long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& p) {
        // write code here
        init(n);
        for(int i=0;i<n-1;i++){
            a[i]=p[i];
            add(u[i],v[i],1);
            add(v[i],u[i],1);
        }
        long long ans=0;
        for(int sta=0;sta<=20;sta++){
            for(int i=0;i<n;i++)if((p[i]>>sta)&1)a[i]=1;else a[i]=0;
            memset(vs,0,sizeof(vs));
            for(int i=0;i<n;i++){
                if(vs[i]||a[i]==0)continue;
                nm=0;
                dfs(i);
                ans+=(nm+nm*(nm-1)/2)*(1<<sta);
            }
        }
        return ans;
    }
};