牛客入门刷题
毒瘤XOR
题目链接
注意点：本题i和j容易弄混，请在脑子清醒状态下写题。
解题思路：
既然给出所有元素要去求l-r的解，我们首先应当看到异或的话，是最好是最终答案里头的1带的越多越好，由于X跟其他元素异或，先看单个元素吧，举个例子：10001，那么就要01110来对应来得到最大的数，既然这样，王多个数推，就是要在l-r这个区间内能变成1最多的，即，如果区间内的所有数的32位的某一位，1多于0，那么x的这一位就需要是0来让更多的1出现，相反同理。那么好，得出结论，是要找让所有数字32位（实际是31位，最后一位好像是符号符）的1的数量统计出来*2看跟l到r的距离大小比较，从而确定这个位应当是0还是1。直接用前缀和来做不然在q循环里在循环可能TLE，前n个数的31位每一位上1的数量。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int main(){ int n;cin>>n;int v[N];int ps[N][40];for(int i=1;i<=n;i++)cin>>v[i];for(int j=1;j<=n;j++){ //这里上下俩个循环可以倒过来，不影响，就是注意i和j的设置for(int i=0;i<31;i++){ps[j][i]=ps[j-1][i];if((v[j]>>i)&1){ps[j][i]++;}}}int q;cin>>q;int l,r;for(int i=1;i<=q;i++){cin>>l>>r;int x=0;for(int j=0;j<31;j++){if((ps[r][j]-ps[l-1][j])*2 < (r-l+1)){x|=(1<<j);}}cout<<x<<endl;}return 0;
}兔子的区间密码
题目链接
转换成二进制来看，哦才能够最大位二进制往后看，遇到第一个不一样的开始，就都可以变成1了，比如说101010111和101010010，那么最后4位就可以变成1111，前面相同的就都是0，至于为什么，因为前面但凡出现一个不一样的，就要脱轨了，一定在原来这个范围之外了。这题需要i注意的一点是他的范围是1e18，转换成二进制需要是64位的，所以遍历二进制的时候从0到61.
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int main(){ int n;cin>>n;while(n--){ll l,r,ans=0,pos=-1,flag=0;scanf("%lld %lld",&l,&r);for(ll i=63;i>=0;i--){if(!flag&&(l>>i)&1==1||(r>>i)&1==1)flag=1;if(!flag)continue;if(flag){if(((l>>i)&1)!=((r>>i)&1)){//cout<<i<<endl;pos=i;break;}//else{pos=i;break;}} }for(ll i=pos;i>=0;i--){ans|=1ll<<i;} printf("%lld\n",ans);}return 0;
}