题解

11 条题解

  • 11
    @ 2017-04-08 10:40:17

    菜鸟表示想不出这道题的算法。看了下别人的blog,总算想明白思路是怎样的。于是写个略详细的题解,方便初学者学习。
    【单调栈】

    思考方向:

    我们先考虑简单的几个数的情况,
    比如数组[1,2,3],那么我们要比较的就是1^2,2^3的大小关系。注意到1^3的情况不在考虑范围中,因为对于1到3的这段区间,次大数为2,所以ans[1,2,3] 其实也就等于 ans[2,3](ans就是指最终的答案), 1已经不需要再考虑了。
    这是问题的突破口。
    也就是说,假定数组一开始的两个数是a,b,且a<b, 我们先用(a^b)更新ans值,然后对于其他的区间,我们发现都不再需要a来更新答案了。
    比如区间[1..n](n>2),
    要么存在两个数都大于b(最大数次大数就是这两个数),
    要么只存在一个数大于b(最大数是这个数,次大数是b),
    要么不存在大于b的数,存在比a大的数(最大的比a大的数是次大数,最大数是b)
    要么其他所有的数都比a,b小(最大数次大数是ba,已经更新过答案)。

    这四种情况中,没有一种是需要再次用a来更新答案的。所以,我们更新了a^b后,就可以把a舍弃掉。

    扩展一下,不仅仅在开头两个位置,在序列里任意一个位置,出现了两个数升序的情况(a在b左边,a<b),我们都可以在用a^b更新答案后,把a舍弃掉。

    也就是说,我们可以维护一个严格降序的单调序列。
    举个例子,数组是[6,4,2],此前我们依次用6^4,4^2更新答案,然后再加一个数:
    如果这个数是5,那么先用2^5更新答案,然后舍弃2(2已经用不到了),再用4^5更新答案,4照样也不再需要用到,舍弃4,最后用6^5更新答案,把5加入序列,变成[6,5].

    所以最终算法是,用stack实现,第一个元素入栈,后面加元素时,把栈头小于新元素的数全部压出栈(出栈同时更新答案),再用新元素和栈头更新答案,新元素入栈。

    #include <cstdio>
    #include <stack>
    using namespace std;
    stack <int> s;
    int ans = -1;
    void update(const int a,const int b)
    {
        if ((a ^ b) > ans)  ans = a ^ b;
    }
    int main()
    {
    
        int n;
        scanf("%d",&n);
        int x;
        scanf("%d",&x);
        s.push(x);
        for (int i = 1; i < n; i++)
        {
            int x;
            scanf("%d",&x);
            while (!s.empty()&&s.top() <= x)
            {
                update(s.top(),x);
                s.pop();
            }
            if (!s.empty()) update(s.top(),x);
            //printf("%d\n",ans);
            s.push(x);      
        }
        printf("%d\n",ans);
    }
    
    
  • 1
    @ 2017-09-12 12:46:32

    想法基于优先队列,如果能理解优先队列的意义就很好想到怎么做了,还有位运算的优先级不知道坑了我几次了……

    #include <iostream>
    using namespace std;
    long a[100001];
    long x[100001];
    int main()
    {
        long n,i,top;
        long Max;
        cin>>n;
        for (i=1;i<=n;i++) cin>>a[i];
        top=0;
        Max=0;
        for (i=1;i<=n;i++){
            while (x[top]<=a[i] && top>0){
                if ((x[top]^a[i])>Max) Max=(x[top]^a[i]);
                top--;
            }
            if ((x[top]^a[i])>Max && top>0) Max=(x[top]^a[i]);
            top++;
            x[top]=a[i];
        }
        cout<<Max;
        return 0;
    }
    
  • -1
    @ 2018-08-08 14:50:15

    Linked list to simulate a priority stack

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>
    #include <ctype.h>
    struct node {
    int data;
    struct node *next;
    };

    typedef struct stack{
    struct node *top;
    int size;
    }_stack;

    _stack *new_stack();
    int show_stack(_stack *s);
    void push(_stack *s, int value);
    int pop(_stack *s);
    int is_empty(_stack *s);
    int max(int a, int b);

    int main() {
    _stack *s = new_stack();
    int n, i, fg, value, ans = -1;
    scanf("%d", &n);
    for (i = 0 ; i < n; i++) {
    scanf("%d", &value);

    if (is_empty(s)) {
    push(s, value);
    } else {
    if (show_stack(s) >= value) {
    ans = max(ans, show_stack(s) ^ value);
    push(s, value);
    } else {
    fg = false;
    while (!is_empty(s)) {
    if (value > show_stack(s)) {
    ans = max(ans, show_stack(s) ^ value);
    pop(s);
    } else {
    ans = max(ans, show_stack(s) ^ value);
    push(s, value);
    fg = true;
    break;
    }
    }
    if (fg == false) {
    push(s, value);
    }
    }
    }
    }
    printf("%d\n", ans);
    return 0;
    }

    int max(int a, int b) {
    return a > b ? a : b;
    }

    int is_empty(_stack *s) {
    return s->size > 0 ? 0 : 1;
    }

    int pop(_stack *s) {
    s->size--;

    struct node *curr = s->top;
    int value = curr->data;
    if (s->top->next == NULL) {
    free(curr);
    s->top = NULL;
    } else {
    s->top = s->top->next;
    free(curr);
    }

    return value;
    }

    void push(_stack *s, int value) {
    struct node *newnode = (struct node *) malloc(sizeof(struct node));
    newnode->data = value;
    newnode->next = s->top;
    s->top = newnode;
    s->size++;
    }

    _stack *new_stack() {
    _stack *s = (_stack *) malloc(sizeof(_stack));
    s->size = 0;
    s->top = NULL;
    return s;
    }

    int show_stack(_stack *s) {
    return s->top->data;
    }

  • -1
    @ 2016-06-11 21:05:29

    经典,单调性。
    ```c++
    #include<cstdio>
    #include<cstring>
    #include<stack>
    using namespace std;

    int w[100100],n,ans=-1;
    stack<int> S;

    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&w[i]);

    for(int i=1;i<=n;i++)
    {
    while(!S.empty()&&w[i]>S.top()) {ans=max(S.top()^w[i],ans);S.pop();}
    if(S.empty()||S.top()>w[i])
    {
    if(!S.empty()) ans=max(S.top()^w[i],ans);
    S.push(w[i]);
    }
    }
    printf("%d\n",ans);
    return 0;
    }
    ```

  • -1
    @ 2016-06-10 20:19:04

    分情况讨论一下就好。。。(原来以为是队列。。。后来发现只有ed在连续的变。。op只是在跳。。)
    #include<cstdio>
    #include<iostream>
    #define MAXN 100005
    using namespace std;

    int n;
    int num[MAXN];
    int q[MAXN],p;

    int poi=1;
    int ans=0;

    inline void swap(int &a,int &b)
    {int t=a;a=b;b=t;return ;}

    int main()
    {
    scanf("%d",&n);
    scanf("%d",&num[1]);
    int t1;
    for(int i=2;i<=n;i++)
    {
    scanf("%d",&t1);
    if(t1!=num[poi])
    num[++poi]=t1;
    }
    /*for(int i=1;i<=poi;i++)
    num[poi+i]=num[i];*/
    p=1;
    q[1]=num[1];
    for(int i=2;i<=poi;i++)
    {
    if(num[i]<q[p])
    ans=max(ans,num[i]^q[p]),q[++p]=num[i];
    else
    {
    while(num[i]>q[p])
    {
    ans=max(ans,num[i]^q[p]);
    p--;
    if(p<1)break;
    }
    q[++p]=num[i];
    if(p!=1)ans=max(ans,q[p]^q[p-1]);
    }
    }

    printf("%d\n",ans);

    return 0;
    }

  • -1
    @ 2016-04-01 00:55:12

    测试数据 #0: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 948 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 944 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #6: Accepted, time = 31 ms, mem = 944 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 944 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 948 KiB, score = 10
    测试数据 #9: Accepted, time = 46 ms, mem = 940 KiB, score = 10
    Accepted, time = 154 ms, mem = 948 KiB, score = 100
    http://www.cnblogs.com/Coolxxx/p/5343516.html

  • -1
    @ 2015-08-10 13:01:58

    讲一下

  • -1
    @ 2015-04-06 19:26:59

    能不能说一下对这个单调性的证明?

  • -1
    @ 2015-02-17 21:04:01

    使用数据结构“栈”解决这个问题。
    开一个栈,
    使得里面的元素从栈底到栈顶严格递减。
    具体操作:
    读入一个新的数时,
    将从栈顶开始的元素依次退栈,
    同时用异或值更新答案,
    直到栈顶元素大于新数为止,
    将新数入栈。
    最后得到的就是最终答案。
    var s:array[0..100010]of longint; n,i,r,x,ans:longint;
    begin

    readln(n);
    for i:=1 to n do
    begin
    read(x);
    while (r>0) and (s[r]<=x) do
    begin
    if (x xor s[r])>ans then ans:=x xor s[r];
    dec(r);
    end;
    if (x xor s[r])>ans then ans:=x xor s[r];
    inc(r);
    s[r]:=x;
    end;
    writeln(ans);
    end.

    • @ 2015-02-19 14:24:59

      orz......希望能解释一下原理

    • @ 2015-02-19 21:08:34

      把问题转化成:
      取两个数,满足这两个数大于它们之间的任何数,并且最大化异或值。

      随着新数的读入,
      之前那些不大于新数的都不可能再作为可行的左端点了(因为上面那个条件),
      需要把它们淘汰掉,
      而单调栈存的就是那些仍然能作为左端点的数,
      退栈的过程既完成了对不可行数的淘汰,
      又维持了栈中元素的单调递减,
      顺便用以新数为右端点的数对更新了答案。
      时间复杂度O(n),因为每个数最多进出栈一次。
      类似DP单调队列优化。

    • @ 2015-02-19 23:06:08

      orz……又涨姿势了,非常感谢

    • @ 2015-02-22 12:33:53

      orz

    • @ 2016-12-07 03:07:03

      orz

  • -2
    @ 2018-08-20 09:26:07
    #include<cstdio>
    #include<cstring>
    #include<stack>
    using namespace std;
    
    int w[100100],n,ans=-1;
    stack<int> S;
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
    
        for(int i=1;i<=n;i++)
        {
            while(!S.empty()&&w[i]>S.top()) {ans=max(S.top()^w[i],ans);S.pop();}
            if(S.empty()||S.top()>w[i])
            {
                if(!S.empty()) ans=max(S.top()^w[i],ans);
                S.push(w[i]);
            }
        }
        printf("%d\n",ans);
        return 0;
    }
    
  • -2
    @ 2016-12-07 04:15:22
    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <climits>  
    #include <cmath>
    #include <algorithm>
    #include <functional>
    #include <iterator>
    #include <cstring>
    #include <set>
    #include <vector>
    #include <queue>
    #include <list>
    #include <cctype>
    #include <string>
    #include <sstream>
    #include <stack>
    using namespace std;
    
    long long maxxx=0;
    
    int main()
    {
     long long n;
     cin>>n;
    
     long long w[100005];
    
     for(long long i=1;i<=n;i++){cin>>w[i];}
    
    //___________________________________________________________
    
      stack<long long> s;
      s.push(w[1]);
    
      for(long long i=2; i<=n; i++)
      {
       if(s.top()<=w[i])
        {
          while (s.top()<=w[i])
          {
            maxxx=max(maxxx,s.top()^w[i]);
            s.pop();
            if(s.empty()){break;}
          } 
          if(!s.empty()){maxxx=max(maxxx,s.top()^w[i]);}
          s.push(w[i]);     
        }
        else if(s.top()>w[i])
        {
          maxxx=max(maxxx,s.top()^w[i]);
          s.push(w[i]);     
        } 
      }
    
      cout<<maxxx;
    
      return 0;
    }
    
    
  • 1

信息

ID
1926
难度
5
分类
数据结构 | 队列 点击显示
标签
(无)
递交数
569
已通过
197
通过率
35%
上传者