Znzryb's Blog
0%

Posted on Edited on

题目大意

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

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

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

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
3
1
6
4
2 3 6 8
2
2 2

Output:
Left
Right
Right

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

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

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

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

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

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

思路讲解

PDF

image

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

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

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

Posted on Edited on

题目大意

题目描述
给定一个 n×mn \times m 的网格，每个格子 (i,j)(i, j) 中包含一个非负整数 ai,ja_{i, j}。
你需要从左上角 (1,1)(1, 1) 出发，经过上下左右四连通的合法移动，最终到达右下角 (n,m)(n, m)，移动过程中不能离开网格。
令 SS 表示路径上经过的所有格子中的整数构成的集合，mex(S)\text{mex}(S) 表示集合 SS 中未出现的最小非负整数。
求出所有从 (1,1)(1, 1) 到 (n,m)(n, m) 的路径中，可能得到的最小的 mex(S)\text{mex}(S) 值。

输入格式
第一行包含一个整数 TT（1≤T≤10001 \le T \le 1000），表示测试数据组数。
对于每组数据：
第一行包含两个整数 nn 和 mm（∑n≤2000\sum n \le 2000，∑m≤2000\sum m \le 2000）。
接下来 nn 行，每行 mm 个整数，表示网格中的数字 ai,ja_{i, j}（0≤ai,j≤1090 \le a_{i, j} \le 10^9）。

输出格式
对于每组测试数据，输出可能得到的最小的 mex(S)\text{mex}(S)。

样例输入

1
2
3
4
5
1
3 3
0 0 0
0 0 0
0 0 0

样例输出

1
1

样例解释
在此样例中，给定了 3×33 \times 3 的网格，且所有格子内的数字均为 0。无论布布选择哪一条从 (1,1)(1, 1) 走到 (3,3)(3, 3) 的合法路径，路径上经过的数字集合 SS 必然只包含元素 0，即 S={0}S = \{0\}。在集合 {0}\{0\} 中，未出现的最小非负整数是 1，因此可能得到的最小的 mex(S)\text{mex}(S) 为 1。

思路讲解

PDF

image

找出所有的这个值为 k 的屏障。

这个代码就是看哪些值是避无可避的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int y = 1; y <= M; ++y) {
    if (vis[1][y]) {
        continue;
    }
    vis[1][y] = 1;
    if (dfs(1, y,1,y)) {
        st.erase(maze[1][y]);
    }
}
for (int x = 1; x <= N; ++x) {
    if (vis[x][M]) {
        continue;
    }
    vis[x][M] = 1;
    if (dfs(x, M,x,M)) {
        st.erase(maze[x][M]);
    }
}

AC代码

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

Posted on Edited on

image

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
\section{错误六：答案计算缺少 $+\infty$ 守卫}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
ll lans = INF;
for (int num1 = 0; num1 < 2; ++num1) {
    if (d[num1][1] == INF) continue;
    ll val = d[num1][1] + 1;
    lans = min(lans, val);
}
// 缺少：if (lans == INF) continue;
ans += lans % mod * dp[status] % mod;
ans %= mod;
\end{minted}

\subsection*{错误分析}
当某个自动机状态 $D$ 的 $d_{01}$ 和 $d_{11}$ 均为 $+\infty$ 时，意味着落在该状态的子序列无法完成合法划分，其 $f$ 值为 $0$，不应对答案有任何贡献。

但如果缺少 \texttt{if (lans == INF) continue;}，\texttt{lans} 仍为初始值 \texttt{INF}（$= 2^{61} - 1$），这个巨大的数值会被乘以 \texttt{dp[status]} 后加入答案，导致结果完全错误。

\subsection*{修复}
\begin{minted}{cpp}
if (lans == INF) continue;   // f=0 的状态不贡献答案
\end{minted}

\subsection*{教训}
使用哨兵值（如 \texttt{INF}）初始化 \texttt{min} 变量时，计算结束后必须检查结果是否仍为哨兵值。如果是，说明没有任何有效候选，必须跳过后续计算，否则哨兵值会作为"正常数值"参与运算。

Posted on Edited on

https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=18676

https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=18673

image

image

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
\section{错误七（TLE）：循环内 \texttt{vector} 拷贝构造导致 $10^7$ 次堆分配}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < N; ++i) {
    ll ch = s[i] - '0';
    vector<ll> ndp = dp;   // 拷贝构造：每次都 new 一块内存
    for (int status = 0; status <= 45; ++status) {
        // ...
    }
    swap(ndp, dp);
}   // ndp 析构：每次都 delete 一块内存
\end{minted}

\subsection*{错误分析}
\texttt{vector<ll> ndp = dp;} 是拷贝构造，每次调用都会在堆上分配 $50 \times 8 = 400$ 字节的新内存，循环结束时 \texttt{ndp} 析构又将其释放。$N$ 最大为 $10^7$，因此总共触发 $10^7$ 次 \texttt{malloc} + $10^7$ 次 \texttt{free}，系统调用开销远超 DP 本身的计算量。

\subsection*{修复}
将 \texttt{ndp} 的声明提到循环外部，循环内用赋值代替构造：

\begin{minted}{cpp}
vector<ll> ndp;              // 提到循环外
for (int i = 0; i < N; ++i) {
    ll ch = s[i] - '0';
    ndp = dp;                // 赋值：size 相同时不会重新分配内存
    for (int status = 0; status <= 45; ++status) {
        // ...
    }
    dp.swap(ndp);            // O(1)，只交换内部指针
}
\end{minted}

Posted on Edited on

image

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
\section{错误三：BFS 建自动机时 \texttt{nxt} 表不完整}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < 2; ++i) {
    auto v = u.next_state(i);
    if (mp.contains(v)) {
        continue;   // 错误：跳过了，但没有记录转移边
    }
    mp[v] = idx;
    nxt[mp[u]][i] = idx;
    ++idx;
    q.push(v);
}
\end{minted}

\subsection*{错误分析}
当目标状态 \texttt{v} 已经在 BFS 中被访问过时，代码直接 \texttt{continue}，\textbf{没有设置 \texttt{nxt[mp[u]][i] = mp[v]}}。这导致所有"转移到已访问状态"的边全部留为初始值 $-1$。

自动机共 $40$ 个状态、$80$ 条有向边，但其中只有 $39$ 条（BFS 树边）被正确记录，剩下 $41$ 条（回边和交叉边）全部丢失。后续的子序列 DP 在遇到这些 $-1$ 的转移时会直接跳过，导致大量合法的子序列转移被忽略。

\subsection*{修复}
\begin{minted}{cpp}
 for (int i = 0; i < 2; ++i) {
    auto v = u.next_state(i);
    if (mp.contains(v)) {
        nxt[mp[u]][i] = mp[v];
        continue;
    }
    mp[v] = idx;
    idx_state[idx] = v;
    nxt[mp[u]][i] = idx;
    ++idx;
    q.push(v);
}
\end{minted}

\subsection*{教训}
BFS 建图时，"发现新节点"和"记录边"是两个独立的操作。即使目标节点已经在队列中，从当前节点到它的\textbf{转移边}仍然必须被记录。这是 BFS 建自动机的经典易错点。