Romantic Glasses

解题思路

题目说的很清楚了，求是否存在 LL 和 $ R$，使 aLa_L 到 aRa_R 中奇数下标的数之和等于偶数下标的数之和，如果存在输出 Yes，否则输出 No。

方法一：前缀和 + 暴力

抛开时间复杂度（n2n ^ 2）不谈，在输入过程中根据下标奇偶性预处理前缀和数组，再通过双重循环判断即可。

1
2
3
4
5
6
for (int i = 1; i <= n; i ++)
    {
        int x; cin >> x;
        if (i & 1) pre[i] = pre[i - 2] + x;
        else pre[i] = pre[i - 2] + x;
    }

方法二：前缀和 + map

仔细想想不难看出，我们可以仅在一个前缀和数组上双向处理，如果 ii 为奇则加上这个数，为偶则减去这个数。此时求出的前缀和 preipre_i 就是 从 11 到 ii 之中奇数下标之和与偶数下标之和之差。如果存在 prei−1=prejpre_{i - 1} = pre_j，则说明从 i−1i - 1 到 jj 之中数下标的数之和等于偶数下标的数之和，此时可以输出 YES，如果在循环之后没有 NO。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Problem: E. Romantic Glasses
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define int long long

const int N = 2e5 + 9;
const int INF = 0x3f3f3f3f;
int n, pre[N];
map<int, bool> mp;

bool solve()
{
    bool flag = false;
    cin >> n;
    mp.clear(); mp[0] = true;
    for (int i = 1; i <= n; i ++)
    {
        int x; cin >> x;
        if (i & 1) pre[i] = pre[i - 1] + x;
        else pre[i] = pre[i - 1] - x;
        
        if (mp[pre[i]] == true) flag = true;
        mp[pre[i]] = true;
    }
    return flag;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T --) cout << (solve() ? "YES\n" : "NO\n");
    return 0;
}