85 条题解
-
2
猫粮寸断 LV 10 @ 2017-11-08 15:40:19
维护一个前缀和，遇到男生加一，遇到女生减一，最后前缀和相等的两个数中间一段男女人数相同，防止出现负数要先设一个大值，开大数组暴力找。
#include<iostream> using namespace std; int q[100010],num[200010][2],pan[200010]; int main() { int n,i,a,ans=0; cin>>n; pan[100000]=1; q[0]=100000; for(i=1;i<=n;i++) { cin>>a; if(a) q[i]=q[i-1]+1; else q[i]=q[i-1]-1; if(!pan[q[i]]) { num[q[i]][0]=i; pan[q[i]]=1; } else num[q[i]][1]=i; } for(i=0;i<=200000;i++) ans=max(ans,num[i][1]-num[i][0]); cout<<ans; return 0; } -
1
Sky1231 (sky1231) LV 10 @ 2020-10-25 11:28:28
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; namespace dts { const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,ans,a[100000],sum[100000]; int sub[200001][2]; #define submin(x) sub[(x)+100000][0] #define submax(x) sub[(x)+100000][1] void main() { scanf("%d",&n); for (int i=0;i<n;i++) { scanf("%d",&a[i]); if (a[i]==0) a[i]=-1; } sum[0]=a[0]; for (int i=1;i<n;i++) sum[i]=sum[i-1]+a[i]; memset(sub,oo_min,sizeof(sub)); submin(0)=-1; for (int i=0;i<n;i++) { if (submin(sum[i])==oo_min) submin(sum[i])=i; submax(sum[i])=i; } ans=0; for (int i=0;i<n;i++) ans=max(ans,submax(sum[i])-submin(sum[i])); printf("%d\n",ans); } } int main() { dts::main(); } -
1
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,maxn=0,a[200017],b[200017];
int main()
{
//freopen("brick.in","r",stdin);
//freopen("brick.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]) a[i]=a[i-1]+1;
else a[i]=a[i-1]-1;
}//记录相同点的位置
memset(b,-1,sizeof(b));
for(int i=0;i<=n;i++)
{
if(b[a[i]+n]!=-1)//相同就减去上一个
maxn=max(maxn,i-b[a[i]+n]);
else b[a[i]+n]=i;//更新
}
cout<<maxn<<endl;
//fclose(stdin);fclose(stdout);
return 0;
} -
1
数据点水了点，没想到思路，暴力也过了。
#include <iostream>
#include <stdio.h>using namespace std;
#define MAX 100000
short a[MAX];
int s[2];
int main()
{
int n; scanf("%d",&n); getchar();
int girl = 0, boy = 0;
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
s[a[i]]++;
}
int len = n;
int oldb = s[1], oldg = s[0];
do {
if(s[0] == s[1]) {
cout << s[0] + s[1]; return 0;
}
for(int i=len;i<n;i++) {
s[a[i-len]]--;
s[a[i]]++;
if(s[0] == s[1]) {
cout << s[0] + s[1]; return 0;
}
}len--;
if(len <= 1) break;
if(a[len] == 0) oldg--;
else oldb--;s[0] = oldg;
s[1] = oldb;
} while(true);cout << "0";
return 0;
} -
0
#include<iostream>
using namespace std;
int q[100010],num[200010][2],pan[200010];
int main()
{
int n,i,a,ans=0;
cin>>n;
pan[100000]=1;
q[0]=100000;
for(i=1;i<=n;i++)
{
cin>>a;
if(a)
q[i]=q[i-1]+1;
else
q[i]=q[i-1]-1;
if(!pan[q[i]])
{
num[q[i]][0]=i;
pan[q[i]]=1;
}
else
num[q[i]][1]=i;
}
for(i=0;i<=200000;i++)
ans=max(ans,num[i][1]-num[i][0]);
cout<<ans;
return 0;
} -
0
好像和动态规划没有关系……
```c++
#include<cstdio>
#include<map>
#include<vector>
using namespace std;int n,ans=0;
vector<int> s;
map<int,int> look_up;int main()
{
scanf("%d",&n);
s.push_back(0);
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
if(k) s.push_back(s[i-1]+1);
else s.push_back(s[i-1]-1);
}
for(int i=0;i<=n;i++)
{
if(look_up.count(s[i])) ans=max(ans,i-look_up[s[i]]);
else look_up[s[i]]=i;
}
printf("%d\n",ans);
return 0;
}
``` -
0
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000000+10;
int Ans,n,s[N],p[N*2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&s[i]);
if(s[i]) s[i]=s[i-1]+1;
else s[i]=s[i-1]-1;
}
memset(p,-1,sizeof(p));
for(int i=0;i<=n;++i){
if(p[s[i]+n]!=-1){
Ans = max(Ans,i-p[s[i]+n]);
}else{
p[s[i]+n]=i;
}
}
printf("%d\n",Ans);
return 0;
} -
0
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1000000+10;
int Ans,n,s[N],p[N*2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&s[i]);
if(s[i]) s[i]=s[i-1]+1;
else s[i]=s[i-1]-1;
}
memset(p,-1,sizeof(p));
for(int i=0;i<=n;++i){
if(p[s[i]+n]!=-1){
Ans = max(Ans,i-p[s[i]+n]);
}else{
p[s[i]+n]=i;
}
}
printf("%d\n",Ans);
return 0;
} -
0
#include <iostream> using namespace std; const int MAXN = 100000 + 5; int sex[MAXN], sum[MAXN] = {0}, ans = 0, n, h1[MAXN], h2[MAXN]; int pos(int x) { if (x >= 0) return h1[x]; else return h2[-x]; } void ins(int val, int pos) { if (val >= 0) h1[val] = pos; else h2[-val] = pos; } int main() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> sex[i]; h1[i] = MAXN; h2[i] = MAXN; if (sex[i] == 0) sex[i] = -1; } sex[0] = 0; sum[0] = 0; h1[0] = 0; h2[0] = 0; for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + sex[i]; if (pos(sum[i]) == MAXN) ins(sum[i], i); else ans = max(ans, i - pos(sum[i])); } cout << ans << endl; return 0; } //女的都设置成-1； //用哈希表pos()寻找前序和为x的，维护最大值就好。 -
0
记录信息
评测状态 Accepted
题目 P1195 “非常男女”计划
递交时间 2015-08-08 17:26:58
代码语言 C++
评测机 VijosEx
消耗时间 1105 ms
消耗内存 1692 KiB
评测时间 2015-08-08 17:27:00
评测结果
编译成功测试数据 #0: Accepted, time = 15 ms, mem = 1688 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1692 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1688 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1692 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1692 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 1688 KiB, score = 10
测试数据 #6: Accepted, time = 906 ms, mem = 1692 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 1688 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 1692 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1688 KiB, score = 10
Accepted, time = 1105 ms, mem = 1692 KiB, score = 100
代码
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int wm[100010];
int man[100010],wom[100010];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&wm[i]);
int m=0,w=0;
for(int i=1;i<=n;i++)
{
if(wm[i]==1)
m++;
else
w++;
man[i]=m;
wom[i]=w;
}
int ans=0;
for(int i=n;i>=ans;i--)
for(int j=0;j<i-ans;j++)
{
if(man[i]-man[j]==wom[i]-wom[j])
ans=max(ans,2*(man[i]-man[j]));
}
printf("%d",ans);
} -
0
超时的：
var n,max,s,i,j,m:longint;a:array[0..100000]of longint;
begin
readln(n);max:=0;
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
begin
m:=0;s:=0;
for j:=i to n dobegin
if a[j]=1 then inc(s) else dec(s);
if s=0 then m:=j-i+1;end;
if m>max then max:=m;
end;
writeln(max);
end.
-
0
jiaoyunhao LV 10 @ 2012-08-10 23:27:12
var
n,i,j,tot,max:longint;
a:array[1..100000] of integer;
ans:array[-100000..100000] of longint;begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do
begin
if a[i]=1 then inc(tot);
if ans[2*tot-i]=0 then ans[2*tot-i]:=i else
if i-ans[2*tot-i]>max then max:=i-ans[2*tot-i];
if (i=tot*2) and (i>max) then max:=i;
end;
writeln(max);
end. -
0
1054391275 LV 8 @ 2012-07-17 12:23:04
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
注意，此题一定要用动态规划！ -
0
prince_hao LV 10 @ 2009-10-30 17:54:36
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms太水了
-
0
program p1195(input,output);
var n,i,j,k,max:longint;
a,s,c:array[0..100000] of longint;
hash:array[-100000..100000] of longint;begin
readln(n);
s[0]:=0;
for i:=-n to n do hash[i]:=maxlongint;
hash[0]:=0;
for i:=1 to n do
begin
read(a[i]);
s[i]:=s+a[i];
c[i]:=c+a[i]*2-1;
if hash[c[i]]>i then hash[c[i]]:=i;
end;
max:=0;
for i:=1 to n do
begin
if (hashmax) then
max:=i-hash;
if (hash[2*s[i]-i]max) then
max:=i-hash[2*s[i]-i];
end;
writeln(max);
end.请问这个程序错哪了，为什么就是第6个点和第10个点输出了错误答案？？
纠结~~~~！@#￥%……&*（
HELP!!!! -
0
囧死我了 真没智商了
总共这么长的代码 居然写错了一回---|-->从1到i和为0也是一种可行状态........
var
a,b,c:array[-100000..100000] of longint;
i,n,ans:longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
begin
if a[i]=1 then b[i]:=b+1
else b[i]:=b-1;
if c[b[i]]=0 then c[b[i]]:=i
else if i-c[b[i]]>=ans then ans:=i-c[b[i]];
if b[i]=0 then if i>ans then ans:=i;
end;
writeln(ans);
end.
猫粮寸断
LV 10
@ 2017-11-08 15:40:19
