NowCoder Crazy Binary String

题目描述

链接:https://ac.nowcoder.com/acm/contest/883/B

ZYB loves binary strings (strings that only contains 0 and1’). And he loves equal binary strings more, where the number of 0and the number of 1 in the string are equal.

ZYB wants to choose a substring from an original string T so that it is an equal binary stringwith the longest length possible. He also wants to choose a subsequence of T which meets the same requirements.

A string v is a substring of a string w if v is empty, or there are two integers l and r (1≤l≤r≤∣w∣) such that v=wl*wl+1 ⋯wr A string v is a subsequence of a string w if it can be derived from w by deleting any number (including zero) of characters without changing the order of the remaining characters.

For simplicity, you only need to output the maximum possible length. Note that the empty string is both a substring and a subsequence of any string.

输入描述

The first line of the input contains a single integer N (1≤N≤100000),the length of the original string T. The second line contains a binary string with exactly N characters, the original string T

输出描述

Print two integers A and B, denoting the answer for substring and subsequence respectively.

示例输入

8

0100101001

示例输出

4 6

分析这道题目的时候,10^5用N^2的时间复杂度跑一遍肯定会TLE,这时候考虑对前缀和的剪枝操作。

Solve A:map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
map<int,int>k;
int max(int x,int y){
if(x>=y){
return x;
}else{
return y;
}
}
int min(int x,int y){
if(x>=y){
return y;
}return x;
}
int main(){
int a=0,b=0;
int n;
int maxn=0;
cin>>n;
k[0]=0;
char s;
for(int i=1;i<=n;i++){
cin>>s;
if(s=='1'){
a++;
}else{
b++;
}
if(k.find(a-b)==k.end()){
k[a-b]=i;
}else{
maxn=max(maxn,i-k[a-b]);
}

}
cout<<maxn<<" "<<min(a,b)*2;

}

Solve B:前缀和

贯彻数学思想的前缀和…这种简单的做法基本换汤不换药,记得归纳总结。

设s1[i]为前i项0的个数,s2[i]为前i项1的个数,所以[i,j]范围内有0 s1[j]-s1[i-1]个,1 s2[j]-s2[i-1]个。

列出方程式

s1[j]-s1[i-1] = s2[j]-s2[i-1]

移项得

s1[j]-s2[j] = s1[i-1] - s2[i-1]

设x[i] = s1[i] - s2[i]

得到当x[j] = x[i-1] 时 满足情况。

写一个结构体,重新排序一下,然后取 x[j]=x[i-1] 的情况即可(此方法适用于各种前缀和N^2 TLE 求子串含有相同字符的时候)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<iostream>
#include<algorithm>
const int N = 200005;
typedef long long ll;
using namespace std;
ll ans=0;
struct node{
int x,id;
}a[N];
char ch;
bool cmp(node a,node b){
return a.x<b.x || (a.x==b.x&&a.id<b.id);
}
ll maxx(ll xx,ll yy){
if(xx>yy){
return xx;
}return yy;
}ll minn(ll xx,ll yy){
if(xx>yy){
return yy;
}return xx;
}
int main(){
int n;
cin>>n;
ll zero=0,one=0;
for(int i=1;i<=n;i++){
cin>>ch;
a[i].id=i;
if(ch=='0'){
a[i].x=a[i-1].x+1;
zero++;
}else{
a[i].x=a[i-1].x-1;
one++;
}

}

sort(a,a+n+1,cmp);


int t=a[0].id;
for(ll i=1;i<=n;i++){
if(a[i].x==a[i-1].x) ans=maxx(ans,a[i].id-t);
else t=a[i].id;
}

cout<<ans<<" "<<2*minn(zero,one)<<endl;
return 0;
}