1644 -- 字符串

发布于:2022-11-13 ⋅ 阅读:(322) ⋅ 点赞:(0)

Description

Smart \text{Smart} Smart 有一个只包含 0 , 10 , 1 0,10,1 0,10,1 的字符串,设这个字符串长度为 l e n len len,那么它是个下标为 1 ∼ l e n 1 \sim len 1len 的字符串,它想找到一个位置 x ( 1 ≤ x < l e n ) x(1≤x \lt len) x(1x<len),使得 1 ∼ x 1 \sim x 1x中的 1 1 1的个数与 x + 1 ∼ l e n x+1 \sim len x+1len中的 0 0 0 的个数相等,如果存在多个位置,则输出最小的。如果不存在一个合法的 x x x,则输出 l e n + 1 len+1 len+1

Input

一个字符串 s s s

Output

一个整数表示答案。

Sample Input

01100

Sample Output

3

Hint

40 % 40\% 40% 的数据: l e n ≤ 255 len≤255 len255
60 % 60\% 60% 的数据: l e n ≤ 1000 len≤1000 len1000
100 % 100\% 100% 的数据: l e n ≤ 100000 len≤100000 len100000

思路: \text {思路:} 思路:
肥肠煎蛋的前缀和。
l e n > 1 e 8 len >1e8 len>1e8就是另外一个故事了
a [ i ] = Σ j = 1 i s [ j ] = = 48 a[i] = \Sigma_{j=1}^is[j]==48 a[i]=Σj=1is[j]==48 (数字 0 0 0)
然后求答案。
1 ∼ i 1 \sim i 1i 1 1 1的个数为 j − s [ j ] j-s[j] js[j]
i + 1 ∼ n i+1 \sim n i+1n 0 0 0的个数为 s [ n ] − s [ i ] s[n]-s[i] s[n]s[i]
判断是否相等,相等则输出+ return 0; \text {return 0;} return 0;
循环完了都没找到,输出 n + 1 n+1 n+1
好吧 太简单了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long ll;
void read(int &x) {
	int k = 1, cnt = 0;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') k = -k;
		ch = getchar();
	}
	while (isdigit(ch)) {
		cnt = cnt * 10 + ch - '0';
		ch = getchar();
	}
	x = cnt * k;
}
void print(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x < 10) putchar(x + '0');
	else {
		print(x / 10);
		putchar(x % 10 + '0');
	}
}
char s[100010];
int n, sum[100010];
int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) {
		sum[i] = sum[i - 1] + (s[i] == '0' ? 1 : 0);
//		print(sum[i]);putchar(' ');
	}
	for (int i = 1; i < n; ++i) {
		if (i - sum[i] == sum[n] - sum[i]) {
			print(i);
			return 0;
		}
	}
	print(n + 1);
	return 0;
}


网站公告

今日签到

点亮在社区的每一天
去签到