AT_abc265_d 题解

发布时间 2023-11-15 23:12:00作者: SSSSSSSSSSoil

### 题意

给出一串数,请尝试在这串数中找到三段**连续**的子段,使得这三个子段的和分别为 $P$、$Q$ 和 $R$。问:是否可行?

### 思路

通过观察,观察我们可以发现,其实我们可以根据题目的要求写出一段关系式:

$A+P+Q+R+B$(其中 $A$ 表示被选子段前面没被选的子段和,其中 $B$ 表示被选子段后面没被选的子段和)

接下来,我们把这个式子带入前缀和,就会发现,如果我们知道了这三个子段中任意一个的一个端点,通过以下推导式,就能得到是否可行。

前缀和为 $S_{i} + P$ 的 $x$ 存在,且前缀和为 $S_{i} + Q + R$ 的 $x$ 存在,且前缀和为 $S_{i} + P + Q + R$ 的 $x$ 存在。

### 代码实现

所以,在代码实现时,我们寻找前缀和为 $a$ 的 $x$ 是否存在时,传统的方法是用 `map` 实现,但是,我用了另一种容器: `set`。我对 `set` 的理解是:集合。

本次我使用到 `set` 的功能是:`insert`、`find` 和 `end`。

- `insert`:在集合里插入某个元素。
- `find` 和 `end` :我们可以用 `st.find( a ) != st.end()` 判断元素 `a` 是否在集合中存在。

### AC CODE

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , a[200005] , s1 , s2 , s3 , sum ;
set<int> st( {0} ) ;
signed main(){
cin >> n >> s1 >> s2 >> s3 ;
for( int i = 1 ; i <= n ; i ++ ){
cin >> a[i] ;
sum += a[i] ;
st.insert( sum ) ;
}
for( auto i : st ){
if( st.find( i + s1 ) != st.end() && st.find( i + s1 + s2 ) != st.end() && st.find( i + s1 + s2 + s3 ) != st.end() ){
cout << "Yes\n" ;
return 0 ;
}
}
cout << "No\n" ;
return 0 ;
}
```