链接：https://ac.nowcoder.com/acm/contest/883/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

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

A string  v v is a substring of a string  w w if  v v is empty, or there are two integers  l l and r (1≤l≤r≤|w|)r (1≤l≤r≤|w|) such that v=wlwl+1⋯wrv=wlwl+1⋯wr. A string  v v is a subsequence of a string  w w  if it can be derived from  w 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)N (1≤N≤100000), the length of the original string  T T. The second line contains a binary string with exactly  N N characters, the original string  T T.

输出描述:

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

示例1

输入

复制

8
01001001

输出

复制

4 6

题目大意:给你一段01序列让你找其中的最长的01子串和01子序列,子序列是可以拆开的,子串必须连续.

题目思路:

子序列好说01最小值,子串的话

两个思路 思路 :二分 && 枚举

二分:

为什么想到二分,sum[r]-sum[l-1],设l-1=x  即 sum[r]-sum[x] 所以如果该段连续就判断 sum[r]-sum[x]=(r-x)/2  然后我们可以根据 for循环 第一层 i从1 - n,第二层 k从1-i  然后想办法把第二层优化成二分 使其复杂度变成nlgn,这样一般需要控制一个变量枚举,另一个变量二分,我们观察 变量 l,x的关系,当满足要求时我们只需要找到sum[r]-sum[x]=(r-x)/2 所以 2sum[r]-r=2sum[x]-x  所以我们枚举 r,二分x,找到最小的x满足当前等式的x,求出长度即可:

AC代码:

/*
语言：C++ 代码长度：1402 运行时间： 27 ms 占用内存：3300K
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e5+8;
const double PI=acos(-1);
const ll mod=1000000007;
ll n,m;
int num[maxn];
ll cot1=0,cot0=0;
int s=1,e=1;
ll maxl=0;
ll sum[maxn];
struct node{
    ll val;
    int id;
}cop[maxn];
int biarysearch(ll res)
{
    int ans=-1;
    ll l=0,r=n;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(cop[mid].val<res)
            l=mid+1;
        else if(cop[mid].val>res)
            r=mid-1;
        else if(cop[mid].val==res)
        {
            r=mid-1;
            ans=mid;
        }
    }
    return ans;
}
bool cmp(node a,node b)
{
    if(a.val==b.val)
        return a.id<b.id;
    return a.val<b.val;
}
int main()
{
    ll cnt=0;
    scanf("%lld",&n);
    cop[0].val=0;
    cop[0].id=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%1d",&num[i]);
        if(num[i]==1) cot1++;
        else cot0++;
        sum[i]=sum[i-1]+num[i];
        cop[i].val=2*sum[i]-i;
        cop[i].id=i;
      //  printf("%lld\n",sum[i]);
    }
    sort(cop,cop+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        ll temp=2*sum[i]-i;
        int re=biarysearch(temp);
        if(re==-1) continue;
        else
        {
            ll temp1=i-cop[re].id;
            //printf("%lld\n",temp1);
            maxl=max(maxl,temp1);
        }
    }
    printf("%lld %lld\n",maxl,min(cot0,cot1)*2);
    return 0;
}

直接枚举O(N)

这个方法比赛的时候没用,后来一起比赛的兄弟告诉我的,当时过题用二分过,出题人说 没卡lg(感谢出题人哈哈哈)

我们设 0为-1,1为1  那么满足序列长度 0 1 数目相等的条件就是 sum[r]-sum[x]=0  即sum[r]=sum[x] 所以说从左到右 一遍O(n)就可以了,保留每一个不同sum权值第一次出现之后都与第一次做差就可以了.

为了防止前缀和出现负数无法标记,都+maxn即可,针对全是0的极限情况.

/*
 代码长度：717 运行时间： 17 ms 占用内存：1516K
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e13+5;
const int maxn=1e5+8;
const double PI=acos(-1);
const ll minl=999000000;
ll n,m;
int num[maxn];
int sum[maxn];
int vis[2*maxn];
int cot1=0,cot2=0;
int main()
{
    int maxl=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) {
    scanf("%1d",&num[i]);
    if(num[i]==0)num[i]=-1;
    if(num[i]==1) cot1++;
    else cot2++;
    }
    sum[0]=maxn;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+num[i];
        if(sum[i]==maxn) maxl=max(maxl,i);
        else if(vis[sum[i]]) maxl=max(maxl,i-vis[sum[i]]);
        else if(!vis[sum[i]]) vis[sum[i]]=i;
    }
    printf("%lld %lld\n",maxl,min(cot1,cot2)*2);
    return 0;
}

总结: 锻炼了思维,每次都能在比赛中进步!加油!