Codeforces-1474 D. Cleaning（前缀和）

本文主要是介绍Codeforces-1474 D. Cleaning（前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

During cleaning the coast, Alice found 𝑛 piles of stones. The 𝑖-th pile has 𝑎𝑖 stones.

Piles 𝑖 and 𝑖+1 are neighbouring for all 1≤𝑖≤𝑛−1. If pile 𝑖 becomes empty, piles 𝑖−1 and 𝑖+1 doesn’t become neighbouring.

Alice is too lazy to remove these stones, so she asked you to take this duty. She allowed you to do only the following operation:

Select two neighboring piles and, if both of them are not empty, remove one stone from each of them.
Alice understands that sometimes it’s impossible to remove all stones with the given operation, so she allowed you to use the following superability:

Before the start of cleaning, you can select two neighboring piles and swap them.
Determine, if it is possible to remove all stones using the superability not more than once.

Input
The first line contains a single integer 𝑡 (1≤𝑡≤104) — the number of test cases.

The first line of each test case contains the single integer 𝑛 (2≤𝑛≤2⋅105) — the number of piles.

The second line of each test case contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤109) — the number of stones in each pile.

It is guaranteed that the total sum of 𝑛 over all test cases doesn’t exceed 2⋅105.

Output
For each test case, print YES or NO — is it possible to remove all stones using the superability not more than once or not.

Example
inputCopy
5
3
1 2 1
3
1 1 2
5
2 2 2 1 3
5
2100 1900 1600 3000 1600
2
2443 2445
outputCopy
YES
YES
YES
YES
NO
Note
In the first test case, you can remove all stones without using a superability: [1,2,1]→[1,1,0]→[0,0,0].

In the second test case, you can apply superability to the second and the third piles and then act like in the first testcase.

In the third test case, you can apply superability to the fourth and the fifth piles, thus getting 𝑎=[2,2,2,3,1].

In the fourth test case, you can apply superability to the first and the second piles, thus getting 𝑎=[1900,2100,1600,3000,1600].

题意：
你可以任选相邻两个非0数，使得两者都减1。
你可以选择相邻两个数交换位置，至多操作1次。
求能否使得每个数都变成0。

思路：

从边界开始考虑，很明显边界的数只能被边上一个数抵消掉（因为边上只有一个数）。因此可以维护一个前缀和代表从第一个数依次抵消到了第 $i$ 个数后，第 $i$ 个数剩下的数（如果不能抵消到第 $i$ 个数，结果就是INF）。同理可以维护个后缀和代表从最后的数依次抵消到第 $i$ 个数后第 $i$ 个数的值。
假设没有交换操作，那么就是满足 $p r e [i] = s u f [i + 1]$ 即可，也就是一个前缀和等于后缀和。
如果有交换操作，那也好整，就只前缀和和后缀和中间的两个数分别考虑一下，此时变成了4个数 $p r e [i], a [i + 2], a [i + 1], s u f [i + 3]$ ，只要保证 $a [i + 2] \geq p r e [i], a [i + 1] \geq s u f [i + 3]$ ，且 $a [i + 2] - p r e [i] = a [i + 1] - s u f [i + 1]$ ，就说明交换 $a [i + 1], a [i + 2]$ 后可以全部消掉。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
int pre[maxn],suf[maxn],a[maxn];
int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);for(int i = 1;i <= n;++i) scanf("%d",&a[i]);suf[n + 1] = 0;for(int i = 1;i <= n;i++) {if(a[i] >= pre[i - 1]) {pre[i] = a[i] - pre[i - 1];} else {pre[i] = INF;}}for(int i = n;i >= 1;i--) {if(a[i] >= suf[i + 1]) {suf[i] = a[i] - suf[i + 1];} else {suf[i] = INF + 1e6;}}int flag = 0;for(int i = 1;i < n;i++) {if(pre[i] == suf[i + 1]) {flag = 1;break;} else { //i和i+1交换int x = a[i + 1],y = a[i];if(x >= pre[i - 1] && y >= suf[i + 2]) {x -= pre[i - 1];y -= suf[i + 2];if(x == y) {flag = 1;break;}}}}if(flag) {printf("YES\n");} else {printf("NO\n");}}return 0;
}