【题解】牛牛大闯关

题意

给你个字符串，要求穿过这个字符串，初始能量为，当走到时，能量加一，反之能量减一，当能量小于时，回到初始原点，并且初始能量加一。问当穿过字符串时总的步数是多少。

题解

答案实际上就是每次回到原点的位置的累加和，那么我们只要知道什么时候会回到原点即可在的复杂度完成计数，当当前能量小于的时候我们不需要真的回到原点，因为每次回去的时候初始能量会加一，相当于我们可以从原点走到当前这个位置，且能量为0，开始闯关。当能量小于时答案加上所在的位置，然后能量变为0重新计数即可。

复杂度

时间复杂度

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
char s[N];
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%s", s+1);
        int n = strlen(s+1);
        long long ans = 0, sum = 0;
        for (int i = 1; i <= n;i++)
        {
            if (s[i] == '1')
                sum++;
            else
                sum--;
            if (sum < 0)
            {
                ans += i;
                sum=0;
            }
        }
        ans += n;
        printf("%lld\n",ans);
    }
    return 0;
}