A. 阿廖娜与方形拼图 详细题解

问题描述

阿廖娜拼图：第一天放中心块（$1$ 块），之后每天按顺时针方向添加若干块，总是完整地完成当前层再开始下一层。每天结束后，如果已经拼出的部分是一个完整的正方形（即边长是奇数的完美正方形），则她当天是“高兴”的。给定每天添加的块数，求高兴的天数。

---

核心观察

拼图从中心开始向外逐层构建。第 $1$ 层（中心）有 $1$ 块，边长为 $1$（$1=1^2$，$1$ 是奇数）。
第 $2$ 层（围绕中心的第一圈）需要 $8$ 块，加上中心共 $1+8=9=3^2$。
第 $3$ 层需要 $16$ 块，累计 $1+8+16=25=5^2$。
一般地，第 $m$ 层（$m\ge 1$）需要的块数为：

• $m=1$ 时：$1$ 块；
• $m\ge 2$ 时：第 $m$ 层边框的块数为 $8(m-1)$。

因此，完成前 $m$ 层后的总块数为：

$$\begin{aligned} S(m) &= 1 + \sum_{i=2}^{m} 8(i-1) \\ &= 1 + 8 \cdot \frac{(m-1)m}{2} \\ &= 1 + 4m(m-1) \\ &= (2m-1)^2. \end{aligned} $$

恰好是奇数的平方。
反之，若当前总块数是某个奇数的平方，则一定恰好完成了完整的若干层。

结论：阿廖娜在第 $i$ 天结束时高兴 当且仅当 到当天为止累计的总块数是某个奇数的平方。

---

算法步骤

1. 预处理所有不超过可能最大总块数的奇数平方数。
   由于 $n \le 100$，每天最多 $100$ 块，总块数 $\le 10000$。但为了安全，可以计算到 $100\times 1000$（标程取到 $100000$）。
   对于 $k=1,3,5,\dots$，计算 $k^2$ 并存入集合。
2. 初始化当前总块数 cur = 0，答案 ans = 0。
3. 遍历每一天的块数 $a_i$：
   • cur += a_i
   • 如果 cur 在奇数平方集合中，则 ans++
4. 输出 ans。

---

复杂度

• 预处理 $O(\sqrt{\text{MAX}})$，$\text{MAX}$ 取 $10^5$ 时约 $316$ 次。
• 每个测试用例 $O(n)$，$n \le 100$，$t \le 500$，总复杂度 $O(5\times 10^4)$，非常快。

---

代码（标程原版，Python，提交时请上交c++代码）

NT = int(input())

sqs = set()
k = 1
while k * k <= 100 * 1000:
    sqs.add(k * k)
    k += 2

for _ in range(NT):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    cur = 0
    for x in a:
        cur += x
        if cur in sqs:
            ans += 1
    print(ans)

---

示例验证

以样例第三组 1 3 2 1 2 为例：

• 第1天：cur=1（奇数平方 $1^2$）→ 高兴
• 第2天：cur=4（不是奇数平方）→ 不高兴
• 第3天：cur=6（不是）→ 不高兴
• 第4天：cur=7（不是）→ 不高兴
• 第5天：cur=9（$3^2$）→ 高兴 共 $2$ 天，与输出一致。