社区讨论

求助P1114

灌水区参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m2kbvii6
此快照首次捕获于
2024/10/22 18:54
去年
此快照最后确认于
2025/11/04 16:31
4 个月前
查看原帖
为啥wa了三个点,思路就是记录第一次出现与最后出现位置,用前缀和
CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n; 
int a[100005];
int sum[100005],maxn,ans;
map<int,int>stat;
map<int,int>last;
int read(){
	int x=0,f=1;
	char ch  = getchar();
	while (ch < 48 || ch > 57){
		if (ch == 45){
			f = -1;
		}
		ch = getchar();
	}
	while (ch >= 48 && ch <= 57){
		x = (x << 1) + (x << 3) + (ch - 48);
		ch = getchar();
	} 
	return  x * f;
}
signed main(){
	 n = read();
	for (int i=1; i<=n; i++){
		a[i] = read();
		if (a[i] == 0) a[i] = -1;
		sum[i] = sum[i-1]+a[i];
		stat[sum[i]] = 0;
		last[sum[i]] = 0;
	}
	for (int i=1; i<=n; i++){
		last[sum[i]] = i;
		if (stat[sum[i]] > 0){
			continue;
		}
		else {
			stat[sum[i]] = i;
		}
	}
	for (int i=1; i<=n; i++){
		if (stat[sum[i]] == last[sum[i]]){
			continue;
		}
		ans = last[sum[i]] - stat[sum[i]];
		maxn = max(ans,maxn);
	}
	cout << maxn;
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...