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 1∼len 的字符串，它想找到一个位置 x ( 1 ≤ x < l e n ) x(1≤x \lt len) x(1≤x<len)，使得 1 ∼ x 1 \sim x 1∼x中的 1 1 1的个数与 x + 1 ∼ l e n x+1 \sim len x+1∼len中的 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 len≤255；
60 % 60\% 60% 的数据： l e n ≤ 1000 len≤1000 len≤1000
100 % 100\% 100% 的数据： l e n ≤ 100000 len≤100000 len≤100000
思路： \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 1∼i的 1 1 1的个数为 j − s [ j ] j-s[j] j−s[j]
从 i + 1 ∼ n i+1 \sim n i+1∼n的 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;
}