题目理解

我们有一个长度为 $n$ 的路径，单元格可能是：

• '.'：空
• '@'：硬币
• '*'：荆棘

起点是第 $1$ 个单元格（下标从 $1$ 开始，代码中从 $0$ 开始），保证是 '.'。

移动规则：

• 每次可以走 $1$ 步 或 $2$ 步
• 目标单元格 不能是荆棘 '*'
• 走到硬币单元格自动捡起硬币

目标：从起点出发，按规则移动，最多能捡多少硬币。

---

核心思路

标程给出的思路非常巧妙，不需要复杂 DP：

尽量走 $1$ 步，如果下一步是荆棘，就走 $2$ 步；如果连续两步都是荆棘，则游戏结束。

为什么这样是对的？

1. 如果下一步 s[i] 不是荆棘，走 $1$ 步是最优的，因为：
   • 不会错过硬币
   • 不会浪费移动机会
2. 如果下一步 s[i] 是荆棘，必须走 $2$ 步（前提是 $s[i+1]$ 不是荆棘）。
3. 如果当前格子的下一步 s[i] 是荆棘，并且下两步 s[i+1] 也是荆棘，那么无论走 $1$ 步还是 $2$ 步都会踩到荆棘，游戏终止。

因此，游戏会在第一次遇到连续两个荆棘 "**" 时被迫结束。

---

算法步骤

1. 初始化 $ans = 0$。
2. 从 $i = 1$ 到 $n-1$ 遍历字符串（跳过起点 $i=0$）：
   • 如果 s[i] == '@'，$ans$ 加 $1$。
   • 如果 s[i] == '*' && s[i-1] == '*'，立即 结束循环。
3. 输出 $ans$。

---

为什么不需要显式模拟跳跃？

标程巧妙地没有模拟跳跃，而是直接遍历并统计硬币，直到遇到 "**"。

为什么这样可行？

• 因为只要没遇到 "**"，我们 总是有办法 走到当前位置。
• 我们走过的路径是：
  • 如果遇到荆棘，就跳 $2$ 步，此时当前遍历的 i 可能跳过一些格子，但硬币仍然被统计。
  • 实际上，遍历顺序不是实际跳跃顺序，但统计结果是等价的。

更严格地说：
从起点开始，实际跳跃路径中能到达的格子，就是 从位置 $1$ 开始，遇到 "**" 之前的所有 '@' 位置，因为：

• 只要不是两个荆棘连续，总可以通过适当选择 $1$ 步或 $2$ 步跳过去。
• 遇到 "**" 就无法继续。

因此，只需要统计 第一个 "**" 之前的所有 '@'。

---

时间复杂度

• 每个测试用例：$O(n)$
• $n \le 50$，$t \le 1000$，完全可行。

---

代码对应关系

for (int i = 1; i < n; i++) {
    ans += (s[i] == '@');
    if (s[i] == '*' && s[i - 1] == '*')
        break;
}

• i = 1 开始：从第二个格子开始判断
• ans += (s[i] == '@')：遇到硬币就计数
• if (s[i] == '*' && s[i-1] == '*') break;：遇到 "**" 结束

---

示例验证

示例 1

.@@*@.**@@

遍历：

• i=1: @ → ans=1
• i=2: @ → ans=2
• i=3: * → 不计数，且 s[2]='@', s[3]='*' 不是连续 **
• i=4: @ → ans=3
• i=5: . → ans=3
• i=6: * → 不计数，且 s[5]='.', s[6]='*' 不是 **
• i=7: * → 不计数，且 s[6]='', s[7]='' 是 ** → break 输出 $3$ ✅

示例 2

.@@@@

i=1..4 全是 @，无 ** → ans=4 ✅

示例 3

.@@..@***..@@@*

i=1: @ → 1
i=2: @ → 2
i=3: . → 2
i=4: . → 2
i=5: @ → 3
i=6: * → 3，且 s[5]='@', s[6]='' 不是 **
i=7: * → 3，且 s[6]='', s[7]='*' 是 ** → break
输出 $3$ ✅

---

总结

项目	说明
核心观察	遇到连续两个荆棘 "**" 就无法继续
算法	统计第一个 "**" 之前的所有 '@'
复杂度	$O(n)$ 每个测试用例
难度	CF 800 分 / 1–10 分制下约 1.5

#include <bits/stdc++.h>
 
using namespace std;
 
signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
 
    int t;
    cin >> t;
    for(int _ = 0; _ < t; ++_){
        int n, ans = 0;
        cin >> n;
        string s;
        cin >> s;
        for (int i = 1; i < n; i++) {
            ans += (s[i] == '@');
            if (s[i] == '*' && s[i - 1] == '*')
                break;
        }
        cout << ans << "\n";
    }
    return 0;
}