AT_agc069_b [AGC069B] Pair Guessing

题目描述

给定 $N$ 个长度为 $N$ 的 $01$ 字符串 $S_1,\ldots,S_N$。用 $S_{i,j}$ 表示 $S_i$ 的第 $j$ 个字符。保证存在至少一个整数对 $(i,j)$ 满足 $S_{i,j}=$1。

高桥君和青木君进行如下游戏：

1. 高桥君选择一个满足 $1\leq i,j\leq N$ 且 $S_{i,j}=$1 的整数对 $(i,j)$。
2. 青木君可以向高桥君提问 $0$ 到 $N$ 次。每次提问，青木君选择一个满足 $1\leq i',j'\leq N$ 的整数对 $(i',j')$，并询问“$i=i'$ 或 $j=j'$ 至少有一个成立”是否为真。高桥君会如实回答。
3. 青木君猜测 $(i,j)$。如果猜对，则青木君获胜，否则失败。

青木君在游戏开始前已知高桥君可能选择的 $(i,j)$，即已知 $S_1,\ldots,S_N$。在第 2 步中，青木君可以根据之前的回答选择新的 $(i',j')$。

请判断：无论高桥君如何选择 $(i,j)$，青木君是否总能通过合适的策略必胜。

对于每个输入，包含 $T$ 个测试用例。

输入格式

输入通过标准输入给出，格式如下：

$T$
$case_1$
$\vdots$
$case_T$

每个测试用例格式如下：

$N$
$S_1$
$\vdots$
$S_N$

输出格式

对于每个测试用例，如果青木君必胜则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3
2
01
11
2
11
11
10
0101011110
1100100001
1101100000
0111101010
1000011001
1110101010
1110110100
1110000110
0000001011
1001111100

输出 #1

Yes
No
Yes

说明/提示

限制条件

• $1\leq T\leq 2\times 10^5$
• $1\leq N\leq 500$
• 所有测试用例中 $N^2$ 的总和不超过 $500^2$
• $S_i$ 是长度为 $N$ 的 $01$ 字符串
• 至少存在一个 $(i,j)$ 使 $S_{i,j}=$1

样例解释 1

以下是第 1 个测试用例的游戏示例：

1. 高桥君选择 $(i,j)=(2,2)$，满足 $S_{i,j}=$1。
2. 青木君提问 2 次。第一次提问 $(i',j')=(1,1)$，高桥君回答“$i=1$ 或 $j=1$ 至少有一个成立”为假。第二次提问 $(i',j')=(2,2)$，高桥君回答“$i=2$ 或 $j=2$ 至少有一个成立”为真。
3. 青木君猜测 $(i,j)=(2,2)$，猜对，获胜。

这只是游戏的一个例子，不一定是最优策略。但只要青木君采取合适策略，总能获胜，因此第 1 个测试用例的输出为 Yes。

由 ChatGPT 4.1 翻译