CF1671A.String Building

题目大意

题目描述

给出一个只有字母 $a$ 和 $b$ 的字符串 $s$ ，问能否用多个字符串aa,aaa,bb,bbb组成这个字符串。

输入格式

给出一个数 $t$，表示有 $t$ 组测试用例。

接下来 $t$ 行，每行一个字符串 $s$。

输出格式

一共 $t$ 行，每行都是YES或者NO表示能否组成这个字符串。

题目分析

由题意可得，将 $s$ 分为 $k$ 块。如果第 $i$ 块有奇数个字符，并且字符数量多于 $1$ 那么就再分，分为 $2n(n\in\mathbb N)$ 块。多出来的一个字符可以给第 $n$ 块，这样就会有 $2(n-1)$ 个字符串aa或bb，$1$ 个字符串aaa或bbb。如果第 $i$ 块有偶数个字符，那么就有 $2n(n\in\mathbb N)$ 块aa或bb。

但是无论如何第 $i$ 块都必须有多于 $1$ 个字符。如果有一块只有一个字符，那么它这个字符必定和前后不一样。所以我们只需要从 $s_1$ 开始查找，判断这个字符和它前后的字符是否相同。

注意要判断 $s_0$ 是否等于 $s_1$，否则如果出现如abb这样的数据就会给出错误结果，还有s.size()是否等于 $0$，否则会Runtime Error。

时间复杂度 $\mathcal O(n)$，注意有 $\mathcal O(2)$ 的处理。

代码

#include<bits/stdc++.h>
using namespace std;

void solve () {
	string s;
	cin >> s;
	
	if (s.size () == 1) {
			cout << "NO" << endl;
			return;
	} 
	
	if (s [0] != s [1]) {
		cout << "NO" << endl;
		return;
	}
	
	for (int i = 1; i < s.size (); i ++) {
		if (s [i] != s [i - 1] && s [i] != s [i + 1]){
			cout << "NO" << endl;
			return;
		} 
	}
	
	cout << "YES" << endl;
}

int main () {
	int t;
	cin >> t;
	
	while (t --) {
		solve();
	}
	
	return 0;
}