2026 杭电春季联赛 4——1004-左右脑互搏

题目大意

题目规则
有两个玩家（左脑先手，右脑后手）进行回合制游戏。
初始给出一个包含 $n$ 个正整数的多重集合。
每次操作时，玩家必须从集合中删除一个数 $x$，且必须满足：$x$ 严格大于删除该数后集合中剩余元素的异或和。
特别地，若当前集合中只有一个元素，则可以直接将其删去。
无法进行合法操作的玩家判定为失败。
假设双方均采用最优策略，求哪方获胜。

输入格式
第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。
对于每组测试数据：
第一行包含一个整数 $n$（$1 \le n \le 20$），表示初始元素的数量。
第二行包含 $n$ 个正整数，表示初始元素，元素范围 $[1, 100000]$。

输出格式
如果左脑（先手）获胜，输出 “Left”，否则输出 “Right”。

样例

Input:
3
1
6
4
2 3 6 8
2
2 2

Output:
Left
Right
Right

样例解释第一组数据：集合为 $\{6\}$。左脑可以直接删除唯一的一个元素，获胜。
第二组数据：集合为 $\{2, 3, 6, 8\}$。

• 左脑只能先删除 8（此时剩余元素异或和为 $2 \oplus 3 \oplus 6 = 7$，满足 $8 > 7$）。

• 右脑只能再删除 6（此时剩余元素异或和为 $2 \oplus 3 = 1$，满足 $6 > 1$）。

• 左脑只能再删除 3（此时剩余元素异或和为 $2$，满足 $3 > 2$）。

• 右脑面对唯一的元素 2，最后将其删去，获胜。

第三组数据：集合为 $\{2, 2\}$。左脑如果尝试删除其中一个 2，删除后剩余元素的异或和为 2，不满足 $2 > 2$ 的条件。因此左脑无法删除任何元素，右脑直接获胜。

思路讲解

latex 记忆化

\documentclass{article}

\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{tocloft} % 支持目录引导点
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning, calc}

% 与原先 listings 外观大致对齐；
\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

% --- 目录样式修改 ---
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}} % 让 section 也有点点
% ------------------

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref} % 添加超链接和PDF书签支持

\definecolor{leftc}{RGB}{220,80,60}    % 红色 — 左脑
\definecolor{rightc}{RGB}{50,120,200}  % 蓝色 — 右脑
\definecolor{winc}{RGB}{0,160,80}      % 绿色 — 胜
\definecolor{losec}{RGB}{160,160,160}  % 灰色 — 负
\definecolor{reuse}{RGB}{180,80,200}   % 紫色 — 状态复用

\title{1004 左右脑互搏 题解}
\author{Gospel\_rock}
\date{}

\begin{document}
\maketitle

\section{题意}

给定一个包含 $n$（$1 \le n \le 20$）个正整数的多重集合 $S$。
左脑（先手）和右脑（后手）轮流操作：每次必须从集合中删除一个元素 $x$，
且 $x$ 必须\textbf{严格大于}删除后剩余元素的异或和。
若集合中只剩一个元素，可以直接删去（剩余异或和为 $0$）。
无法操作者判负。双方均采用最优策略，求谁获胜。

\section{分析}

\subsection{博弈建模}

这是一个标准的\textbf{组合博弈}问题。
每个局面（当前集合的状态）在双方最优策略下有确定的胜负：

\begin{itemize}
	\item \textbf{必胜态}：存在至少一种合法操作，使得对手进入\textbf{必败态}。
	\item \textbf{必败态}：所有合法操作都使对手进入\textbf{必胜态}；或者根本无法操作。
\end{itemize}

空集是必败态（当前玩家无法操作）。我们从空集出发，自底向上递推出所有状态的胜负。

\subsection{状态表示——为什么需要状压？}

朴素做法是对多重集合进行 DFS 回溯搜索。但问题在于：
\textbf{不同的删除顺序可以到达相同的剩余集合}。
例如先删 $a$ 再删 $b$，和先删 $b$ 再删 $a$，
到达的集合完全一样，博弈结论也一样，却被搜了两次。

图~\ref{fig:dag} 展示了 $3$ 个元素 $\{a_0, a_1, a_2\}$ 的状态转移关系。
每个节点是一个子集（用二进制掩码标注），
箭头表示"删除一个元素"的转移。
可以看到 $\{a_0\}$、$\{a_1\}$、$\{a_2\}$ 各自都被\textbf{两条不同的路径}到达。
如果不记忆化，同一个状态会被重复计算多次；
当 $n = 20$ 时，不同的删除排列数量可达 $20!$，远远无法承受。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[
	>=Stealth,
	node distance=1.8cm and 2.2cm,
	state/.style={rectangle, rounded corners=4pt, draw, thick,
		minimum width=1.6cm, minimum height=0.7cm, align=center, font=\small},
	reusearrow/.style={->, thick, reuse, dashed},
	normarrow/.style={->, thick, black!70},
]
	% Layer 0
	\node[state, fill=leftc!12] (111) {$111$\\[-2pt]{\scriptsize $\{a_0,a_1,a_2\}$}};

	% Layer 1
	\node[state, fill=rightc!12, below left=1.6cm and 2.2cm of 111] (011) {$011$\\[-2pt]{\scriptsize $\{a_0,a_1\}$}};
	\node[state, fill=rightc!12, below=1.6cm of 111]              (101) {$101$\\[-2pt]{\scriptsize $\{a_0,a_2\}$}};
	\node[state, fill=rightc!12, below right=1.6cm and 2.2cm of 111] (110) {$110$\\[-2pt]{\scriptsize $\{a_1,a_2\}$}};

	% Layer 2（加宽间距，避免交叉边标签重叠）
	\node[state, fill=leftc!12, below left=1.6cm and 2.2cm of 101] (001) {$001$\\[-2pt]{\scriptsize $\{a_0\}$}};
	\node[state, fill=leftc!12, below=1.6cm of 101]                (010) {$010$\\[-2pt]{\scriptsize $\{a_1\}$}};
	\node[state, fill=leftc!12, below right=1.6cm and 2.2cm of 101] (100) {$100$\\[-2pt]{\scriptsize $\{a_2\}$}};

	% Layer 3
	\node[state, fill=losec!30, below=1.6cm of 010] (000) {$000$\\[-2pt]{\scriptsize $\varnothing$}};

	% Edges: Layer 0 -> Layer 1
	\draw[normarrow] (111) -- node[above left, font=\scriptsize] {删 $a_2$} (011);
	\draw[normarrow] (111) -- node[left, font=\scriptsize] {删 $a_1$} (101);
	\draw[normarrow] (111) -- node[above right, font=\scriptsize] {删 $a_0$} (110);

	% Edges: Layer 1 -> Layer 2
	% 不交叉的边：标签放中间即可
	\draw[normarrow] (011) -- node[left, font=\scriptsize] {删 $a_1$} (001);
	\draw[normarrow] (110) -- node[right, font=\scriptsize] {删 $a_1$} (100);
	% 交叉的边：标签靠近起点，避免在交叉处重叠
	\draw[normarrow] (101) -- node[pos=0.2, left, font=\scriptsize] {删 $a_2$} (001);
	\draw[normarrow] (011) -- node[pos=0.2, right, font=\scriptsize] {删 $a_0$} (010);
	\draw[normarrow] (110) -- node[pos=0.2, left, font=\scriptsize] {删 $a_2$} (010);
	\draw[normarrow] (101) -- node[pos=0.2, right, font=\scriptsize] {删 $a_0$} (100);

	% Edges: Layer 2 -> Layer 3
	\draw[normarrow] (001) -- (000);
	\draw[normarrow] (010) -- (000);
	\draw[normarrow] (100) -- (000);

	% 标注复用
	\node[reuse, font=\small\bfseries, align=center, right=0.5cm of 100] {多条路径\\汇聚！};
\end{tikzpicture}
\caption{$3$ 个元素的子集状态转移 DAG（忽略操作合法性）。
同一状态可从多条路径到达，如 $\{a_0\}$ 同时被 $\{a_0,a_1\}$ 和 $\{a_0,a_2\}$ 转移到。
用掩码标识状态后，每个状态只需计算一次。}
\label{fig:dag}
\end{figure}

解决方案：$n \le 20$，用一个 $n$ 位的\textbf{二进制掩码}（bitmask）表示
"哪些元素还在集合中"。共 $2^n$ 种状态，对每个状态记忆化搜索结果即可。

注意到轮到谁操作也不需要额外记录——已经删除了 $n - \texttt{popcount}(\mathit{mask})$
个元素，其奇偶性直接决定当前是左脑还是右脑。

\subsection{DFS 的设计：用一行表达极小极大}

博弈搜索的核心在于 \texttt{dfs(sta)} 的返回值定义和递归逻辑。
我们令 \texttt{dfs(sta)} 返回 $1$ 表示"当前操作者必胜"，$0$ 表示"当前操作者必败"。
则关键的一行代码为：

\begin{minted}{cpp}
res |= dfs(sta - (1ll << i)) ^ 1;
\end{minted}

这一行同时完成了两件事：

\begin{itemize}
	\item \textbf{视角翻转}（\texttt{\^{} 1}）：\texttt{dfs} 返回的是对手的胜负，
	      而我们关心的是"这步操作对\textbf{我}是否有利"。
	      对手必败（返回 $0$）意味着我必胜（$0 \oplus 1 = 1$）；
	      对手必胜（返回 $1$）意味着我必败（$1 \oplus 1 = 0$）。
	\item \textbf{存在性判定}（\texttt{|=}）：只要\textbf{存在}某个操作使对手进入必败态，
	      \texttt{res} 就被置为 $1$，此后不论其它操作结果如何都不会再变回 $0$。
	      这正是"必胜态 $\iff$ 存在至少一步使对手进入必败态"的直接编码。
\end{itemize}

若所有合法操作都找不到让对手必败的，\texttt{res} 保持初始值 $0$，即当前状态为必败态。
这也自然涵盖了"无合法操作"的情况（循环体不执行，直接返回 $0$）。

图~\ref{fig:dfs} 展示了这一过程：当前状态 $S$ 有三种合法操作，分别转移到 $S_1, S_2, S_3$。
递归返回的是\textbf{对手视角}下的胜负，经 \texttt{\^{} 1} 翻转为我方视角后，
再用 \texttt{|=} 汇总——只要有一个 $1$，当前状态就是必胜态。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[
	>=Stealth,
	wnode/.style={rectangle, rounded corners=4pt, draw, thick, fill=winc!15,
		minimum width=1.4cm, minimum height=0.7cm, align=center, font=\small},
	lnode/.style={rectangle, rounded corners=4pt, draw, thick, fill=leftc!15,
		minimum width=1.4cm, minimum height=0.7cm, align=center, font=\small},
	flipbox/.style={rectangle, rounded corners=2pt, draw, thick, dashed,
		fill=yellow!12, minimum width=0.9cm, minimum height=0.5cm, font=\small},
	orbox/.style={rectangle, rounded corners=4pt, draw=winc, very thick, fill=winc!8,
		minimum width=2.8cm, minimum height=0.7cm, font=\small},
]
	% 当前状态
	\node[wnode, minimum width=2.4cm, minimum height=0.9cm] (S) {状态 $S$\\[-1pt]{\scriptsize\texttt{res = ?}}};

	% 子状态
	\node[lnode, below left=2.0cm and 2.8cm of S] (S1) {$S_1$\\[-1pt]{\scriptsize 对手\textbf{必胜}}};
	\node[wnode, below=2.0cm of S]                (S2) {$S_2$\\[-1pt]{\scriptsize 对手\textbf{必败}}};
	\node[lnode, below right=2.0cm and 2.8cm of S] (S3) {$S_3$\\[-1pt]{\scriptsize 对手\textbf{必胜}}};

	% dfs 返回值标注
	\node[font=\scriptsize, below=0.15cm of S1] (r1) {返回 $1$};
	\node[font=\scriptsize, below=0.15cm of S2] (r2) {返回 $0$};
	\node[font=\scriptsize, below=0.15cm of S3] (r3) {返回 $1$};

	% 翻转框
	\node[flipbox, below left=0.8cm and 0.9cm of S] (f1) {$\oplus 1$};
	\node[flipbox, below=1.0cm of S]                (f2) {$\oplus 1$};
	\node[flipbox, below right=0.8cm and 0.9cm of S] (f3) {$\oplus 1$};

	% 翻转后值
	\node[font=\small\bfseries, text=leftc, left=0.15cm of f1] {$0$};
	\node[font=\small\bfseries, text=winc, left=0.15cm of f2] {$1$};
	\node[font=\small\bfseries, text=leftc, right=0.15cm of f3] {$0$};

	% 边：S -> 翻转框 -> 子状态
	\draw[->, thick] (S) -- node[above left, font=\scriptsize] {删 $a_i$} (f1);
	\draw[->, thick] (S) -- node[left, font=\scriptsize] {删 $a_j$} (f2);
	\draw[->, thick] (S) -- node[above right, font=\scriptsize] {删 $a_k$} (f3);
	\draw[->, thick, black!50] (f1) -- (S1);
	\draw[->, thick, black!50] (f2) -- (S2);
	\draw[->, thick, black!50] (f3) -- (S3);

	% |= 汇总箭头
	\draw[->, thick, winc, densely dashed] (f1.north) to[bend left=25] node[above, font=\scriptsize, text=black] {} (S.south west);
	\draw[->, thick, winc, densely dashed] (f2.north) -- (S.south);
	\draw[->, thick, winc, densely dashed] (f3.north) to[bend right=25] node[above, font=\scriptsize, text=black] {} (S.south east);

	% 结论
	\node[orbox, right=1.5cm of S] (result) {\texttt{res = 0\,|\,0\,|\,1\,|\,0 = \textbf{1}}};
	\draw[->, thick, winc] (S.east) -- (result.west);

	% 底部说明
	\node[font=\small, text=winc!70!black, below=3.6cm of S] {存在一条路使对手必败 $\Longrightarrow$ 当前状态为\textbf{必胜态}};
\end{tikzpicture}
\caption{\texttt{res |= dfs(...) \^{} 1} 的工作原理。递归返回对手视角的胜负，经 $\oplus 1$ 翻转为我方视角，再用 \texttt{|=} 汇总。只要有一个分支翻转后为 $1$，当前状态即为必胜。}
\label{fig:dfs}
\end{figure}

\subsection{完整算法流程}

对状态 $\mathit{mask}$，执行如下递归：

\begin{enumerate}
	\item 计算当前集合的异或和 $S = \bigoplus_{i:\, \mathit{mask} \text{ 的第 } i \text{ 位为 } 1} a_i$。
	\item 枚举 $\mathit{mask}$ 中每个为 $1$ 的位 $i$，若 $a_i > S \oplus a_i$，
	      则尝试删除 $a_i$，递归求解 $\mathit{mask} \setminus \{i\}$。
	\item 若存在某次删除使对手进入必败态（\texttt{res} 被 \texttt{|=} 置 $1$），
	      则当前状态为\textbf{必胜态}；否则为\textbf{必败态}。
	\item 将结果存入 $\texttt{memo}[\mathit{mask}]$ 以避免重复计算。
\end{enumerate}

\section{样例推演}

以样例 $2$（$\{2, 3, 6, 8\}$）为例，图~\ref{fig:game} 展示了完整的博弈过程。
由于每一步恰好只有一种合法操作，博弈路径是唯一确定的。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[
	>=Stealth,
	state/.style={rectangle, rounded corners=4pt, draw, thick,
		minimum width=2.8cm, minimum height=1.1cm, align=center, font=\small},
	every edge/.style={draw, ->, thick},
]
	% 节点
	\node[state, fill=leftc!12] (s0)
		{$\{2,3,6,8\}$\\[-1pt]{\scriptsize 异或和 $= 15$}};
	\node[state, fill=rightc!12, below=1.3cm of s0] (s1)
		{$\{2,3,6\}$\\[-1pt]{\scriptsize 异或和 $= 7$}};
	\node[state, fill=leftc!12, below=1.3cm of s1] (s2)
		{$\{2,3\}$\\[-1pt]{\scriptsize 异或和 $= 1$}};
	\node[state, fill=rightc!12, below=1.3cm of s2] (s3)
		{$\{2\}$\\[-1pt]{\scriptsize 异或和 $= 2$}};
	\node[state, fill=losec!30, below=1.3cm of s3] (s4)
		{$\varnothing$};

	% 边
	\draw[->] (s0) -- node[right, font=\small, text=leftc] {左脑删 $8$\;($8 > 15 \oplus 8 = 7$ \checkmark)} (s1);
	\draw[->] (s1) -- node[right, font=\small, text=rightc] {右脑删 $6$\;($6 > 7 \oplus 6 = 1$ \checkmark)} (s2);
	\draw[->] (s2) -- node[right, font=\small, text=leftc] {左脑删 $3$\;($3 > 1 \oplus 3 = 2$ \checkmark)} (s3);
	\draw[->] (s3) -- node[right, font=\small, text=rightc] {右脑删 $2$\;($2 > 0$ \checkmark)} (s4);

	% 结论
	\node[winc, font=\bfseries, right=0.5cm of s4] {右脑获胜！};

	% 图例
	\node[state, fill=leftc!12, minimum width=1.2cm, minimum height=0.5cm] at (5.5, 0) {\scriptsize 左脑回合};
	\node[state, fill=rightc!12, minimum width=1.2cm, minimum height=0.5cm] at (5.5, -0.8) {\scriptsize 右脑回合};
\end{tikzpicture}
\caption{样例 $2$（$\{2,3,6,8\}$）的博弈过程。每步只有唯一合法操作，共 $4$ 步，最后一步由右脑完成，右脑获胜。}
\label{fig:game}
\end{figure}

样例 $3$（$\{2, 2\}$）则更简单：当前异或和为 $2 \oplus 2 = 0$，
左脑若删去一个 $2$，剩余异或和为 $2$，不满足 $2 > 2$，
因此左脑\textbf{无法进行任何操作}，直接判负。

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：共 $2^n$ 个状态，每个状态枚举 $O(n)$ 个元素尝试转移，
	      总计 $O(2^n \cdot n)$。当 $n = 20$ 时约为 $2 \times 10^7$，可以通过。
	\item \textbf{空间复杂度}：$O(2^n)$ 用于存储记忆化数组。
\end{itemize}

\section{AC 代码}

\inputminted{cpp}{../src/1004_upsolve.cpp}

\end{document}

PDF

其实也没什么为什么需要记忆化搜索，进行状态压缩。

int dfs(ll sta) {
    if (memo[sta] != -1) {
        return memo[sta];
    }
    int res = 0;
    ll xorSum = 0;
    for (int i = 0; i <= __lg(sta); ++i) {
        if (sta >> i & 1) {
            xorSum ^= A[i];
        }
    }
    for (int i = 0; i <= __lg(sta); ++i) {
        if (sta >> i & 1) {
            if (A[i] > (xorSum ^ A[i])) {
                res |= dfs(sta - (1ll << i)) ^ 1;
            }
        }
    }
    memo[sta] = res;
    return memo[sta];
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1200&rid=13297

源代码

// teamname: Gospel_rock
/**
 * Problem: 左右脑互搏
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1200&pid=1004
 * Created: 2026-04-11 23:42:01
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N;
    vector<ll> A;
    vector<int> memo;

    int dfs(ll sta) {
        if (memo[sta] != -1) {
            return memo[sta];
        }
        int res = 0;
        ll xorSum = 0;
        for (int i = 0; i <= __lg(sta); ++i) {
            if (sta >> i & 1) {
                xorSum ^= A[i];
            }
        }
        for (int i = 0; i <= __lg(sta); ++i) {
            if (sta >> i & 1) {
                if (A[i] > (xorSum ^ A[i])) {
                    res |= dfs(sta - (1ll << i)) ^ 1;
                }
            }
        }
        memo[sta] = res;
        return memo[sta];
    }

    Solve() {
        cin >> N;
        A.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        memo.resize((1ll << N) + 4, -1);
        int res=dfs((1ll << N) - 1);
        if (res) {
            cout<<"Left\n";
        }else {
            cout<<"Right\n";
        }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve solve;
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1200&rid=13297

*/

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