UVA1326 Jurassic Remains

Paleontologists in Siberia have recently found a number of fragments of Jurassic period dinosaur skeleton. The paleontologists have decided to forward them to the paleontology museum. Unfortunately,the dinosaur was so huge, that there was no box that the fragments would fit into. Therefore it wasdecided to split the skeleton fragments into separate bones and forward them to the museum wherethey would be reassembled. To make reassembling easier, the joints where the bones were detached from each other were marked with special labels. Meanwhile, after packing the fragments, the new bones were found and it was decided to send them together with the main fragments. So the new bones were added to the package and it was sent to the museum.

However, when the package arrived to the museum some problems have shown up. First of all, not all labels marking the joints were distinct. That is, labels with letters ‘A’ to ‘Z’ were used, and each two joints that had to be connected were marked with the same letter, but there could be several pairs of joints marked with the same letter.

Moreover, the same type of labels was used to make some marks on the new bones added to the box. Therefore, there could be bones with marked joints that need not be connected to the other bones.

The problem is slightly alleviated by the fact that each bone has at most one joint marked with someparticular letter.

Your task is to help the museum workers to restore some possible dinosaur skeleton fragments. That is, you have to find such set of bones, that they can be connected to each other, so that the following

conditions are true:

• If some joint is connected to the other joint, they are marked with the same label.

• For each bone from the set each joint marked with some label is connected to some other joint.

• The number of bones used is maximal possible.

Note that two bones may be connected using several joints.

Input

Input consists of several datasets. The first line of each dataset contains N — the number of bones

(1 ≤ N ≤ 24). Next N lines contain bones descriptions: each line contains a non-empty sequence of different capital letters, representing labels marking the joints of the corresponding bone.

Output

For each dataset, on the first line of the output file print L — the maximal possible number of bones that could be used to reassemble skeleton fragments. After that, in another line, output L integer numbers in ascending order — the bones to be used. Bones are numbered starting from one, as they are given in the input file.

Sample Input

1

ABC

6

ABD

EG

GE

ABE

AC

BCD

Sample Output

5

1 2 3 5 6

这道题很好理解，就是有几个地方想要重点记录一下

Meet-in-the-Middle

如果这道题用最暴力的方式求解，每一组数据的时间复杂度为224,这是我们很难忍受的，但是如果我们分开来看，把每组数据分成前一半和后一半来看，这样时间复杂度就降到了212，哇，这可不仅仅是降了一半，这直接开根号了呀！所以特殊种类的情况下这样的暴力简直不要太美，可能有些同学会问了，这样把一组数分成两组，每组的时间复杂度是212，后面继续一个双重循环，时间复杂度不就又恢复到224了吗，如果我们这样处理的话的确时间上并没有得到很好的优化，但是我们在做后一半数据的处理的时候完全可以顺便把这样的判断处理完，处理完后一半数据的一种情况之后直接判断该数在之前有没有出现过就好了呀，在处理后一半数据的时候边处理边判断是不是很Meet。

进制的转化

我们可以把一串英文字符转化为一个数，其中A代表最后一位，B代表倒数第二位，以此类推就能表示一个数了.

for(int i=0;i<n;i++){
		string s;
		cin >> s;
		int a = 0;
		for(int j=0;j<s.length();j++){
			a ^= (1<<(s[j]-'A'));
		}
	}
           

那么怎样把这个数还原呢，也很简单，只需要从后往前判断就好了，假如我们知道这个二进数的长度为 n 。

int n;
string s;
for(int i=0;i<n;i++){
	if(shu & i<<j) s += ('A' + i);
}
           

对前后两半数的处理

第一半数直接暴力进行求解就好，假如一共有n个数字，所以前一部分就是n/2，我们令n1 = n/2，所以可以选择的种类有（1 << n1）种，所以我们的第一个循环就是

for(int i=0;i<(1<<n1);i++);

同理剩下n-n1个数，我们令n2 = n - n1，所以一共有（1<<n2）个数，所以第二个循环是

for(int i=0;i<(1<<n2);i++)

，但是我们要知道这个 i 对应的应该是从n/2+1开始的，所以第二组循环的第i个数应该对应着整体的第（i+n1）个数。

int n2 = n-mid;
		for(int i=0;i<(1<<n2);i++){
			int sum = 0;
			for(int j=0;j<n2;j++) if(i & (1<<j)) sum ^= shu[mid+j];
			if(table[sum]){//如果在前一半中存在
				if(Sum(ans) < Sum(table[sum]^(i<<mid))){
					ans = table[sum]^(i<<mid);
				}
			}
		}
           

完整代码如下：

#include<iostream>
#include<string>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 30;
int shu[maxn];
map<int,int>table;

//void dfs(int wei,int n,int before,int beforei){
//	if(wei>n) return ;
//	dfs(wei+1,n,before,beforei);
//	before ^= shu[wei];
//	beforei ^= (1<<(wei-1));
//	if(Sum(table[before]) < Sum(beforei)) 
//		table[before] = beforei;
//	dfs(wei+1,n,before,beforei);
//}
//void dfs2(int wei,int n,int before,int beforei){
//	if(wei>n) return ;
//	dfs2(wei+1,n,before,beforei);
//	before ^= shu[wei];
//	beforei ^= (1<<(wei-1));
//	if(Sum(hou[before]) < Sum(beforei)) 
//		hou[before] = beforei;
//	if(table[before]){
//		int he = table[before] ^ hou[before];
//		if(Sum(he)>ans) ans = he;
//	}
//	dfs2(wei+1,n,before,beforei);
//}

int Sum(int a){
	int sum = 0;
	while(a){
		if(a&1) sum++;
		a>>=1;
	}
	return sum;
}
void print(int a){	
	int k = 0;
	while(a){
		if(a&1) cout << k+1 << ' ';
		k++;
		a>>=1;
	}
	cout << endl;	
}

int main(){
	int n;
	while(cin >> n){
		memset(shu,0,sizeof(shu));
		table.clear();
		int ans = 0;
		for(int i=0;i<n;i++){
			string s;
			cin >> s;
			int a = 0;
			for(int j=0;j<s.length();j++){
				a ^= (1<<(s[j]-'A'));
			}
			shu[i] = a;
		}		
		int mid = n/2;
//		dfs(1,mid,0,0);
//		dfs2(mid+1,n,0,0);
		for(int i=0;i<(1<<mid);i++){
			int sum = 0;
			for(int j=0;j<mid;j++) if(i & (1<<j)) sum ^= shu[j];
			if(table[sum]==0 || (Sum(table[sum])<Sum(i))) table[sum] = i;
		}
		int n2 = n-mid;
		for(int i=0;i<(1<<n2);i++){
			int sum = 0;
			for(int j=0;j<n2;j++) if(i & (1<<j)) sum ^= shu[mid+j];
			if(table[sum]){
				if(Sum(ans) < Sum(table[sum]^(i<<mid))){
					ans = table[sum]^(i<<mid);
				}
			}
		}
		cout << Sum(ans) << endl;
		print(ans);
	}
	return 0;
}