首页 > 其他分享 >牛客挑战赛67 B数据结构

牛客挑战赛67 B数据结构

时间:2023-03-21 21:33:17浏览次数:52  
标签:int 67 个数 cin 牛客 1e6 挑战赛

牛客挑战赛67 B数据结构

你有一个长度为n的字符串,其中包含'0','1','2'三种字符。问字符串中有多少个字串满足'0','1','2'三种字符数量相等。 \(1 <= n <= 3e5\)

一开始想了一个暴力做法。

对于一个左端点来讲,符合条件的右端点的个数等于它右侧距离最近的,且这段区间符合条件的点的对应的个数+1

也就是满足\([i,j]\)是合法区间的最小的j对应的个数+1.

问题就成了怎么对于每一个i找到其对应的j。

从3开始枚举长度,而长度一定是3的倍数。

若当前区间不符合那么下一个可能符合的最小区间的长度是3 * max(Num[0] , Num[1] , Num[2]);

这个做法卡着牛客的TILE10连测。

正解是将‘0’,‘1’,‘2’三种字符转化成数字,然后判断前缀和。

首先先考虑分别转化成1,2,-3这样是否可行。

发现这样无法区分"0002"这种情况,仔细考虑一下发现是没法将个数这个信息表示出来。

那么将其转化成1 + 1e6 , 2 + 1e6 , -3 - 2e6

因为有了1e6这个大数,如果个数不符合的话一定是不能相等的,这样就解决了。

#include<iostream>
#include<map>
using namespace std;
int main()
{
    int T , n;
    long long t , res;
    char *s;
    map<long long , int> mp;
    cin >> T;
    while(T--)
    {
        cin >> n; s = new char [n + 5];
        cin >> (s+1);
        t = res = 0; mp[0] = 1;
        for(int i = 1 ; i <= n ; ++i)
        {
            if(s[i] == '0')
                t = t + 1 + 1e6;
            else
            if(s[i] == '1')
                t = t + 2 + 1e6;
            else
                t = t - 3 - 2e6;
            res += mp[t]; mp[t]++;
        }
        delete s; mp.clear();
        cout << res << '\n';
    }
    return 0;
}

标签:int,67,个数,cin,牛客,1e6,挑战赛
From: https://www.cnblogs.com/sybs5968QAQ/p/17241547.html

相关文章

  • 6.Java HotSpot(TM) 64-Bit Server VM warning: INFO: os::commit_memory(0x000000079
    这个问题引起的原因是:服务器上物理内存太小,大部分都是应为程序太多,内存吃紧,而给jvm分配的内存太大(java程序启动需要的内存,linux不能给),最好调整java程序jvm内存吧(测试环......
  • 67.Mysql的组复制
    Mysql的组复制(groupcommit)AnInnoDBoptimizationthatperformssomelow-levelI/Ooperations(logwrite)onceforasetofcommitoperations, rathertha......
  • 牛客练习赛100
    牛客练习赛100B.小红的子序列(dp)题目链接子序列问题一般是dp问题,这里结尾dp状态只有四种,蓝偶,红偶,蓝奇,红奇。对于当前物品,所要做的判断就是加与不加入状态完全相反的背......
  • 牛客项目——说说你是如何实现敏感词过滤的?
    面试官:说说你是如何实现敏感词过滤的?敏感词过滤我采用的是前缀树的数据结构,前缀树又叫字典树、查找树,它的根节点不存储信息,其他的每个节点只存储一个字符,有查找效率高的......
  • 启动vagrant up 报错 `await_response_state': scp: /tmp/vagrant-network-entry-eth1
      解决办法Linux df命令用于显示目前在Linux系统上的文件系统的磁盘使用情况统计。Linuxdu命令用于显示目录或文件的大小。du会显示指定的目录或文件所占用的磁盘......
  • MT6737 android 7.0 竖屏横用后u盘以及下载app无法打开
    问题描述:MT6737android7.0竖屏横用后u盘以及下载app无法打开问题的原因:下载APP的布局不支持横屏显示修改方法:diff--gita/frameworks/base/packages/DocumentsUI/Androi......
  • 狂神说的MyBatisPlus笔记 -https://blog.csdn.net/weixin_43070148/article/details/1
    狂神说的MyBatisPlus笔记https://blog.csdn.net/weixin_43070148/article/details/127313367学习MyBatis-Plus之前要先学MyBatis–>Spring—>SpringMVC为什么要学它?MyB......
  • 67、Rgb通道 和 Lab通道
    Lab通道与Rgb通道 的区别:1、Lab通道比Rgb通道的色域更广,所表现的颜色更加丰富2、Lab通道在调色面板中有很多都不能调整的;很多滤镜效果都用不了,不像Rgb那样可以调色,......
  • 牛客网手撕代码(31-58)
    31.数据累加输出题目实现串行输入数据累加输出,输入端输入8bit数据,每当模块接收到4个输入数据后,输出端输出4个接收到数据的累加结果。输入端和输出端与上下游的交互采......
  • LeetCode|1672. 最富有客户的资产总量
    题目链接:1672.最富有客户的资产总量难度简单173收藏分享切换为英文接收动态反馈给你一个mxn的整数网格accounts,其中accounts[i][j]是第i位客户在第j家银......