给定n(5 ≤ n ≤ 10⁵) ，接着给出长度为n的序列a和字符串b

 

b1 = b2 = b3 = b4 = 0.

For all 5 ≤ i ≤ n: 

• b_i = 0 if a_i, a_i - 1, a_i - 2, a_i - 3, a_i - 4> r and b_i - 1 = b_i - 2 = b_i - 3 = b_i - 4 = 1
• b_i= 1 if a_i, a_i - 1, a_i - 2, a_i - 3, a_i - 4< l and b_i - 1 = b_i - 2 = b_i - 3 = b_i - 4 = 0
• b_i = b_i - 1 otherwise

则b中出现00001可确定l下界，11110可确定r上界

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int maxn = 1e5 + 10; 7 int A[maxn]; 8 char S[maxn]; 9 int n;10 11 int _min(int i) {12     int t = A[i];13     for (int j = i - 1; j > i - 5; j--) {14         t = min(t, A[j]);15     }16     return t;17 }18 19 int _max(int i) {20     int t = A[i];21     for (int j = i - 1; j > i - 5; j--) {22         t = max(t, A[j]);23     }24     return t;25 }26 27 int main() {28     scanf("%d", &n);29     for (int i = 0; i < n; i++) scanf("%d", &A[i]);30     scanf("%s", S);31     int zero = 0, one = 0;32     int r = 1e9;33     int l = -r;34     for (int i = 0; i < n; i++) {35         if (S[i] == '0') {36             if (one >= 4) {37                 r = min(r, _min(i) - 1);38             }39             one = 0;40             zero++;41         } else if (S[i] == '1') {42             if (zero >= 4) {43                 l = max(l, _max(i) + 1);44             }45             zero = 0;46             one++;47         }48     }49     printf("%d %d\n", l, r);50     return 0;51 }