Competitive Programming►Problems

Codeforces 280B - Maximum Xor Secondary

Link: http://codeforces.com/problemset/problem/280/B

我的作法頗奇怪的，貼出來分享一下
這題可以用stack單調性O(n)解決，聽起來還滿簡單的，不過我想到的方法不太一樣(反正這題應該有很多種解法)

作法大概是把數字看成二進位，計算它們的有多少位元，要xor的兩個數字的位元數一定不同(除非所有數字位元數相同)，而且其中一個必有最大位元數，暴力弄一弄複雜度還是O(n) (見27行以後)
所有數字位元數相同時，其實可以處理成位元數不同 (見14~25行)

AC submission: http://codeforces.com/contest/280/submission/12995655

AC code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;
int a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];

    int k=1;
    for(int i=0;i<n;i++)
        while(k<=a[i])
            k<<=1;
    int s1=-1,s2=-1;
    for(int i=0;i<n;i++)
        s1&=a[i], s2&=~a[i];
    int m=0;
    for(k>>=1;((s1|s2)&k)>0;k>>=1)
        if(s1&k) m|=k;
    for(int i=0;i<n;i++)
        a[i]^=m;

    int ans=-1;
    for(int i=0;i<n;i++)
        if(a[i]>=k)
        {
            int tmx=0,j;
            for(j=i-1;j>=0&&a[j]<k;j--)
            {
                tmx=max(tmx,a[j]);
                ans=max(ans,a[i]^tmx);
            }
            tmx=0;
            for(j=i+1;j<n&&a[j]<k;j++)
            {
                tmx=max(tmx,a[j]);
                ans=max(ans,a[i]^tmx);
            }
            i=j-1;
        }
    cout<<ans<<'\n';
}