Znzryb's Blog
0%

ABC-386-E - Maximize XOR 

Posted on Edited on

思路讲解

思路其实就是组合数生成惯用套路+深度控制

组合数生成其实就是从start开始，这样可以保证加入顺序都是从编号小的到编号大的，进而达到无视元素加入顺序的效果。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int dep,int start,ull sum){
	if(dep>T){
		ans=max(ans,sum^xorSum);
		return;
	}
	FOR(i, start, N){
		if(vis[i]) continue;
		vis[i]=true;
		dfs(dep+1,i+1,sum^A[i]);
		vis[i]=false;
	}
}

当然，利用异或计算的性质，我们可以控制深度，枚举不选的，而不是枚举选的，以减少计算次数

1
2
3
4
5
if(T>N-T){
		T=N-T;
	}else{	// 正向进行不需要异或
		xorSum=0;
	}

AC代码

AC

https://atcoder.jp/contests/abc386/submissions/62216769

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e6)+10,MAXval=static_cast<ll>(1e18)+3;

ll N,T;
ull A[MAXN];
bool vis[MAXN];
ull ans,xorSum;

void dfs(int dep,int start,ull sum){
	if(dep>T){
		ans=max(ans,sum^xorSum);
		return;
	}
	FOR(i, start, N){
		if(vis[i]) continue;
		vis[i]=true;
		dfs(dep+1,i+1,sum^A[i]);
		vis[i]=false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	FOR(i, 1, N){
		cin>>A[i];
		xorSum^=A[i];
	}
	if(T>N-T){
		T=N-T;
	}else{	// 正向进行不需要异或
		xorSum=0;
	}
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc386/submissions/62216769
*/

心路历程（WA，TLE，MLE……）