方圆游戏

题目描述

给定一个长度为 $n$ 的 0/1 串，0 表示圆、1 表示正方形。A、B 轮流操作（A 先手），每步任选两块图形（不必相邻），按规则替换：两块相同 → 正方形；两块不同 → 圆。重复直到只剩一块，若最后是圆则 A 胜，否则 B 胜。 $n \le 1000$ ， $T$ 组数据。

思路

设 $S$ 为当前串中 1 的个数。一次合并后 $S' \equiv S+1 \pmod 2$ ，即每合并一次奇偶必翻转，与选哪两块无关。 $n$ 个字符恰好合并 $n-1$ 次，末位图形的值被闭式 $v \equiv S_0+n-1 \pmod 2$ 唯一确定。因此 A 必胜当且仅当 $S_0+n-1$ 为偶数。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 20:41
# update_at: 2026-10-02 20:41

import sys


def a_wins(row: str) -> bool:
    """A 是否必胜：等价于最后一次合并后剩下的是圆(0)。

    记 S 为当前行里 1 的个数。合并 a、b 得到 a XNOR b，而
    a + b + (a XNOR b) ≡ 1 (mod 2)（因为 a+b 与 a XOR b 同奇偶），
    即每合并一次 S 的奇偶性翻转一次。长度为 len 的行恰好合并 len-1 次，
    结束后唯一剩下的图形值 ≡ S + len - 1 (mod 2)，与谁走、怎么选都无关。
    """
    squares = row.count('1')                       # 初始的 S
    last_is_circle = (squares + len(row) - 1) % 2 == 0  # 末位是圆 → A 胜
    return last_is_circle


def solve() -> None:
    data = iter(sys.stdin.read().split())
    T = int(next(data))                            # 组数
    print('\n'.join('Win' if a_wins(next(data)) else 'Lost' for _ in range(T)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:30
 * update_at: 2026-10-06 16:30
 */
#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;

char s[1005]; // 每组输入串，长度不超过 1000

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> s;
        int n = strlen(s);
        int cnt1 = 0; // 1 的个数
        for (int i = 0; i < n; ++i)
            if (s[i] == '1') ++cnt1;
        // 每合并一次 1 的个数奇偶翻转，合并 n-1 次后末位为圆当且仅当 cnt1 + n - 1 为偶数
        if ((cnt1 + n - 1) % 2 == 0)
            cout << "Win\n";
        else
            cout << "Lost\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码