B. 是否为正方形 - 详细题解

问题重述

给定一个二进制字符串 $s$，它是由一个美丽的二进制矩阵（边缘全为 $1$，内部全为 $0$）按行展开得到的。判断这个矩阵是否可能是正方形矩阵（即行数等于列数）。

---

美丽矩阵的性质

一个大小为 $r \times c$ 的美丽矩阵具有以下结构：

• 第一行全部为 $1$
• 最后一行全部为 $1$
• 第一列全部为 $1$
• 最后一列全部为 $1$
• 内部（除去边缘）全部为 $0$

例如，一个 $3 \times 3$ 的美丽矩阵为：

$$\begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} $$

---

关键观察

观察 1：矩阵按行展开

字符串 $s$ 是通过逐行连接矩阵的所有行得到的。因此：

• 前 $c$ 个字符对应第 $1$ 行
• 第 $c+1$ 到 $2c$ 个字符对应第 $2$ 行
• 以此类推

观察 2：$r \le 2$ 或 $c \le 2$ 的情况

当行数 $r \le 2$ 或列数 $c \le 2$ 时，矩阵没有内部区域（因为边缘覆盖了整个矩阵）。此时，整个矩阵全为 $1$，字符串也全为 $1$。

结论：若字符串全为 $1$，则只有当 $n = 4$（即 $r = c = 2$）时，矩阵才是正方形。因为：

• $r = 1, c = 1$：$n = 1$，但题目保证 $n \ge 2$，不可能
• $r = 1, c = 2$：$n = 2$，但 $2 \times 1$ 不是正方形
• $r = 2, c = 2$：$n = 4$，是正方形 ✓
• $r = 2, c = 3$：$n = 6$，但 $2 \times 3$ 不是正方形

---

观察 3：存在 $0$ 的情况

如果字符串中存在 $0$，设第一个 $0$ 出现在位置 $id$（从 $0$ 开始索引）。

由于美丽矩阵的第一行全是 $1$，第一列也全是 $1$，第一个 $0$ 只能出现在第 $2$ 行第 $2$ 列的位置（即矩阵内部）。

分析索引关系：

• 第 $1$ 行有 $c$ 个 $1$，对应字符串的索引 $0$ 到 $c-1$
• 第 $2$ 行的第一个字符（第 $2$ 行第 $1$ 列）也是 $1$（因为第一列全是 $1$）
• 所以第 $2$ 行第 $2$ 列是第一个可能为 $0$ 的位置

因此，第一个 $0$ 在字符串中的索引为：

$$id = c + 1$$

其中 $c$ 是矩阵的列数。

---

观察 4：由 $id$ 确定 $r$ 和 $c$

由 $id = c + 1$ 可得：

$$c = id - 1$$

由于矩阵是正方形的，有 $r = c$，所以：

$$r = id - 1$$

矩阵的总元素个数为：

$$n = r \times c = (id - 1) \times (id - 1) = (id - 1)^2 $$

结论：若字符串中存在 $0$，则原矩阵是正方形的充要条件是：

$$n = (id - 1)^2$$

其中 $id$ 是第一个 $0$ 的位置（从 $0$ 开始计数）。

---

算法步骤

1. 读入字符串长度 $n$ 和字符串 $s$
2. 找到第一个 $0$ 的位置 $id$（从 $0$ 开始）
3. 情况 1：$id = n$（字符串全为 $1$）
   • 若 $n = 4$，输出 "Yes"
   • 否则输出 "No"
4. 情况 2：$id < n$（字符串存在 $0$）
   • 计算 $r = id - 1$
   • 若 $r \times r = n$，输出 "Yes"
   • 否则输出 "No"

---

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        
        // 找到第一个 '0' 的位置
        int id = 0;
        while (id < n && s[id] == '1') {
            id++;
        }
        
        // 情况1：全为 '1'
        if (id == n) {
            if (n == 4) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        } 
        // 情况2：存在 '0'
        else {
            int r = id - 1;  // 正方形的边长
            if (r * r == n) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    
    return 0;
}

---

时间复杂度

• 每次查找第一个 $0$：$O(n)$
• 总复杂度：$O(\sum n) \le 2 \times 10^5$

---

示例验证

测试	$n$	$s$	$id$	情况	条件	输出
1	2	11	2（全1）	全1	$n=2 \ne 4$	No
2	4	1111	4（全1）		$n=4$	Yes
3	9	111101111	4	有0	$r=3, 3^2=9$
4		111111111	9（全1）	全1	$n=9 \ne 4$	No
5	12	111110011111	5	有0	$r=4, 4^2=16 \ne 12$

与样例输出完全一致。