hdu7365 0 vs 1

ganking / 2023-08-12 / 原文

0 vs 1
首先如果两端不同肯定只能直接选。
两端都选不了直接失败。

不妨设现在是zero在选，
从左边来010101交替，如果先出现了一个00
比如 01010100.....10
那么我们就能从这边选，因为one只能跟着我们选这边，最后会出现两边都是0的情况。
从右边来同理。
假如是0101010交替，那么肯定是平局。
假如两边都先出现了11
例如01011.....011010，这样zero就输了，如果只有一个11，那么是平局。

#include<algorithm>
#include<cstring>
#include<iostream>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("Zero")
#define B puts("One")
using namespace std;
typedef long long ll;
const int N=1e5+5;
char s[N];
int n;
bool a[N];
void solve(int l,int r,int op){
	if (a[l]!=op && a[r]!=op) {
		printf("%d\n",1-op);
		return;
	}
	
	if (l==r) {
		puts("-1");
		return;
	}
	
	if (a[l]!=op || a[r]!=op) {
		if (a[l]==op) solve(l+1,r,1^op);
		else solve(l,r-1,1^op);
		return;
	}

	int x,y;
	for (x=l; x<=r-1; x++) if (a[x]==a[x+1]) break;
	
	if (x==r) {
		puts("-1");
		return;
	}
	
	if (a[x]==op) {
		printf("%d\n",op);
		return;
	}
	
	for (y=r; y>=x+1; y--) if (a[y]==a[y-1]) break;
	
	if (a[y]==op) {
		printf("%d\n",op); 
		return;
	}

	if (x+1==y) puts("-1");
	else printf("%d\n",1-op);
	
}
int main() {
//	freopen("data.in","r",stdin);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		scanf("%s",s+1);
		fo(i,1,n) a[i]=(s[i]=='1');
		
		solve(1,n,0);
	}
	
    return 0;
}