[TIOJ] 1094. C.幼稚國王的獎賞
題目連結:http://tioj.infor.org/problems/1094
這題有三種作法,一種是我看完馬上想到的砍半枚舉後套trie
這題有三種作法,一種是我看完馬上想到的砍半枚舉後套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;
}
留言
張貼留言