[cf]Codeforces Round #527 (Div. 3) D1 Great Vova Wall (Version 1)

前言

t a g : tag : tag: 思维 难题 数据结构 *2200 传送门 :

题意

给定一个长度为 n n n的围墙,围墙第 i i i位置有 a [ i ] a[i] a[i]的高度

你可以放置一个 2 ∗ 1 2*1 2∗1的砖块,横竖 都可以摆放,询问是否可以将墙统一高度

(放置的砖不可以超出 1 , n 1,n 1,n)

换句话说就是 , 给定一个长度为 n n n的数组 a [ ] a[] a[]

你可以让连续两个元素 + 1 +1 +1

或者让一个元素 + 2 +2 +2,询问 a [ ] a[] a[]是否可能 相等

思路

分析操作的性质

• 对于 + 2 +2 +2,他会改变当前数的奇偶性
• 而对于 + 1 +1 +1,不会改变当前数的 奇偶性

也就是如果存在两个连续奇偶性相同的数,那么这这两个数是可以被移除的

例如 [ 1 , 2 , 2 , 3 ] [1,2,2,3] [1,2,2,3]显然 [ 2 , 2 ] [2,2] [2,2]是可以被移除的,因为 2 , 2 2,2 2,2最后可以转换为 3 3 3这样子对后面的数是没有影响的

因此渐渐的,这个题目就明了了,因为存在可消去操作,又变回了栈匹配问题

最后需要注意的是 s t k . s i z e ( ) = = 1 stk.size()==1 stk.size()==1也是可行的,因为所有数都可以此基础上加到 x x x

Code

map mp;
// const int N =
void solve(){
	int n;cin>>n;
	stack stk;
	
	for(int i=1;i>x;
		x = x%2;
		
		if(stk.empty())stk.push(x);
		else if(stk.top() == x) stk.pop();
		else stk.push(x);
	}
	if(stk.size()