专栏文章

题解：AT_arc119_c [ARC119C] ARC Wrecker 2

lliyao2025
AT_arc119_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mininq0c
此快照首次捕获于
2025/12/02 03:02
3 个月前
此快照最后确认于
2025/12/02 03:02
3 个月前
查看原文

题意

在给定序列中选取一个区间 [L,R][L,R] 并在这个区间内选取相邻两个数同时加一或减一，使得区间和为 00，求有多少个这样的区间。

思路

从区间长度为 22 开始想，则当前区间内两个数必须相等才为合法。接着区间长度为 33 时，要使区间合法，则中间的数必须等于两端数的和才为合法。继续扩大区间，当区间长度为 44 时，令 x1,x2,x3,x4x_1,x_2,x_3,x_4 分别为区间四个数，减去两端的数，则为 0,x2−x1,x3−x4,00,x_2-x_1,x_3-x_4,0，这时就变成区间长度为 22 的情况，整理可得 x1+x3=x2+x4x_1+x_3=x_2+x_4。区间长度扩大到 55 时，我们令 x1,x2,x3,x4,x5x_1,x_2,x_3,x_4,x_5 分别为区间五个数。减去两端的数，则为 0,x2−x1,x3,x4−x5,00,x_2-x_1,x_3,x_4-x_5,0，此时就变成了长度为 33 是的区间情况。

优化

令 s[i]s[i] 为前缀和数组。则每当 s[i],s[j](j<i)s[i],s[j](j<i) 相等时就为一个合法的区间。考虑用 mapmap 来记录前 ii 个 s[i]s[i] 出现的个数，则条件符合时 ans+=m[s[i]]ans+=m[s[i]] 组合答案。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
long long n,sum,ans,t; 
map<long long,long long>m;
int main()
{
	scanf("%lld",&n);
	m[0]=1;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		if(i%2!=0)sum+=t*1;
		else sum+=t*(-1);
		ans+=m[sum]++;
	}
	printf("%lld",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...