Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 671 Accepted Submission(s): 350
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
题意解析：
给出n个顶点，你现在需要把这些顶点全部练起来，变成一个集合，每两个顶点之间距离的权值等于将他们两个的序号进行与操作(&)的结果，即 i 与 j 之间的距离 = i & j ，所以你第一个任务是输出将所有边连起来需要的权值之和，第二个任务是将每个顶点去找的顶点的序号输出，这里还有一个限定条件，就是如果有多个权值相等的结果，你需要输出一个字典序最小的序列，也就是每个顶点都需要去找尽量小的顶点连线。比如4(100)这个顶点，去找3(11),2(10),1(1)的话，权值都是0，但是1是最小值，所以只能去找1；
解题分析：
先给出几个连接的情况：
首先我们知道，我们需要从2到n依次去找到对应的顶点，但其实这些点的二进制数字，可以分为下面几种情况：
1. 这个数是偶数，那么它的二进制最后一位是0，那么它去跟1连线的话，权值为0；
2. 它为奇数，但是所有二进制位全是1，比如3(11)，那么它跟4(100)进行与操作，结果即为0，所以在这种情况下，我们需要判断i + 1 这个数与 n 的大小，如果，那么它就可以去找 i + 1 这个点，这样可以令权值为0；但是如果，也就是 i + 1 这个数不存在，那么它就只能去找1，因为只有这种情况才能令权值最小，而且字典序也是最小；
3. 它是奇数，但是其中有0的存在，比如5(101)，那么它可以去跟2(10)进行与操作，这样可以令权值为0；当这个数有多个0时，比如21(10101)，那么这个数跟2(10)和10(1010)进行与操作都可以使权值为0，但是要使字典序最小，我们只能选择2，也就是这个数的0所在的最小的权值；
而我们去实现的时候，就用二维数组，a[ i ] [ 0 ]存的是点 i 所对应的顶点序号，a[ i ] [ 1 ]存的是点 i 与对应顶点之间的权值；
代码篇：
#include <iostream> #define ll long long ///定义long long using namespace std; ll a[200005][2]; ///0为序号，1为权值; ll judge(ll a) ///判断有无0，若有返回最小权值 { ll ans = 0, res = 1; while(a) { if(!(a & 1)) ///判断最后一位是不是0 { ans = res; return ans; } res <<= 1; a >>= 1; } return ans; } int main() { ios::sync_with_stdio(false); ll t, n, sum; cin >> t; while(t--) { sum = 0; cin >> n; for(ll i = 2; i <= n; i++) { if(i % 2 == 0) ///偶数 { a[i][0] = 1; a[i][1] = 0; } else ///奇数 { if(ll x = judge(i)) ///有0 { a[i][0] = x; a[i][1] = 0; } else ///全1 { if(i + 1 <= n) { a[i][0] = i + 1; a[i][1] = 0; } else { a[i][0] = 1; a[i][1] = 1; } } } sum += a[i][1]; } cout << sum << endl; for(ll i = 2; i < n; i++) ///控制输出 cout << a[i][0] << ' '; cout << a[n][0] << endl; } return 0; }
OVER！
