codeforces 766E 二进制思想dp

官方题解看了半天硬是没懂…最后自己琢磨出来了。 这题主要是二进制的思想，因为异或是按位运算，可以把每个数按照二进制拆成若干个0和1，对每个”位”建树，然后用动态规划的思想求和。
具体实现方法：
以1为根建dfs树。想象从1到一个叶节点的一条路，又有1到另一个叶节点的一条路。假设我们暴力做，那答案里肯定得分别把这两个结果算出来加进去。那我们现在动态规划，就是尽量找到这两条路的公共部分，然后只算一次（就可以节约时间）。那么怎么找到这个公共部分呢？第一步是把复杂的路简单化：先是用二进制的方式把每个数按位拆开，这样一条路就变成了logn条路，每条上面都只有0和1。第二步就是合并。就比方说刚才的那条路，是从1到2再到3。算它，那就得先算1到2的路(a^b^c=(a^b)^c)，而1到2的路本来也是要算的。那我们就把它合并成两个1到2的加上一个2到3的。到底有几个？找个递推关系dp[][]推一下就知道了呗。我的代码里dp[n][i][j]表示的是从第n个节点开始的，二进制第i为的结果是j的路的总条数，当然也可以选择别的。
以下是ac代码。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100010;
int N,S[maxn];
long long dp[maxn][20][2],ans;
int nxt[maxn*2],to[maxn*2],fst[maxn],cnt;
void dfs(int now,int pre){
    for(int i=0;i<20;i++)
        dp[now][i][S[now]>>i&1]=1;
    for(int p=fst[now];p;p=nxt[p])if(to[p]!=pre){
        int z=to[p];
        dfs(z,now);
        for(int i=0;i<20;i++){
            ans+=((long long)dp[z][i][0]*dp[now][i][1]+(long long)dp[z][i][1]*dp[now][i][0])<<i;
            bool t=S[now]>>i&1;
            dp[now][i][0]+=dp[z][i][t];dp[now][i][1]+=dp[z][i][!t];
        }
    }
}
int main(){
    int u,v;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",S+i),ans+=S[i];
    for(int i=1;i<N;i++){
        scanf("%d%d",&u,&v);
        nxt[++cnt]=fst[u];to[cnt]=v;fst[u]=cnt;
        nxt[++cnt]=fst[v];to[cnt]=u;fst[v]=cnt;
    }
    dfs(1,1);
    printf("%I64d",ans);
    return 0;
}

最后

以上就是外向棒棒糖为你收集整理的codeforces 766E 二进制思想dp的全部内容，希望文章能够帮你解决codeforces 766E 二进制思想dp所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。