Codeforces Round #172 (Div. 2) D. Maximum Xor Secondary 单调栈应用-白红宇

Codeforces Round #172 (Div. 2) D. Maximum Xor Secondary 单调栈应用

阅读量：5113 次

发布时间：2019-06-13

本文共 1303 字，大约阅读时间需要 4 分钟。

要求找出一个区间，使得区间内第一大的数和第二大的数异或值最大。

首先维护一个单调递减的栈，对于每个新元素a[i]。要么直接插入后面，如果它插入栈内的某个元素的话。就是说有数字弹出来了，这个时候这个数字和a[i]组成的就是区间第一、第二大，9 8 5 4 3 2 1 7这样，最后那个7，弹出1，证明[7,8]这个区间第一、第二大的数字分别是1、和7，其他类似。

还有一个地方要注意的是: 要特别处理那些不能弹出的数字，就是9和8这样，不能被其他数字弹出，他们组成的区间没办法计算。解决办法就是每次都把栈顶元素和第二顶元素算一次，更新答案。这么才能不重不漏。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  const int maxn = 1e5 + 20;LL a[maxn];int stack[maxn];void work (){ int n; scanf ("%d", &n); LL mx = -inf, sec = -inf; for (int i = 1; i <= n; ++i) { scanf ("%I64d", &a[i]); mx = max (a[i], mx); } for (int i = 1; i <= n; ++i) { if (a[i] > sec && a[i] != mx) { sec = a[i]; } } LL ans = mx ^ sec; int top = 0; for (int i = 1; i <= n; ++i) { while (top >= 1 && a[i] > a[stack[top]]) { ans = max (ans, a[i] ^ a[stack[top]]); top--; } ++top; stack[top] = i; if (top >= 2) { ans = max (ans, a[stack[top]] ^ a[stack[top - 1]]); } } printf ("%I64d\n", ans); return ;}int main (){#ifdef local freopen("data.txt","r",stdin);#endif work (); return 0;}

View Code

转载于:https://www.cnblogs.com/liuweimingcprogram/p/5821582.html

你可能感兴趣的文章