修建公路|2019 蓝桥杯省赛 A 组模拟赛(一)第4题

原题链接

这一题的主要考点是位运算和最小生成树。
分析：
根据题意我们可以知道这颗树的边权值是x|y，而目的是生成一个最小树。所以我们要选择边权值最小的，在什么情况下x|y最小的呢？根据我之前的博客可知 x|y >= x 当且仅当 在二进制下，x的为0的位置，对应y必须为0，x为1的位置，对应y可以为0也可以为1。

解决完边权值的问题，下面就是如何生成一个最小树？
我们先思考一般情况：此时，我们已经构造出一个树，我们需要向其中加入一个结点，我们如何选择？当然是选择和要加入结点边权值最小的结点相连。而在这一题中，根据上文的论述，我们只需要统计当前结点i在二进制下有多少1(假设有n个1)，因为1的位置我们可以变化，而0的位置 我们不可以变。所以一共有2^n - 1 个可能的选择。之后我们在用这个树之前的可能构造数乘（2^n - 1 ）就是一般情况下的解决。

之后我们考虑起点的情况：我们发现编号0与任何一个数进行or运算都是0，所以0可以和任何一个结点相连都是最小的。那么，我们就可以选择0作为我们起点。

#include<iostream>
using namespace std;
const int mod = 1e9 + 7;

int main(){
    int n = 2019;
    long long ans = 1;
    for(int i = 1; i < n; i++){
        int cnt = 0;
        for(int j = 0; i >> j > 0; j++){
            if(i >> j & 1) cnt ++;
        }
        ans = ans * ((1 << cnt) - 1) % mod;
    }
    cout<<ans % mod;
}