老师为即将毕业的同学们准备了一场舞会，有$2N$个同学会参加这场舞会，他们会被分成$N$对跳舞，每个人有一个编号，如果编号为$i$的同学和编号为$j$的同学配对，那么这一对的满意度是$A_{i,j}(i<j)$，我们规定这个舞会的满意度为每一队的满意度的异或和，也就是说，当同学们分成$N$组后，第$i$对同学的满意度为$A_i$，那么舞会的满意度为$A1\oplus A2\oplus ...AN$

请你求出本场舞会满意度的最大值

输入描述

第一行给出一个数$N$，有$2N$个人参加舞会

接下来给出一个矩阵表示$i$和$j$配对时的满意度

$A_{1,2},A_{1,3},...A_{1,2N}$

$A_{2,3},...A_{2,2N}$

… … …

$A_{2N-1,2N}$

其中$1\le N\le 8,0\le A_{i,j}\le 2^{30}$

输出描述

输出本场舞会满意度的最大值

样例输入

2
4 0 1
5 3
2

样例输出

6

样例解释

如果 { 1 , 2 } , { 3 , 4 } , a n s = A 1 , 2 ⊕ A 3 , 4 = 4 ⊕ 2 = 6 \{1,2\},\{3,4\},ans=A_{1,2}⊕A_{3,4}=4⊕2=6 {1,2},{3,4},ans=A1,2​⊕A3,4​=4⊕2=6

如果 { 1 , 3 } , { 2 , 4 } , a n s = A 1 , 3 ⊕ A 2 , 4 = 0 ⊕ 3 = 3 \{1,3\},\{2,4\},ans=A_{1,3}⊕A_{2,4}=0⊕3=3 {1,3},{2,4},ans=A1,3​⊕A2,4​=0⊕3=3

如果 { 1 , 4 } , { 2 , 3 } , a n s = A 1 , 4 ⊕ A 2 , 3 = 1 ⊕ 5 = 4 \{1,4\},\{2,3\},ans=A_{1,4}⊕A_{2,3}=1⊕5=4 {1,4},{2,3},ans=A1,4​⊕A2,3​=1⊕5=4

最后答案为$max(6,3,4)=6$

解题思路

因为数据$N\le 8$，所以直接$DFS+$剪枝就可以。

问题可能在于如何$DFS$：

写一个$DFS$需要定义四个部分（并不一定都需要）：状态部分（函数声明），停止条件，主体部分，返回后操作。

我们从简单到复杂逐个定义。

（1）结束条件：配对数到达$n$；

（2）返回后操作：将已配对的两个人取消标记；

（3）状态部分：状态部分为已配对数、舞会满意度；

（4）主体部分：首先利用一个循环找出第一个未配对的人，然后再用一个循环去为他搭配所有可能。

void dfs(int couple, int confid) {//状态if (couple == n + 1) {//结束条件ans = max(ans, confid);return;}//函数主体int i, j;for (i = 1; i <= 2 * n; i++) {if (!vis[i]) {for (j = i + 1; j <= 2 * n; j++) {if (!vis[j]) {vis[i] = vis[j] = true;dfs(couple + 1, confid ^ relation[i][j]);vis[i] = vis[j] = false;//返回后操作}}}}
}

如何降低时间复杂度：

（1）依靠遍历顺序：$1,2$和$2,1$算一种情况，所以只考虑前者（递增序），依靠遍历查找的顺序来实现；

（2）依靠$DFS$序：我们在第一层配对$1$和$3$，在第二层配对$2$和$4$这种情况与我们在第一层配对$2$和$4$和在第二层配对$1$和$3$二者是相同的。

优化之后的算法如下：

void dfs(int couple, int confid) {if (couple == n + 1) {ans = max(ans, confid);return;}int i, j;for (i = 1; i <= 2 * n; i++) {if (!vis[i]) break;//DFS序剪枝}for (j = i + 1; j <= 2 * n; j++) {//遍历顺序剪枝if (!vis[j]) {vis[i] = vis[j] = true;dfs(couple + 1, confid ^ relation[i][j]);vis[i] = vis[j] = false;}}
}

AC代码如下：

#include <iostream>
using namespace std;
const int max_n = 16;int relation[max_n + 1][max_n + 1], n, ans;
bool vis[max_n + 1];void dfs(int couple, int confid) {if (couple == n + 1) {ans = max(ans, confid);return;}int i, j;for (i = 1; i <= 2 * n; i++) {if (!vis[i]) break;}for (j = i + 1; j <= 2 * n; j++) {if (!vis[j]) {vis[i] = vis[j] = true;dfs(couple + 1, confid ^ relation[i][j]);vis[i] = vis[j] = false;}}
}int main() {cin >> n;for (int i = 1; i <= 2 * n; i++) {for (int j = i + 1; j <= 2 * n; j++) {cin >> relation[i][j];}}dfs(1, 0);cout << ans << endl;return 0;
}

（并没有什么奇妙的算法呢$qwq$）