HihoCoder#1509:异或排序(二进制)

题意

题目链接

Sol

挺简单的吧。考虑两个元素什么时候不满足条件

设(a_i)与(a_i + 1)最高的不同位分别为0 1，显然(S)的这一位必须为(0)，否则这一位必须为(1)

剩下的就没有限制条件了

时间复杂度：(nlogn)??????!!!!!!

#include#define LL long long#define int long long  using namespace std;const int MAXN = 62, B = 60;inline int read() {    int x = 0, f = 1; char c = getchar();    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N;LL a[MAXN], mark[MAXN];main() {    N = read();    for(int i = 1; i <= N; i++) a[i] = read();    memset(mark, -1, sizeof(mark));    LL ans = 1ll << 60;    for(int i = 1; i <= N - 1; i++) {        for(int x = B; x >= 0; x--) {            int aa = (a[i] >> x) & 1, bb = (a[i + 1] >> x) & 1;            if(aa != bb) {                int now = aa < bb ? 1 : 2;                if((mark[x] != now) && (mark[x] != -1)) {puts("0"); exit(0);}                if(mark[x] == -1) ans /= 2;                mark[x] = now;                 break;            }        }           }    cout << ans;}   /**/