HDU-6614 AND Minimum Spanning Tree(思维）(2019杭电多校第四场1001)

题目链接：题目链接
1001AND Minimum Spanning Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3206 Accepted Submission(s): 1018

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.

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.

题意：给出一个无向带权图，其中两个顶点之间的边权重是两顶点之编号作与运算，要求给出该图的最小生成树和它的总权重，如果有多个方案要求最小字典序的方案。
考察：首先需要理解最小生成树是什么不然不知道如何下手，故本题考查最小生成树的理解、思维、位运算
思路：①如果顶点编号是偶数：直接和1作与运算，得0（偶数二进制最低位是0，1的高位都是0，只有最低位是1，与运算后就得0）
②如果节点编号是奇数：按照偶数位这边的想法，我们也尽量去让边的权重为0，故而对于某节点p，它的二进制表示下第x位是0并且图中存在顶点2^x也即2x<=n记为顶点q，我们就直接让p和q相连，当然我们可以发现可能会有多个满足条件的q，题目要求字典序最小，我们应该选择x尽量小，这样q也会尽量小，因而我们就能得到字典序最小排列。当然，如果p=2^x-1,也就是p的每一位都是1或者说按上述方法得到的q已经大于n，我们直接选择这条边和1相连，因为取不到0就取1嘛。也就是说，树中的边只会有0和1两种情况。
AC代码:

#include <bits/stdc++.h>

#define rep(i, n) for(int i=1;i<=n;i++)
#define per(i, n) for(int i=n;i>=1;i--)
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
//const ll inf = INT64_MAX;
using namespace std;
int ans[maxn];
int weight;

int main() {
    int n, T;
    scanf("%d", &T);
    while (T--) {
        weight = 0;
        scanf("%d", &n);
        for (int i = 2; i <= n; i++) {
            if (i&1==0) ans[i] = 1;//偶数和1连接
            else {//奇数
                int x = i, y = 0;
                while (x & 1) {//寻找最低位的0
                    y++;
                    x >>= 1;
                }
                if ((1<<y) <= n)//也就是说2^y<=n，我们就让这个当前顶点和这个顶点连接
                    ans[i] = (1<<y);
                else {//最低位0超出范围或者是全为1，将其和节点1连接
                    ans[i] = 1;
                    weight++;//只有这个时候权重加1
                }
            }
        }
        cout << weight << endl;
        rep(i, n - 1) {
            if (i == 1) cout << ans[i + 1];
            else cout << ' ' << ans[i + 1];
        }
        cout << endl;
    }
    return 0;
}