Codeforces Round 979 (Div. 2) C. A TRUE Battle
题目链接:题目
大意:
Alice和Bob先后轮流向一串01字符串中加入or或and,前者想让结果为1后者想让结果为0,问Alice能不能赢。
思路:
对于相同的两个布尔值,or和and都不能改变它们,而对于Alice,他倾向于向01之间加入or,Bob则想加入and。一开始我想比较1和0的多少不就行了吗,但是不对,当你加入一个运算符后,不能马上结算,因为or和and没有结合律,但是它们可以分别结合,并且and的优先级高。我们可以把or看做加法,and看做乘法,那么很明显是不能随便结合的(不过可以分配)。
有一个性质,就是如果or的一边有一个1,那么另一边无论是什么最终都是1,所以我们只要保住一个1就行了。如果字符串的最左边或者最右边有1,那么Alice在它旁边放一个or,最后肯定是1。否则看中间是否存在至少两个连续的1,如果有,那么Alice先手在中间放or,最后总能用两个or把一个1保护起来,这样最后一定是1。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int, int>
#define vec vector
void solve(){
int n;
cin >> n;
string s;
cin >> s;
if(s[0] == '1' || s[n - 1] == '1'){
cout << "YES" << '\n';
return;
}
for(int i = 1; i < n; i++){
if(s[i] == s[i - 1] && s[i] == '1'){
cout << "YES" << '\n';
return;
}
}
cout << "NO" << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin >> t;
while(t--){
solve();
}
return 0;
} ```