2019 蓝桥杯省赛 A 组模拟赛（一）-修建公路

LJHAHA 2021-08-29 原文

题目：

蒜头国有

吝啬的国王想要花最少的价格修建高速公路，使得所有城市可以通过若干条高速公路互相达到。现在请你求出 $10^9+7取模的结果。$

样例输入

无

样例输出

无

思路：

这一题的主要考点是位运算和最小生成树。
分析：
根据题意我们可以知道这颗树的边权值是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作为我们起点。
转载自：https://blog.csdn.net/caipengbenren/article/details/87118136

拓展：在c语言中1<<i与i<<1的区别是什么

1<<i是把1左移i位，每次左移以为就是乘以2，所以1<<i的结果是1乘以2的i次方
i<<1就是把i左移一位，即i乘以2，假如i=5,最后结果就是5*2=10
至于为什么左移一位是乘以2，这是运算器内部机理，说起来就更多了，计算机做乘法运算的时候不是一个个的相加，而是用移位来实现的。>>这个符号是右移，与左移相反，右移是除以2.
这里还有一点容易搞错的，就是移位符号的左边是需要计算的数，右边是需要移动的位数。

代码：

#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)//如果数i右移j位为1，即统计二进制状态下的i中有多少个1
                cnt ++;
        }
        ans = ans * ((1 << cnt) - 1) % mod;//(1<<cnt)表示1*2^cnt
    }
    cout<<ans % mod;
}