「hihoCoder 1509」异或排序

发表于 | | 阅读次数:
字数统计: 491 字

Description

题目链接：hihoCoder 1509

给定一个长度为 $n$ 的非负整数序列 $a_i$

你需要求有多少个非负整数 $S$ 满足以下两个条件：

  1. $0\le S<2^{60}$
  2. 对于所有 $1\le i<n$，都有 $a_i\oplus S\le a_{i+1}\oplus S$（其中 $\oplus$ 为异或）

数据范围：$1\le n\le 50$，$0\le a_i<2^{60}$

Solution

对于两个数比较大小，我们回归它的本质：比较从最高位开始第一个不相同的位置。如果有两个数 $x$ 和 $y$，满足 $x\oplus S\le y\oplus S$。我们从他们的最高位开始考虑，$x$ 和 $y$ 在二进制下相同的数位和 $S$ 对应的位置异或的结果肯定一样，我们只关系第一个不相同的位置。打个比方：

那么 $x$ 和 $y$ 前 $4$ 位是相同的，第 $5$ 位是第一个不同的位置。$x$ 在这一位是 $0$，$y$ 在这一位是 $1$，如果要满足 $x\oplus S\le y\oplus S$，那么 $S$ 在这一位必须为 $1$。而我们注意到一旦有一位答案不同，那么 $S$ 接下来的位置就没有限制了。

当 $S$ 某一个位置的限制有冲突时就是无解情况，否则答案为 $2^{没有限制的位的个数}$。

时间复杂度：$O(n\log a_i)$

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
 
#include <cstdio>
#define fail return puts("0"),0
const int N=60;
int n,num[N];
long long now,las;
int main() {
    for(int i=59;i>=0;--i) num[i]=-1;
    scanf("%d",&n),--n;
    scanf("%lld",&las);
    for(;n--;las=now) {
        scanf("%lld",&now);
        for(int i=59;i>=0;--i) {
            if(((now>>i)&1)==((las>>i)&1)) continue;
            if((las>>i)&1) {
                if(num[i]==-1) num[i]=1;
                else if(num[i]==0) fail;
            }
            if((now>>i)&1) {
                if(num[i]==-1) num[i]=0;
                else if(num[i]==1) fail;
            }
            break;
        }
    }
    int ans=0;
    for(int i=59;~i;--i) if(num[i]==-1) ++ans;
    printf("%lld\n",1LL<<ans);
    return 0;
}
0%