[TIOJ] 1094. C.幼稚國王的獎賞

題目連結:http://tioj.infor.org/problems/1094

---

這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie

#include <bits/stdc++.h>
using namespace std;
const int LOG_C = 20;
const int N = 30 + 5;

inline int two(int x){return 1<<x;}

class Trie{
	private:
		static constexpr int MEM = 5000000;
		struct node{
			int lc, rc;
			node(): lc(0), rc(0){}
		} nodes[MEM];
		int mem_, root;
		inline int new_node(){
			assert(mem_ < MEM);
			nodes[mem_] = node();
			return mem_++;
		}
		void insert(int x, int& cur, int d){
			if(!cur) cur = new_node();
			if(d == -1) return;
			if(x & two(d)) insert(x, nodes[cur].rc, d-1);
			else insert(x, nodes[cur].lc, d-1);
		}
		int query(int x, int cur, int d){
			if(d == -1) return 0;
			if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc);
			int ret = 0;
			if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d);
			else ret = query(x, nodes[cur].lc, d-1);
			if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc);
			return ret;
		}
	public:
		void init(){
			new_node(); root = 0;
		}
		void insert(int x){
			insert(x, root, LOG_C);
		}
		int query(int x){
			return query(x, root, LOG_C);
		}
} trie;

int arr[N];

void solve1(int,int);
int solve2(int,int);

int main(){
	int n;
	while(scanf("%d", &n), n){
		trie.init();
		for(int i=0;i<n;i++) scanf("%d", arr+i);
		int mid = n>>1;
		solve1(0, mid);
		printf("%d\n", solve2(mid, n));
	}
	return 0;
}

void solve1(int l, int r){
	int n2 = 1<<(r-l);
	for(int s=0;s<n2;s++){
		int x = 0;
		for(int i=l;i<r;i++) if(s&two(i-l)){
			x ^= arr[i];
		}
		trie.insert(x);
	}
}

int solve2(int l, int r){
	int n2 = 1<<(r-l), ret = 0;
	for(int s=0;s<n2;s++){
		int x = 0;
		for(int i=l;i<r;i++) if(s&two(i-l)){
			x ^= arr[i];
		}
		ret = max(ret, trie.query(x));
	}
	return ret;
}

或是其實直接DP就可以了

#include <bits/stdc++.h>
using namespace std;
const int C = 1048576;

bool dp[C];

int main(){
	int n;
	while(scanf("%d", &n), n){
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for(int _=0;_<n;_++){
			int x; scanf("%d", &x);
			for(int i=0;i<C;i++) dp[i^x] |= dp[i];
		}
		for(int i=C-1;i>=0;i--) if(dp[i]){
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}

還可以利用線性基的概念

#include <bits/stdc++.h>
using namespace std;
const int LOG_C = 20;

inline int two(int x){return 1<<x;}
int base[LOG_C];

int main(){
	int n;
	while(scanf("%d", &n), n){
		memset(base, 0, sizeof(base));
		for(int _=0;_<n;_++){
			int x; scanf("%d", &x);
			for(int i=LOG_C-1;i>=0;i--){
				if(!(two(i) & x)) continue;
				if(base[i]) x ^= base[i];
				else{
					base[i] = x;
					for(int j=0;j<i;j++) if(base[i] & two(j)) base[i] ^= base[j];
					for(int j=i+1;j<LOG_C;j++) if(base[j] & two(i)) base[j] ^= base[i];
					break;
				}
			}
		}
		int ans = 0;
		for(int i=0;i<LOG_C;i++) ans ^= base[i];
		printf("%d\n", ans);
	}
	return 0;
}