Codeforces 940D

题意略。

这道题目在比赛的时候怎么想也没想明白，后来看了别人的题解才顿悟，可以说很辣鸡了。

只有b[i - 1],b[i - 2],b[i - 3],b[i - 4]相等的时候才能对答案产生限制，否则全部都会成为第三种情况。

那么现在就有00000，00001，11110，11111这4种情况了。

1.00000可知这种状态来源于第三种情况，那么说明第二种状况的第一个条件是错的。

2.00001可知这种状态来源于第二种情况，那么说明第二种状况的两个条件都是对的。

3.11110可知这种状态来源于第一种情况，那么说明第一种情况的两个条件都是对的。

4.11111可知这种状况来源于第三种情况，那么说明第一种情况的第一个条件是错的。

详见代码：

#include<bits/stdc++.h>
#define maxn 100010
#define INF 1e9
using namespace std;

char b[maxn];
int a[maxn];
int l,r,n;

int getmax(int l,int r){
    int ret = -INF;
    for(int i = l;i <= r;++i){
        ret = max(a[i],ret);
    }
    return ret;
}
int getmin(int l,int r){
    int ret = INF;
    for(int i = l;i <= r;++i) ret = min(ret,a[i]);
    return ret;
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
    scanf("%s",b + 1);
    l = -INF,r = INF;
    for(int i = 5;i <= n;++i){
        if(b[i - 1] == '0' && b[i - 2] == '0' && b[i - 3] == '0' && 
        b[i - 4] == '0'){
            int maxx = getmax(i - 4,i);
            if(b[i] == '0') l = min(l,maxx);
            else l = max(l,maxx + 1);
        }
        else if(b[i - 1] == '1' && b[i - 2] == '1' && b[i - 3] == '1' && 
        b[i - 4] == '1'){
            int minn = getmin(i - 4,i);
            if(b[i] == '0') r = min(r,minn - 1);
            else r = max(r,minn);
        }
    }
    printf("%d %d
",l,r);
    return 0;
}