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

小鱼儿 2024-03-23 22:09 70阅读 0赞

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

题意：

![4973e7ce1154472b86da1b267e7f26dc.png][]

思路：

考虑动态的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;
    }

[IT]: https://ac.nowcoder.com/acm/contest/51727/B
[4973e7ce1154472b86da1b267e7f26dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/426561d8992f4156b9905859cc08c9bb.png

发表评论取消回复

表情：

评论列表（有 0 条评论，70人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客练习赛109 B D

浅浅vp了一下 [牛客练习赛109\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][109_ACM_NOI_

﹏ヽ暗。殇╰゛Y/ 2024年03月26日 17:19/ 0 赞/ 92 阅读

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

[登录—专业IT笔试面试备考平台\_牛客网][IT] 题意： ![4973e7ce1154472b86da1b267e7f26dc.png][] 思路：考虑动态的ma

小鱼儿/ 2024年03月23日 22:09/ 0 赞/ 71 阅读

相关【牛客Wannafly挑战赛12】小H和圣诞树

[题目][Link 1] 可以考虑边分治，对于某一种颜色，我们处理出分治边左右两边所有以这个颜色为端点的路径长度，之后随便拼一拼就好了但是这样对于每一组询问都需要边分一遍

ゝ一纸荒年。/ 2023年10月11日 11:16/ 0 赞/ 54 阅读

相关【牛客挑战赛32E】树上逆序对

[题目][Link 1] 数据范围非常奇怪，询问的逆序对个数\\(k\\leq 30000\\)，我们应该可以把所有的情况都求出来发现对于树上两点\\(x,y\\)，如果

ゝ一世哀愁。/ 2023年10月11日 06:30/ 0 赞/ 64 阅读

相关 a+b【牛客】

输入两个十进制的a,b．输出a+b的十六进制表示… 链接：https://ac.nowcoder.com/acm/contest/31343/A 来源：牛客网输入描述

男娘i/ 2023年09月30日 11:41/ 0 赞/ 20 阅读

相关【Map与Set】之LeetCode&牛客练习

目录 1. 只出现一次的数字 2. 复制带随机指针的链表 3. 宝石与石头 4. 旧键盘 5. 前k个高频单词 -------------------- 1.

太过爱你忘了你带给我的痛/ 2023年09月28日 16:56/ 0 赞/ 75 阅读

相关牛客挑战赛37——牛牛与组合数数学（小白视角）

牛牛与组合数学（等效）做题心得在牛客里我已经不是第一次遇到求组合数了，但是由于组合数Cnm是好久之前学的，遇到题目时就懵了…… 具体格式：Cnm=n!/((n-

分手后的思念是犯贱/ 2023年07月07日 11:27/ 0 赞/ 23 阅读

相关 BSG白山极客挑战赛 B君的圆锥

[B君的圆锥][B] ![male.jpg][] [wwwwodddd][] (命题人) 基准时间限制：1 秒空间限制：131072 KB 分值: 40 B君要用一个

心已赠人/ 2022年08月22日 14:16/ 0 赞/ 149 阅读

相关牛客网 Wannafly挑战赛21 - B机器人

题目链接：[点我][Link 1] 链接：https://www.nowcoder.com/acm/contest/159/B 来源：牛客网从前在月球上有一个机器人

骑猪看日落/ 2022年05月17日 05:17/ 0 赞/ 206 阅读

相关牛客 Wannafly挑战赛24 A石子游戏(思维)

[题目链接][Link 1] 链接：[https://www.nowcoder.com/acm/contest/186/A][Link 1] 来源：牛客网 Alice

谁借莪１个温暖的怀抱￠/ 2021年09月16日 09:00/ 0 赞/ 352 阅读