2023河南萌新联赛第（五）场：郑州轻工业大学 --Kruskal

题目描述

给定一张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;
}