P1114 【“非常男女”计划】

· · 题解

读题后可以发现，这题可以用前缀和。

因为男女配对，所以不妨使 男+女=0 ，也就是把女置为-1，男置为1。

然后我们可以用前缀和s[i]判断1~i是否为0，还有s[i]-s[j-1]就表示j~i是否完全配对。

想了想，我们的前缀和只有s[i]==s[j-1]时才更新ans，那为什么不把s[i]的值最早出现的位置记录下来呢？

因为这里每次+1或-1，所以值域为[-n,n]，加n后就是[0,2n]了！

然后桶记录下来就好了。

但是我懒得打桶，时间也不紧，用map就好了。

附上代码：

#include<cstdio>
#include<map>
using namespace std;
map<int,bool> bj;   //该值是否出现的标记
map<int,int> mp;    //最早出现的位置
int n,i,u,sum,ans;
inline int maxs(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    scanf("%d",&n);
    bj[0]=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&u);
        if(u==0)u=-1;
        sum+=u;         //与前面的前缀和无关了
                        //所以我们直接加上去
        if(bj[sum]==0)
        {
            bj[sum]=1;  //未出现记录第一次出现
            mp[sum]=i;
        }
        else
        ans=maxs(ans,i-mp[sum]);//出现则更新ans
    }
    printf("%d",ans);
    return 0;
}

补上桶的代码：

#include<cstdio>
#include<map>
using namespace std;
int mp[200010],bj[200010];
int n,i,u,sum,ans,x;
inline int maxs(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    scanf("%d",&n);
    bj[n]=1;                    //初始的0加上n
    for(i=1;i<=n;i++)
    {
        scanf("%d",&u);
        if(u==0)u=-1;
        sum+=u;
        x=sum+n;                //后面的前缀和也加上n
        if(bj[x]==0)
        {
            bj[x]=1;
            mp[x]=i;
        }
        else
        ans=maxs(ans,i-mp[x]);
    }
    printf("%d",ans);
    return 0;
}