题意
给你n堆石头,每次你能让相邻的两个石头-1,且开局时你有一个特殊操作可以交换两个相邻
的堆。问你能否实现将所有的堆都减为0
思路
考虑消除过程:
给定一个序列:(a_1,a_2,a_3,a_4...a_{n-2},a_{n-1},a_n)
正向消除:
[a_1-0, a_2-(a_1-0),a_3-(a_2-(a_1-0))...
]
为了方便我们令(pre[i])表示消除当前元素后的剩余值,再看一遍正向消除:
[pre[1] = a[1] - pre[0],pre[2] = a[2] - pre[1], pre[3] = a[3] - pre[2]...
]
整个过程中我们必须要保证(pre[])是正值((a[i] - pre[i - 1] < 0 --> pre[i - 1] > a[i]))那么(a[i-1])是没有消完的)
反向消除:
[a_n - 0, a_{n - 1} - (a_n - 0),a_{n - 2} - ( a_{n - 1} - (a_n - 0))...
]
为了方便我们令(suf[i])表示消除当前元素后的剩余值(反向消除n->1),再看一遍反向消除:
[suf[n] = a[n] - 0, suf[n-1] = a[n -1] - suf[n],suf[n -2] = a[n - 2] - suf[ - 1]...
]
我们容易明白的是正向消除时假设消除到了x处((pre[i] < 0)),此时对前面成功消除的(1~x-2)并不会产生影响
反向消除时假设消除到了x处((suf[i] <0)),此时对后面成功消除的(x+2~n)并不会产生印象。
那么我们预处理前后缀后来枚举交换哪两个即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
//#define int long long
int a[N], pre[N], suf[N];
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 0; i <= n + 1; ++i)pre[i] = suf[i] = 0;
for (int i = 1; i <= n; ++i) {
if (pre[i - 1] > a[i] || pre[i - 1] == -1) pre[i] = -1;
else pre[i] = a[i] - pre[i - 1];
}
if (pre[n] == 0) {
cout << "YES
";
return ;
}
for (int i = n; i >= 1; --i) {
if (suf[i + 1] > a[i] || suf[i + 1] == -1) suf[i] = -1;
else suf[i] = a[i] - suf[i + 1];
}
for (int i = 0, j = 3; j <= n + 1; ++i, ++j) {
if (pre[i] == -1 || suf[j] == -1) continue;
if (pre[i] <= a[j - 1] && a[i + 1] >= suf[j] && a[j - 1] - pre[i] == a[i + 1] - suf[j]) {
cout << "YES
";
return ;
}
}
cout << "NO
";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}