什么是网站的自适应,装修室内设计培训学校,北京市建设工程信息网交易网站,百度搜索 相关网站【每日一题】7月3日精讲—毒瘤xor
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
Special Judge, 64bit IO Format: %lld文章目录题目描述题解#xff1a;代码#xff1a;题目描述 输入描述: 第一行一个整…【每日一题】7月3日精讲—毒瘤xor
时间限制C/C 1秒其他语言2秒
空间限制C/C 32768K其他语言65536K
Special Judge, 64bit IO Format: %lld文章目录题目描述题解代码题目描述 输入描述: 第一行一个整数N表示序列的长度 第二行N个整数表示序列内的元素 第三行一个整数q表示询问的个数 接下来q行每行两个整数[L, R]表示询问的区间 输出描述: 输出q行每行一个整数表示答案 若有多组可行解请输出较小的解 示例1 输入 复制
5
4 78 12 1 3
3
2 5
1 4
3 3输出
2147483632
2147483635
2147483635备注:
对于30%的数据n , q ≤ 10
对于60%的数据n , q ≤ 1000
对于100%的数据n, q ≤ 10^5
保证ai 2^31题解
很久没有遇到异或的题了 先讲下异或1 ^ 1 0 , 0 ^ 0 0,1 ^ 0 1,0 ^ 1 1 相同为0不同为1 异或是两个数二进制状态下相同数位进行操作 我们要找一个x使得x ^ a[i]的和最大那我们就尽量使x与a[i]的相同位数异或后为1这样就最大 a[i]是一个数组所以我们就求这个数组里每个数的二进制状态下每一位0和1的个数比如说数组有n个数其中b个数二进制状态下第一位是0剩下n-b个数二进制状态下第一位是1如果bn-b,那我们就使X二进制的第一位是1就是和最多情况的数呈相反这样异或出来才是1 然后是第二位依次类推最后我们就得到X的二进制状态转化成十进制输出即可 因为有多轮询问所以我们可以用前缀和来处理每一位为1的数 bool w((a[i]j)1);//判断第j位是0是1 sum[i][j](sum[i-1][j]w);//前缀和进行累加代码
#includebits/stdc.h
using namespace std;
const int maxn1e54;
typedef long long ll;
ll a[maxn];
int sum[maxn][40];
int main()
{int n;cinn;for(int i1;in;i){cina[i];}for(int i1;in;i){for(int j0;j31;j){bool w((a[i]j)1);//判断第j位是0是1 sum[i][j](sum[i-1][j]w);}}int q;cinq;int tot0;while(q--){tot0;int l,r;cinlr;for(int j0;j31;j){if(sum[r][j]-sum[l-1][j] ( (r-l)/21) )//当这一位0居多时X选为1 tot(1j); }couttotendl; }
}
