登錄—專業(yè)IT筆試面試備考平臺_牛客網

題意：

思路：

考慮動態(tài)的map

可以先定義一個狀態(tài)，然后用map統(tǒng)計前綴這個狀態(tài)的出現(xiàn)次數(shù)

在這里，定義{a,b}為cnt1 - cnt0和cnt2 - cnt0

當cnt0 和 cnt1都和cnt2相同時，統(tǒng)計貢獻

Code：

#include <bits/stdc++.h>using i64 = long long;constexpr int N = 2e5 + 10;
constexpr int mod = 1e9 + 7;void solve() {int n;std::string s;std::cin >> n >> s;int a = 0, b = 0;std::map<std::array<int,2> ,i64> mp;mp[{0, 0}] = 1;i64 ans = 0;for (int i = 0; i < s.size(); i ++) {if (s[i] == '0') {a -= 1;b -= 1;}else if (s[i] == '1') {a += 1;}else {b += 1;}ans += mp[{a, b}];mp[{a, b}] ++;}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}