题解 - Vijos

11

xudf6 LV 8 @ 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

Sky1231 (sky1231) LV 10 @ 2020-12-03 15:16:46

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
    
    int n,ans;
    deque<int> w,sta;
    
    void main()
    {
        scanf("%d",&n);
        w.resize(n);
        for (int i=0;i<n;i++)
            scanf("%d",&w[i]);
        ans=oo_min;
        sta.resize(1,w[0]);
        for (int i=1;i<n;i++)
        {
            while (sta.size()>0)
                if (sta[sta.size()-1]<=w[i])
                {
                    ans=max(ans,sta[sta.size()-1]^w[i]);
                    sta.resize(sta.size()-1);
                }
                else
                    break;
            if (sta.size()>0)
                ans=max(ans,sta[sta.size()-1]^w[i]);
            sta.push_back(w[i]);
        }
        printf("%d\n",ans);
    }
}

int main()
{
    dts::main();
}

1

WIZeaz (dg_zyh) LV 8 @ 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;
}

0

chenyiming LV 7 @ 2021-06-05 17:00:04

维护一个单调递减的序列。假设现在的序列是a,b,c...

首先a,b的异或是可能产生最终的结果的。

　　如果a<b,来了一个c，

　　　　如果b<c,则a,c这对组合是永远不可能的，也就是说a是可以删除的。

　　　　如果b>c,则如果a>c,abc的最大值也是a,b，而a,b已经求过了所以a是可以删除的。

　　如果a>b,来了一个c，

　　　　如果b>c,则b，c是可能产生最终的结果的

　　　　如果b<c且c<a,则a,c是有可能的，所以a不能删除

　　　　如果b<c且c>a,则a,c也是有可能的，所以a不能删除。

综上所述，只有a<b这种情况a是可以删除的，也就是说在增长的序列中，无论后面来了什么数，都不可能与当前最大值前面的值产生最终的结果

#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);
}

0

chenyiming LV 7 @ 2021-06-05 16:58:19

维护一个单调递减的序列。假设现在的序列是a,b,c...

首先a,b的异或是可能产生最终的结果的。

　　如果a<b,来了一个c，

　　　　如果b<c,则a,c这对组合是永远不可能的，也就是说a是可以删除的。

　　　　如果b>c,则如果a>c,abc的最大值也是a,b，而a,b已经求过了所以a是可以删除的。

　　如果a>b,来了一个c，

　　　　如果b>c,则b，c是可能产生最终的结果的

　　　　如果b<c且c<a,则a,c是有可能的，所以a不能删除

　　　　如果b<c且c>a,则a,c也是有可能的，所以a不能删除。

综上所述，只有a<b这种情况a是可以删除的，也就是说在增长的序列中，无论后面来了什么数，都不可能与当前最大值前面的值产生最终的结果。
前方高能，贴代码了：
#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

heyifan LV 10 @ 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

qig159357 LV 8 @ 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

everforever LV 10 @ 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

coolxxx LV 9 @ 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

AZHENG LV 6 @ 2015-08-10 13:01:58

讲一下

-1

民逗公知 LV 8 @ 2015-04-06 19:26:59

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

-1

Glaceon08 LV 9 @ 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.

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

orz......希望能解释一下原理
Glaceon08 @ 2015-02-19 21:08:34

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

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

orz……又涨姿势了，非常感谢
q234rty @ 2015-02-22 12:33:53

orz
5661lhr @ 2016-12-07 03:07:03

orz

-2

PowderHan LV 10 @ 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

5661lhr LV 8 @ 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;
}

题解

14 条题解

紫色的手链

信息

状态

开发

支持

题解

14 条题解

紫色的手链

信息

状态

开发

支持

还没有账户？

登录