传送门
AND Minimum Spanning Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 378 Accepted Submission(s): 190
Problem Description
You are given a complete graph with N vertices, numbered from 1 to N.
The weight of the edge between vertex x and vertex y (1<=x, y<=N, x!=y) is simply the bitwise AND of x and y. Now you are to find minimum spanning tree of this graph.
The weight of the edge between vertex x and vertex y (1<=x, y<=N, x!=y) is simply the bitwise AND of x and y. Now you are to find minimum spanning tree of this graph.
Input
The first line of the input contains an integer T (1<= T <=10), the number of test cases. Then T test cases follow. Each test case consists of one line containing an integer N (2<=N<=200000).
Output
For each test case, you must output exactly 2 lines. You must print the weight of the minimum spanning tree in the 1st line. In the 2nd line, you must print N-1 space-separated integers f2, f3, … , fN, implying there is an edge between i and fi in your tree(2<=i<=N). If there are multiple solutions you must output the lexicographically smallest one. A tree T1 is lexicographically smaller than tree T2, if and only if the sequence f obtained by T1 is lexicographically smaller than the sequence obtained by T2.
Sample Input
2
3
2
Sample Output
1
1 1
0
1
Hint
In the 1st test case, w(1, 2) = w(2, 1) = 0, w(1, 3) = w(3, 1) = 1, w(2, 3) = w(3, 2) = 2. There is only one minimum spanning tree in this graph, i.e. {(1, 2), (1, 3)}.
For the 2nd test case, there is also unique minimum spanning tree.
Source
题意:
有N个结点,两两之间的权值为两个点取与
比如说结点2和结点3之间的权值 W(2,3) = 10&11 = 10
问整个图的最小生成树
第一行输出最小生成树的权值和
第二行分别输出2到N节点连接的点(如果一个节点连接了2个点的话,需要输出小的那个)
思路:
举个例子:
10011(二进制)最好和哪个结点连接呢
无疑是 00100(二进制)
感受一下?
其实本质就是找到第一个非1的位置,其他的所有位置都置为0就OK。
这里有个特殊情况
如果是111?(二进制)
那么最优的连接结点就是1000。
但是如果N恰好就是7,那么就没有1000(十进制是8)来和111(十进制是7)组队了。
111只能去和1连接(被迫)
所以第一行答案要么是1要么是0
判断一下N是不是二的幂次减1就行
第二行的话可以按照上面的规律去找,即找到第一个非1的位置为1,其他的都为0
#include"bits/stdc++.h" using namespace std; typedef long long LL; int a[200011]; bool judge(int x){ int n = x&(x-1); return n == 0; } /* 找到二进制中第一个不是0的 比如说 1001 返回的是 0010 1111返回的是10000 */ int getMin(int x){ int ans = 1; while(true){ int k = x&1; x >>= 1; if(k == 0){ break; } ans <<= 1; } return ans; } int main() { int _; for(scanf("%d",&_);_--;){ int n; scanf("%d",&n); memset(a,0,sizeof(int)*(n+1)); judge(n+1)?puts("1"):puts("0"); for(int i = 2 ; i <= n ; i++){ int Min = getMin(i); Min > n? printf("1"):printf("%d",Min);//判断一下找到的数是不是大于n i == n ? printf(" "):printf(" "); } } } /* 2 3 2 */