2019 蓝桥杯省赛 A 组模拟赛(一)-修建公路
题目:
蒜头国有 nn 座城市,编号分别为 0,1,2,3,…,n-1。编号为 x 和 y 的两座城市之间如果要修高速公路,必须花费 x|y 个金币,其中|
表示二进制按位或。
吝啬的国王想要花最少的价格修建高速公路,使得所有城市可以通过若干条高速公路互相达到。现在请你求出 n=2019 时,一共有多少不同的方案,能让所有城市连通并且造价最低。方案数可能很大,你只需输出对 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; }