首页 > 其他分享 >对于一个数字串,如何确定某段区间出现的数字是否都是偶数次

对于一个数字串,如何确定某段区间出现的数字是否都是偶数次

时间:2024-06-13 17:55:23浏览次数:24  
标签:那么 数字串 数字 某段 int 偶数 区间 string

本章对标:D - Three Days Ago
问题非常简单,也就是求出所有连续区间且这个区间内的数字都出现了偶数次的总合法区间数
那么很明显有中 \(O(n^2)\) 的算法,但复杂度不够,那么枚举区间不行,从别的方面入手,考虑到每个字符只能是数字,那么我们此时可以将其转化为一个二进制串,表示的含义就是,某个数字出现了偶数次还是奇数次,举个例子:12234445,那么其二进制串为:1011100000,因为我们的次数一定是递增的,也就是如果我们从 000000000 转化到 000000000,那么很明显这段区间就符合偶数次,也就是说只要出现了两次同样的,那么这段区间就符合,这样我们就可以用 \(map\) 来储存次数

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string s; cin>>s;
    int n=s.size();
    s=" "+s;
    map<string,int>mp;
    int res=0;
    string now="0000000000";
    mp[now]++;
    for(int i=1;i<=n;i++){
        if(now[s[i]-'0']=='1'){
            now[s[i]-'0']='0';
        }
        else now[s[i]-'0']='1';
        res+=mp[now],mp[now]++;
    }
    cout<<res;
    return 0;
}

标签:那么,数字串,数字,某段,int,偶数,区间,string
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18246445

相关文章

  • 【C语言】写一个宏,可以将一个整数的二进制位的奇数位和偶数位交换
    思路:10的二进制是00000000000000000000000000001010,然后交换奇数位和偶数位那么就是第一位和第二位交换,第三位和第四位交换,以此类推解题步骤:(1)将00000000000000000000000000001010的奇数位保留,偶数位变为0则变成00000000000000000000000000000000(2)将00000000000000000000......
  • Python(四)——基础控制流程语句:简单用户登录和输出10以内的奇偶数
    例子1:编写一小段代码,输入正确的账号和密码实现登陆操作。利用input函数判断用户名和密码是否正确,正确输出“欢迎您!“,用户名默认admin,密码默认为123代码实现:username=input("请输入用户名:")password=input("请输入密码:")ifusername=="admin":ifpassword=="123......
  • 2024-05-01:用go语言,给定两个长度为偶数n的整数数组nums1和nums2, 分别移除它们各自的一
    2024-05-01:用go语言,给定两个长度为偶数n的整数数组nums1和nums2,分别移除它们各自的一半元素,将剩下的元素合并成集合s。找出集合s中可能包含的最多元素数量。输入:nums1=[1,2,3,4,5,6],nums2=[2,3,2,3,2,3]。输出:5。答案2024-05-01:chatgpt题目来自leetcode3002。大体......
  • 监控某段时间特定进程CPU使用情况
    监控某段时间特定进程CPU使用情况背景之前一直想找一个进程级别的监控工具尤其是想能通过prometheus进行监控但是发现总是很不如人意node_exporter的监控只能看到整体的actuator的无法看到启动过程中的CPU使用情况.一直没有找到一个比较好的方式.之前一般采用top-Hp......
  • mac的cpu某段时间占用很高
    pmset-gsched,会发现如下所示:列出所有的计划事件wakepoweronat9:50AMeverydayScheduledpowerevents:[0]wakeat04/21/2401:38:54by'com.apple.alarm.user-visible-WeeklyUsageReport'[1]wakeat04/21/2405:37:09by'com.apple.alarm.user-visib......
  • Kafka 采用 RoundRobinPartitioner 时仅向偶数分区发送消息
    背景及问题说明使用Kafkaclient版本3.4.0目前的默认分区策略如下:NOTEthispartitionerisdeprecatedandshouldn'tbeused.Tousedefaultpartitioninglogicremovepartitioner.classconfigurationsetting.SeeKIP-794formoreinfo.Thedefaultpartitioni......
  • Golang交替打印奇偶数
    packagemainimport( "fmt" "sync")varwgsync.WaitGroupfuncmain(){ evenCh,oddCh:=make(chanbool,1),make(chanbool,1) deferclose(evenCh) deferclose(oddCh) wg=sync.WaitGroup{} wg.Add(1) goprintNumbersSequent......
  • 如何进行快速求解大数是否是11的倍数证明(如果奇数位数字和与偶数位数字和的差是11的倍
    当一个数的奇数位上数字和与偶数位上数字和的差是11的倍数时,这个数就是11的倍数。这个性质可以通过数学归纳法和模运算的性质来证明。观察模运算的性质首先,观察到对于任意正整数k,10^k对11取模的结果是循环的:......
  • C语言调整奇数偶数顺序
    输入一个整数数组,实现一个函数,来调整该数组中数字的顺序使得数组中所有的奇数位于数组的前半部分,所有偶数位于数组的后半部分。代码如下#include<stdio.h>voidFunction(int*p,intk){ int*left=p; int*right=p+k-1; while(left<right){ while(le......
  • linux中sed命令利用n;p选项输出奇数行、偶数行、或指定规则行
     001、输出偶数行[root@pc1test1]#lsa.txt[root@pc1test1]#cata.txt##测试文本0101020203030404050506060707080809091010[root@pc1test1]#sed-n'n;p'a.txt##输出偶数行02020404060608081010 002、输出......