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

题意

Sol

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

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

剩下的就没有限制条件了

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

#include<bits/stdc++.h>

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

}

/*

*/

巴特西

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

题意

Sol

最新文章

热门文章