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

小鱼儿 2024-03-23 22:09 46阅读 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 条评论，46人围观）

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

相关阅读

相关牛客练习赛109 B D

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关牛客练习赛1-B-树题解

文章目录题目描述输入描述输出描述输入输出备注算法分析解题代码 --

系统管理员/ 2022年12月28日 12:45/ 0 赞/ 137 阅读

相关牛客网----动态规划（python实现）

动态规划难不倒我一：股票（一次交易）：二：子数组的最大累加和：三：连续子数组的最大和：四：求路径：

我就是我/ 2022年10月23日 14:25/ 0 赞/ 185 阅读

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

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

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

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

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

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

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

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

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