安阳市哪里做网站建设,公司起名字大全免费三字,广东网站建设制作,网站阵地建设管理正题 题目大意
一个长度为nnn的序列aaa。 对于一个数每秒可以将一个二进制位取反或异或aaa中的一个数。 qqq个询问#xff0c;询问从xxx变化到yyy最少要多少秒。 解题思路
对于一个x和yx和yx和y#xff0c;设 xxorwyx\ xor\ wyx xor wy ⇒xyxorw\Rightarrow xy\ xor\ w⇒xy…正题 题目大意
一个长度为nnn的序列aaa。 对于一个数每秒可以将一个二进制位取反或异或aaa中的一个数。 qqq个询问询问从xxx变化到yyy最少要多少秒。 解题思路
对于一个x和yx和yx和y设 xxorwyx\ xor\ wyx xor wy ⇒xyxorw\Rightarrow xy\ xor\ w⇒xy xor w xxorywx\ xor\ ywx xor yw 所以我们对于每个询问我们只需要求000变成www的距离就好了。 由于起点只有一个我们可以用bfsbfsbfs预处理000到www距离。 时间复杂度:O(220(n20)q)O(2^{20}(n20)q)O(220(n20)q) codecodecode
#includecstdio
#includequeue
#includecctype
#define MS 2097151
using namespace std;
int n,Q,a[25],v[MS10];
queueint q;
inline char Getchar()
{static char buf[100000],*p1buf100000,*pendbuf100000;if(p1pend){p1buf; pendbuffread(buf,1,100000,stdin);if (pendp1) return -1;}return *p1;
}
inline long long read()
{char c;int d1;long long f0;while(cGetchar(),!isdigit(c))if(c45)d-1;f(f3)(f1)c-48;while(cGetchar(),isdigit(c)) f(f3)(f1)c-48;return d*f;
}
inline void write(register long long x)
{if(x0)write(45),x-x;if(x9)write(x/10);putchar(x%1048);return;
}
void bfs()//预处理
{v[0]1;q.push(0);int y,i;while(!q.empty()){int xq.front();q.pop();for(i1;in;i)//异或a中的数{yx^a[i];if(!v[y]){v[y]v[x]1;q.push(y);}}for(i0;i20;i)//位数取反{yx^(1i);if(!v[y]){v[y]v[x]1;q.push(y);}}}
}
int main()
{freopen(data.in,r,stdin);freopen(data.out,w,stdout);nread();Qread();for(int i1;in;i)a[i]read();bfs();for(int i1;iQ;i) {int x,y,z;xread();yread();write(v[x^y]-1);putchar(\n);}
}
