题目描述
给定一张nnn个点的无向完全图,其中两点之间的路径边权为两点编号的按位与(编号为 (1,2,...,n)(1,2,...,n)(1,2,...,n)),即w(u,v)=u&v(1≤u,v≤n)w\left(u, v \right )=u\&v \left( 1 \le u, v \le n \right)w(u,v)=u&v(1≤u,v≤n),求该图最小生成树的边权和。
输入描述:
本题包含多组数据 第一行包含一个正整数T(1≤T≤2×105)T \left( 1 \le T \le 2 \times 10^5 \right)T(1≤T≤2×105),代表测试用例的组数。 对于每组数据: 第一行输入一个正整数n(2≤n<109)n \left( 2 \le n < 10^{9} \right)n(2≤n<109),代表该完全图的节点个数。
输出描述:
对于每组数据: 输出一行一个整数,代表该完全图最小生成树的边权和。
示例1
输入
1
3输出
1
说明
对于n=3n=3n=3的完全图,生成树的方式有如下三种:
* ,生成树的权值之和为0+1=1
* ,生成树的权值之和为1+2=3
* ,生成树的权值之和为0+2=2
选择第一种连接方式最优,因此最小生成树的权值之和为1。
思路:
做这个题首先要先了解二进制的一些小特征
第一个,我们要知道所有的偶数二进制的最后以为一定是0,所以我可以用 1 去连接所有的偶数,总权值和为0
第二个,我们要知道一个特点,就是二进制的中,高位的一个1,即使后面全是0,他也比高位为0后面全是1的数大,所以我们的奇数就可以分为两类了,一类是二进制全部为1的,一类是二进制中有0存在的。
二进制中全部为1的数,我们要想让他贡献最小,可以考虑他的下一个数存不存在。比如 就可以用 来连接,他的贡献也是 0.
二进制中有 0 存在的,我们就可以找小于他的一个数来跟他连接,找的这个数的二进制各位数字恰好与其相反,所以这一类的贡献也都是0
综上,我们就可以看出答案只有两种情况,一个是1,一个是0。总结起来,其实就是看最后一个数属于哪一类,如果属于二进制中全1的一类的话,他的下一个就不存在了,所以我们只能考虑让他跟1连,与运算之后是1.(与其他数运算结果为什么大,就是第二条)
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int a[N];
void solve(){int n;cin >> n;if(n % 2 == 0){cout << "0\n";}else{bool flag = 0;while(n){if(n % 2 == 0){flag = 1;break;}n /= 2;}if(flag)cout << "0\n";else cout << "1\n";}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while(T--){solve();}return 0;
}