【动态map】牛客挑战赛67 B

登录—专业IT笔试面试备考平台_牛客网

题意：

思路：

考虑动态的map

可以先定义一个状态，然后用map统计前缀这个状态的出现次数

在这里，定义{a,b}为cnt1 - cnt0和cnt2 - cnt0

当cnt0 和 cnt1都和cnt2相同时，统计贡献

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;
}