Promising String (easy version)

发表于 更新于 分类于 ，

    给出一个只由+和-组成的字符串。 如果加号和减号的个数相同那么称之为平衡。

    一次操作可以将两个相邻的减号可以替换成一个加号，问这个字符串有多少子串在经过任意次操作后可以变为平衡？

Promising String (easy version)

Created by LXC on Mon May 1 13:17:21 2023

https://codeforces.com/problemset/problem/1660/F1

ranting: 1700

tag: brute force, implementation, math, strings

题意

给出一个只由+和-组成的字符串。 如果加号和减号的个数相同那么称之为平衡。

一次操作可以将两个相邻的减号可以替换成一个加号，问这个字符串有多少子串在经过任意次操作后可以变为平衡？

题解

双重for循环

维护区间内加号的个数a，减号的个数b。以及可以替换为加号的最多减号对数c。

如果经过k次操作加号和减号的个数都相同了，那么就有a+k=b-2k，即k=(b-a)/3

如果b-a>=0 且 b-a是3的倍数则可以通过操作变为相等，但是操作的次数不能操作c，k<=c。

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a = 0, b = 0, c = 0, t = 0;
        for (int j = i; j < n; j++) {
            if (s[j] == '+')
                a++, c += t / 2, t = 0;
            if (s[j] == '-')
                b++, t++;
            if (b >= a && (b - a) % 3 == 0 && (b - a) / 3 <= c + t / 2)
                ans++;
        }
    }
    cout << ans << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}