题面

Great Vova Wall (Version 1)

Vova 在建一堵墙（Vova 美名其曰“The Great Vova Wall”）。此时有序列 a = { a 1 , a 2 , … , a n } a = \{a _ 1 , a _ 2 , \dots , a _ n\} a={a1​,a2​,…,an​}，其中 $a_i$ 表示墙体第 $i$ 部分的高度。

（注：此问题中假设 Vova 的砖头无限且只能用 $2\times 1$ 的砌墙）

Vova 可以将砖头水平放置或垂直放置。当然水平放置时不可让砖头“越界”，即砖头不可有部分位于第 $1$ 部分的左边或位于第 $n$ 部分的右边。水平放置时砖头将会使第 $i$ 和 $i+1$ 部分高度 $+1$，垂直放置时则将其所在的位置高度 $+2$。

重度强迫症患者兼完美主义者 Vova 认为所有部分高度相等以及墙内没有空隙时这堵墙才算完工。

形式化地，给定一个序列 a = { a 1 , a 2 , … , a n } a = \{a _ 1 , a _ 2 , \dots , a _ n\} a={a1​,a2​,…,an​}，有以下两种操作：

• 若 $a_i=a_{i+1}$，则可将 $a_i$ 与 $a_{i+1}$（$1\le i<n$）同时加 $1$；
• 将 $a_i$（$1\le i\le n$）加 $2$。

求问是否可经过多此操作后使得所有 $a_i$ 相等。

输入

第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$），表示墙体部分数。

第二行包含 $n$ 个数 $a_1,a_2,\cdots ,a_n$（$1\le a_i\le 10^9$），表示墙体高度的初始值。

输出

若 Vova 可以添加砖块使得墙体完工输出 YES，否则输出 NO。

思路

$\text{tag}$：math

注意到对任意 $1\le i\le n$ 可将 $a_i$ 加 $2$，于是，可将墙转化为 $a_1\&1,a_2\&2,\cdots ,a_n\&1$ 或 $1-(a_1\&1),1-(a_2\&2),\cdots ,1-(a_n\&1)$，其中 $\&$ 为二进制按位与，$x\&1$ 即表示 $x$ 的奇偶性。

对于一面墙，若墙在 $[l,r]$ 区间可砌，则 $a_{l-1}=a_{r+1}$ 时，$[l-1,r+1]$ 必然可砌。这类似一个合法括号序列问题，相同的 $a_i$ 为一组括号，若去除首尾的 $0$ （或 $1$）前后缀，墙是一个合法的括号序列，则墙可砌。

于是对于 $a_1\&1,a_2\&2,\cdots ,a_n\&1$ 和 $1-(a_1\&1),1-(a_2\&2),\cdots ,1-(a_n\&1)$，用一个栈存储 $a$，对于所有 $1\le i\le n$ 的 $a_i$，若 $a_i$ 与 栈顶数字相等，则栈顶数字出栈；否则 $a_i$ 出栈。若墙可砌，则最后栈中最多剩余一个数，若剩余，则必为墙首或墙尾数字（不妨定为 $0$，分别判断 $a$ 与 $1-a$）；否则墙不可砌。

时间复杂度 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int a[maxn];
int n;
bool check(){
	stack<int> s;
	for(int i=1;i<=n;i++){
		if(s.empty()){
			s.push(a[i]);
			continue;
		}
		int x=s.top();
		if(x^a[i]){
			s.push(a[i]);
		}else{
			s.pop();
		}
	}
	int flag=0;
	while(!s.empty()){
		flag|=s.top();
		s.pop();
	}
	return !flag;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]&=1;
	}
	if(n<2 || check()){
		cout<<"YES\n";
		return;
	}
	for(int i=1;i<=n;i++){
		a[i]^=1;
	}
	if(check()) cout<<"YES\n";
	else cout<<"NO\n";
}
signed main(){
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}

另附：题解：CF1092D2