减法操作
给定一个包含 $n$ 个非负整数的数列 $a_1,a_2, \dots ,a_n$。
你可以对该数列进行以下两种减法操作：
- 任选其中一个元素，并将该元素的值减去 $2$。
- 任选两个相邻元素，并将两个元素的值各减去 $1$。
请你判断，能否经过一系列减法操作，使得数列中的所有元素都变为 $0$。
输入格式
第一行包含整数 $n$。
第二行包含 $n$ 个非负整数 $a_1,a_2, \dots ,a_n$。
输出格式
如果能够经过一系列减法操作，使得数列中的所有元素都变为 $0$，则输出 YES ，否则输出 NO 。
数据范围
前 $6$ 个测试点满足 $1 \leq n \leq 10$。
所有测试点满足 $1 \leq n \leq 2 \times {10}^{5}$，$0 \leq a_i \leq {10}^{4}$。
输入样例1：
4 1 2 1 2
输出样例1：
YES
输入样例2：
3 1 0 1
输出样例2：
NO
解题思路
比赛的时候想到的思路是，既然要求最后整个序列的每个数都变成$0$，那么就构造出一种方案，看看能不能让每个位置上的数都变成$0$。从前往后遍历每一个数，如果这个数是偶数，那么只进行操作$2$就可以。如果这个数是奇数，那么至少要执行一次操作$1$，这里就规定每次执行操作$1$时都是与当前位置的下一个位置减$1$，且对该数只执行一次操作$1$，剩下的都执行操作$2$（如果是序列的最后一个数，由于没有下一位了，因此如果最后一个数是奇数，那么就不可以执行任何操作了，即无法将序列变成全$0$）。最后看一下每一个位置是否都是非负数并且都是偶数就可以了。
补一下y总严格的证明。
我们将所有的操作方案看作是一个集合，现在考虑一下最优解有什么性质，看能不能在一个子集中找到答案。首先操作顺序并不会影响结果，比如对于一个数，先减$2$再减$1$，或者是先减$1$再减$2$都不会影响这个数的最终结果。因此我们可以人为定义一个操作顺序，就是先执行所有的操作$2$再去执行操作$1$，我们就可以在这个子集中看一下是否存在一种方案使得序列变成$0$。同时对于相邻的两个数，如果这两个数执行了两次操作$2$，那么等价于这两个数分别执行一次操作$1$，因此在这个子集中我们还可以考虑另外一个子集，在这子集中同一对元素只会执行一次操作$2$，因此最终我们只需要在这个子集的子集里面考虑就可以了，如果这个子集中存在某个方案使得序列变成$0$，那么代价于执行完所有的操作$2$后所有元素都变成非负偶数才可以。
我们可以从前往后找到第一个奇数，由于要变成偶数，那么就要对这个数执行操作$2$，有两种选择，要么与这个数后面一个数执行操作$2$，要么与这个数前面一个数执行操作$2$。如果是与这个数前面一个数执行操作$2$，由于前面这个数是偶数，因此操作完后就变成奇数，由于要变成偶数，因此也有两种选择，与后面一个数或者与前面一个数执行操作$2$。如果是选择后面一个数，那么相当于相邻的两个元素执行了两次操作$2$，而这种方案不在这个子集中，因此只能选择前面的数。以此类推，前面的数又从偶数变成奇数了，那么总是与前一个数执行操作$2$，直到是序列的第一个元素，第一个数变成奇数，此时它前面没有元素了，就无法执行操作$2$，也不能与后面一个数执行操作$2$，因此就无解了。因此我们从前往后枚举找到第一个奇数后，我们只能操作这个数和它后面一个数，所以操作方案是唯一的。
如果从前往后枚举找到某个数是偶数，要么不执行操作$2$，要么执行两次操作$2$，并且这两次操作$2$分别是选择前面一个数和后面一个数。而与前面一个数执行完操作$2$后，前面那个数就变成奇数了，那么又要对前面这个数执行操作$2$，可以发现又变成上面所描述的无解的情况了。因此如果遇到偶数，我们不能进行操作$2$。
因此如果遇到奇数我们只能操作这个数和它后面一个数，如果数偶数我们不能操作。所以操作方案是唯一确定的。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 2e5 + 10;
5
6 int a[N];
7
8 int main() {
9 int n;
10 scanf("%d", &n);
11 for (int i = 0; i < n; i++) {
12 scanf("%d", a + i);
13 }
14
15 bool flag = true;
16 for (int i = 0; i < n; i++) {
17 if (a[i] < 0) { // 每个数要求是非负偶数
18 flag = false;
19 break;
20 }
21 if (a[i] & 1) { // 奇数
22 if (i == n - 1) flag = false; // 最后一个数是奇数，而最后一个数后面没有数，无法执行操作2
23 a[i + 1]--; // 与后面一个数执行操作2
24 }
25 }
26
27 printf("%s", flag ? "YES" : "NO");
28
29 return 0;
30 }
参考资料
AcWing 4619. 减法操作（AcWing杯 - 周赛）：https://www.acwing.com/video/4405/
标签：奇数,一个,元素,偶数,操作,减法,执行 From： https://www.cnblogs.com/onlyblues/p/16727282.html