题目链接
题意:
给定一个长度为 n 的非负整数序列 a[1..n]，你需要求有多少个非负整数 S 满足以下两个条件：
(1).0 ≤ S < 260
(2).对于所有 1 ≤ i < n ，有 (a[i] xor S) ≤ (a[i+1] xor S)
思路:
这个题目不是很难想,因为我们一看到异或啊啥的跟二进制有关系的东西,都会去想它的每一位的01关系,这个是肯定的,
对大部分都适用。
那么对于这个题目我们能想到的就是,要想ai^s<=ai+1 ^s，那么对于ai和ai+1,从高位到低位,如果两个数的二进制相同,
那么无论对s取什么值,结果都是一样的,对于二进制不同的位,我们要想满足等式的关系就必须使不同的这一位在ai+1中为1,
在ai中为0,否则不可能满足条件.只要确定了这一位,其余的不会影响结果.
所以我们只需要对每一对都找到二进制不同的最高位使其满足条件,如果矛盾,直接输出0,不矛盾,最后的结果就是
2^x (x为没有限制的位数)
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; ll a[111]; ll n; int cnt[66];//记录每一位的情况 int main() { Rl(n); CLR(cnt,-1); for(int i=1;i<=n;i++) Rl(a[i]); for(int i=1;i<n;i++) { ll x=a[i]; ll y=a[i+1]; for(int j=59;j>=0;j--) { if((x^y)&(1ll<<j))//找到两个数对应最高位不同处,剩下后面的不需要考虑. { if(x&(1ll<<j)) { if(cnt[j]==-1) cnt[j]=1; if(cnt[j]==0) { Pi(0); return 0; } } else { if(cnt[j]==-1) cnt[j]=0; if(cnt[j]==1) { Pi(0); return 0; } } break; } } } ll ans=1; for(int i=0;i<=59;i++) { if(cnt[i]==-1) ans<<=1; } Pl(ans); return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
