题解 P1114 【“非常男女”计划】
顾z
2018-09-02 21:00:11
题目描述：---> [P1114 “非常男女”计划](https://www.luogu.org/problemnew/show/P1114)
## 广告： [安利blog](https://www.luogu.org/blog/RPdreamer/#)
**题意概括：**
寻找一段最长的0和1的子序列,要求0和1的数量相同。
**分析：**
很明显,**前缀和问题**。
我们可以将代表女生的值改为-1,这样代表男生的值就是1,1与-1相加即为0,这样如果男生女生人数相同的话,前缀和就是0。
如果直接去写,最普通的写法 O(n^2)?
~~(复杂度不会证明QAQ~~
```cpp
/*60pts*/
for(RI i=1;i<=n;i++)
for(RI j=i+1;j<=n;j++)
{
if(sum[j]-sum[i-1]==0)
ans=std::max(ans,j-i+1);
}
```
很不幸,即使吸氧我们也只能能得到70pts.
**考虑如何优化**~~(看了一眼题解~~
存储某个值(前缀和的值)出现过的最左端位置.
再通过枚举去得到我们最长的连续序列,
以样例为例,我们会得到这样的一个前缀和序列↓
原序列:0 1 0 0 0 1 1 0 0
新序列:-1 0 -1 -2 -3 -2 -1 -2 -3
容易发现 我们的答案是7-1=6
可是如果这个值为负的怎么办?
**数组下标不支持负的**想必大家都知道.
**怎么办？**
提供解决方案:
1.一位会指针存储负下标的大佬%%%[@花_Q](https://www.luogu.org/space/show?uid=87940)
//你可以~~贿赂~~请教他.
2.把数组开的更大一些.
//感觉这个很现实吧~~
我们可以把数组开的更大一些
(由于懒得去判断,所以我直接开了好大的..
然后在读入的时候再存储一下这个值出现位置
(我们从左到右读入,得到的位置一定是最靠左的.
**记得取max！**
--------------------代码--------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define m 100008
#define clear(a) memset(a,0,sizeof a)
IL void read(int &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,sum[100008],ans,mp[m<<1];
int main()
{
read(n);
for(RI i=1,sex;i<=n;i++)
{
read(sex);
if(sex==0)sex=-1;//将女生的值改为-1,达到两两配对的效果.
sum[i]=sum[i-1]+sex;
if(!mp[sum[i]+m])mp[sum[i]+m]=i;//上面↑m足够大吧~
}
for(RI i=1;i<=n;i++)
ans=std::max(ans,sum[i]==0?i:0);
//printf("%d",ans);
for(RI i=1;i<=n;i++)
if(mp[sum[i]+m] and i!=mp[sum[i]+m])//这个and和&&是一样的
ans=std::max(ans,i-mp[sum[i]+m]);
printf("%d",ans);
}
```