树状数组永远的概念神

#include <bits/stdc++.h>
#define int long long
#define pow_of_two(n) (n & -n == n) 
using namespace std;
typedef pair<int , int> PII;
const int N = 5e6 + 10;
int n;
int c[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x , int k)
{
    while (x <= n)
    {
        c[x] += k;
        x += lowbit(x);
    }
}

int query(int x)
{
    int res = 0;
    while (x)
    {
        res += c[x];
        x -= lowbit(x);
    }

    return res;
}

inline void solve()
{
    int t;
    cin >> t;
    int sb = 1;
    while (t -- )
    {
        cin >> n;
        string s;
        cin >> s;
        
        for (int i = 0 ; i < s.size() ; i ++  ) add(i + 1 , s[i] - '0');
        int ans = 0 , temp;
        if (n & 1) temp = n / 2 + 1;
        else temp = n / 2;

        // cout << temp << endl;

        for (int i = 1 ; i <= temp + 1 ; i ++ )
            ans = max(ans , query(i + temp - 1) - query(i - 1));
        // cout << endl;
        printf("Case #%lld: %lld\n" , sb ++ , ans);
        memset(c , 0 , sizeof c);
        // cout << ans << endl;
    }

}


signed main()
{
    ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    solve();
    return 0;
}

世界上最好的题解

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #define int long long

    using namespace std;
    const int N = 5e6 + 10;
    int a[N];
    inline void solve()
    {
        int t;
        cin >> t;
        int num = 1;
        while (t -- )
        {  
            
            int nx;
            cin >> nx;
            for (int i = 1 ; i <= nx ; i ++ )
            {
                char temp;
                cin >> temp;
                a[i] = temp - '0';
                a[i] = a[i - 1] + a[i];
            }

            int ans = 0;
            int n;
            if (nx & 1) n = nx + 1;
            else n = nx;
            for (int i = 1 ; i <= n / 2 ; i ++ )
            {
                int temp = a[i + n / 2 - 1] - a[i - 1];
                ans = max(ans , temp);

                // cout << temp << endl;
            }
            // if (num == 3) cout << ans << endl;
            for (int i = nx ; i >= nx / 2 ; i -- )
            {
                int temp = a[i] - a[i - nx / 2];
                ans = max(ans , temp);

                // cout << temp << endl;
            }


            cout << "Case #" << num << ": " << ans << endl;
            num ++;
        }
        return ;
    }

    signed main()
    {
        ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
        solve();
        return 0;
    }

参考答案：

#include<iostream>
#include<string>
using namespace std;
const int N = 5e6 + 10;
int a[N];
int T;
int main()
{
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        int n;
        int res = 0;
        cin >> n;
        string s;
        cin >> s;
        for (int i = 1; i <= n; ++i) a[i] = s[i - 1] - '0';
        for (int i = 1; i <= n; ++i) a[i] += a[i - 1];

        int len = (n + 1) / 2;
        for (int i = len; i <= n; ++i)
        {
            res = max(res, a[i] - a[i - len]);
        }
        if (s.size()) s.clear();
        printf("Case #%d: %d\n", t, res);
    }
    return 0;
}