[THUPC 2024 决赛] 简单博弈

Luogu
IDLGP10549
Time2000ms
Memory512MB
DifficultyP5
2024THUPC
有 $k$ 个棋盘。每个棋盘大小为 $n\times m$ ,上面有 $3$ 个位置是 $0$,其他是 $1$。 现在 A 和 B 轮流操作,每次操作需要指定一个棋盘,在该棋盘上选定一行或者选定一列或者选定一行一列,将其全部变成 $0$。但是要保证操作前后棋盘至少一个格子数字变了。 不能操作就输了。问是否先手必胜。 ## Input 输入的第一行包含一个正整数 $k$ 表示棋盘总数,保证 $1 \le k \le 10^5$。 接下来 $k$ 组数据,第 $i$ 组数据共 4 行,描述第 $i$ 张棋盘的样子: * 第 1 行用空格隔开的两个正整数 $n,m$ 分别表示棋盘的行数和列数,保证 $1\le n,m \le 500$。 * 第 2-4 行,每行用空格隔开的两个正整数 $x,y$ 表示该棋盘上为 $0$ 的位置,保证互不相同且 $1\leq x\leq n, 1\leq y\leq m$ 。 ## Output 如果先手必胜,输出一个字符串 `OvO`,否则输出一个字符串 `QAQ`。 [samples] ## Note 一开始棋盘为: ``` 011 001 ``` 先手只需要选中第 1 行第 2 列即可全部清零,从而后手无法操作,先手获胜。 **来源与致谢** 来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>
Samples
Input #1
1
2 3
1 1
2 1
2 2
Output #1
OvO
Input #2
1
4 4
1 1
1 2
4 2
Output #2
QAQ
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2024 决赛] 简单博弈",
    "description": {
      "content": "有 $k$ 个棋盘。每个棋盘大小为 $n\\times m$ ,上面有 $3$ 个位置是 $0$,其他是 $1$。 现在 A 和 B 轮流操作,每次操作需要指定一个棋盘,在该棋盘上选定一行或者选定一列或者选定一行一列,将其全部变成 $0$。但是要保证操作前后棋盘至少一个格子数字变了。 不能操作就输了。问是否先手必胜。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10549"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $k$ 个棋盘。每个棋盘大小为 $n\\times m$ ,上面有 $3$ 个位置是 $0$,其他是 $1$。\n\n现在 A 和 B 轮流操作,每次操作需要指定一个棋盘,在该棋盘上选定一行或者选定一列或者选定一行一列,将其全部变成 $0$。但是要保证操作前后棋盘至少一个格子数字变了。\n\n不能操作就输了。问是否先手必胜。\n\n## Input\n\n输入的第一行包含一个正整数 $k$ 表示棋盘总数,保证 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments