题解：CF2030C A TRUE Battle

Luogu Link | Codeforces Link

\(\texttt{Describe}\)

给一个长度为 \(n\) 的二进制序列，Alice 和 Bob 在相邻两个0/1中间分别加 \(\operatorname{or}\) 或 \(\operatorname{and}\) 操作，优先级满足 \(\operatorname{and} > \operatorname{or}\)。

Alice 希望最后运算的值为 \(1\)，Bob 希望它为 \(0\)。

若双方进行最优操作，问最后值为 \(0\)（YES）还是 \(1\)（NO）。

\(\texttt{Solution}\)

Hits 1: 观察首尾性质

注意到当序列首是 \(1\) 的时候，只要 Alice 在后面加个 \(\operatorname{or}\)，整个序列的值一定为 \(1\)。

同理当序列尾是 \(1\) 的时候，值也为 \(1\)。

另外，当序列出现了 \(\dots 11 \dots\) 的时候，Alice 一定可以构造出 \(\dots \operatorname{or} 1 \dots 1 \operatorname{or}\) 或者 \(\dots 1 \operatorname{or} 1 \operatorname{or} \dots\) 的形式使得整个序列为 \(1\)。

判断即可。

\(\texttt{Code}\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

void solve() {
	int n; cin >> n;
	string s; cin >> s;
	if ((s.back() == '1' || s.front() == '1') || s.find("11") != s.npos) {
		cout << "YES\n";
	}else {
		cout << "NO\n";
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	
	int T; cin >> T; while (T --) solve();
	return 0;
}