思路挺有意思，记录下来

原题链接

题目大意：

初始情况下给定一个长为n，元素全为0的数列，规定一种指针移动规则：

1.指针不在最后一个元素上时，先将指针指向的元素加1，再将指针向后移动一个位置

2.指针不在第一个元素上时，先将指针指向的元素减1，再将指针前移一个位置

初始指针位于第一个元素的位置，可以执行任意次数上面两条规则，执行完毕后指针还要处在第一个位置上

现在给你一些长度为n的数列，判断是否能够通过规定的指针移动规则生成此数列，可以输出Yes，不可以输出No

第一行输入t (1≤t≤1000)，表示有t组数据，随后每组数据第一行为n (1≤n≤2e5)，第二行包含n个数si (−1e9≤si≤1e9)；输出每组数据单独一行，例如：

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
intput

7
2
1 0
4
2 -1 -1 0
4
1 -4 3 0
4
1 -1 1 -1
5
1 2 3 4 -10
7
2 -1 1 -2 0 0 0
1
0

output

No
Yes
No
No
Yes
Yes
Yes

原题给出了第二个样例的一个可行方案（星号表示指针所处位置）：⟨0*,0,0,0⟩→⟨1,0*,0,0⟩→⟨1*,−1,0,0⟩→⟨2,−1*,0,0⟩→⟨2,0,0*,0⟩→⟨2,0*,−1,0⟩→⟨2*,−1,−1,0⟩

没有相关经验的话可能容易考虑得比较复杂，以致越想越乱，如何判断给的数组在这种生成方式下是否存在矛盾？

考虑到指针最终必须回到第一位，换句话说整个数列求和必须是0；每个数大小怎么产生？不需要想数和数之间的相互作用，单独考虑每个数：每个数的值=在此位置执行规则1的次数-在此位置执行规则2的次数，又因为指针必须回到第一位，所以在此位置执行规则2的次数必须等于前一个位置上执行规则1的次数，于是发现相邻数的操作1的次数存在递推关系可以求出每个位置上的操作1的次数：

随后即可通过判断b的值来判断是否合法（操作一与操作二对应的，因此只需考虑一种），如果有位置上b<0明显没有可行方案，如果有位置上b=0，那么之后的所有元素都必须是0（指针过不去），最后一个b也必须是0，值得注意的是数据范围较大，b不开long long过不去

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
45
46
#include<iostream>
#include<cstring>
#include<algorithm>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int N=2e5+10;
int t,n;
int s[N];
long long b[N];

int main(){
    fastIO
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>s[i];
        for(int i=1;i<=n;i++){
            b[i]=b[i-1]+s[i];
        }
        if(b[n]!=0){
            cout<<"NO"<<'\n';
            continue;
        }
        bool ok=true,vis=false;
        for(int i=1;i<=n;i++){
            if(b[i]<0){
                ok=false;
                break;
            }
        }
        for(int i=1;i<=n;i++){
            if(vis){
                if(s[i]!=0){
                    ok=false;
                    break;
                }
            }
            else if(b[i]==0){
                vis=true;
            }
        }
        if(ok) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    return 0;
}