AtCoder Beginner Contest 098

前缀和场

C

直接做一个前缀和即可a。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// LUOGU_RID: 174637747
#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 1e5 + 10;
char c[N];
int n;
int E[N], W[N], ans = 0x3f3f3f3f;
int main()
{
    scanf("%d%s", &n, c + 1);
    for (int i = 1; i <= n; i++)
        E[i] = E[i - 1] + (c[i] == 'E');
    for (int i = n; i >= 1; i--)
        W[i] = W[i + 1] + (c[i] == 'W');
    for (int i = 1; i <= n; i++)
        ans = min(ans, n - E[i] - W[i]);
    cout << ans;
    return 0;
}

D

双指针法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// LUOGU_RID: 174639196
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3 * 1e5 + 10;
ll a[N];
ll suma[N], sumb[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        suma[i] = suma[i - 1] + a[i];
        sumb[i] = sumb[i - 1] ^ a[i];
    }
    ll ans = 0;
    int i = 1;
    for (int j = 1; j <= n; j++)
    {
        while ((suma[j] - suma[i - 1]) != (sumb[j] ^ sumb[i - 1]))
        {
            i++;
        }
        ans += j - i + 1;
    }
    cout << ans << endl;
    return 0;
}