51nod 1396 还是01串

布满荆棘的人生 2021-12-10 03:19 209阅读 0赞

给定一个0-1串s，长度为n，下标从0开始，求一个位置k，满足0<=k<=n, 并且子串s\[0..k - 1\]中的0的个数与子串s\[k..n - 1\]中1的个数相等。 注意：

（1） 如果k = 0, s\[0..k - 1\]视为空串

（2） 如果k = n, s\[k..n - 1\]视为空串

（3） 如果存在多个k值，输处任何一个都可以

（4） 如果不存在这样的k值，请输出-1

收起

# 输入 #

就一行，包含一个0-1串S，长度不超过1000000。

# 输出 #

题目要求的k值

# 输入样例 #

01

# 输出样例 #

1
    
    
    前缀和
    代码：

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    char s[1000001];
    int one[1000001];
    int zero[1000001];
    int k = -1;
    int main() {
        scanf("%s",s);
        int len = strlen(s);
        for(int i = 0;i < len;i ++) {
            if(s[i] == '0') zero[i + 1] = zero[i] + 1;
            else zero[i + 1] = zero[i];
            if(s[len - i - 1] == '1') one[len - i] = one[len - i + 1] + 1;
            else one[len - i] = one[len - i + 1];
        }
        for(int i = 1;i <= len + 1;i ++) {
            if(zero[i - 1] == one[i]) {
                k = i - 1;
                break;
            }
        }
        printf("%d",k);
    }

转载于:https://www.cnblogs.com/8023spz/p/10879620.html

发表评论取消回复

表情：

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

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

相关阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 250 阅读

相关 51nod 1007 正整数分组（类01背包问题）

将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。这道题就是要

Love The Way You Lie/ 2022年08月20日 12:29/ 0 赞/ 150 阅读

相关 51nod 1101 找零问题 dp （01背包问题）

N元钱换为零钱，有多少不同的换法？币值包括1 2 5分，1 2 5角，1 2 5 10 20 50 100元。例如：5分钱换为零钱，有以下4种换法： 1、5个1分 2、

小鱼儿/ 2022年08月20日 12:22/ 0 赞/ 184 阅读

相关 51nod 1085 01背包模板

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。

我就是我/ 2022年08月19日 15:19/ 0 赞/ 212 阅读

相关 51nod 1154回文串划分 dp+递推

题意：有一个字符串S，求S最少可以被划分为多少个回文串。例如：abbaabaa，有多种划分方式。 a|bb|aabaa - 3 个回文串 a|bb|a|a

男娘i/ 2022年08月19日 15:18/ 0 赞/ 168 阅读

相关 51nod1432 贪心

上船问题。排序之后枚举最大重量就可以了。 include <map> include <queue> include <sta

谁践踏了优雅/ 2022年07月29日 08:58/ 0 赞/ 219 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 251 阅读

相关 51nod-1770

为该问题添加一个话题隐藏话题 [1770 数数字][1770] 基准时间限制：1 秒空间限制：262144 KB 分值: 20 [难度：3级算法题][3] ![s

小灰灰/ 2022年05月28日 12:51/ 0 赞/ 222 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 231 阅读

相关 51nod 1396 还是01串

给定一个0-1串s，长度为n，下标从0开始，求一个位置k，满足0<=k<=n, 并且子串s\[0..k - 1\]中的0的个数与子串s\[k..n - 1\]中1的个数相等。

布满荆棘的人生/ 2021年12月10日 03:19/ 0 赞/ 210 阅读