大学生网站建设例题答案,国内的优秀设计网站,在哪可以做网站,有效的引流推广方法正题 题目大意
有nnn堆石子#xff0c;每次选择一个区间博弈#xff0c;先手必须先取最右边的石子堆。
每次询问(r,a,b)(r,a,b)(r,a,b)表示在a∼ba\sim ba∼b中选择一个数lll。要求使用l∼rl\sim rl∼r这个区间的石子进行博弈#xff0c;然后若先手必胜输出最右边的石子需…正题 题目大意
有nnn堆石子每次选择一个区间博弈先手必须先取最右边的石子堆。
每次询问(r,a,b)(r,a,b)(r,a,b)表示在a∼ba\sim ba∼b中选择一个数lll。要求使用l∼rl\sim rl∼r这个区间的石子进行博弈然后若先手必胜输出最右边的石子需取的最大石子个数并让石子堆减去这个数。若先手必败输出−1-1−1 解题思路
首先这是一个NIMNIMNIM博弈若alxoral1xoral2xor...xorar0a_l\ xor\ a_{l1}\ xor\ a_{l2}\ xor...\ xor\ a_r0al xor al1 xor al2 xor... xor ar0那么先手必败。
那如果alxoral1xoral2xor...xorar−1xa_l\ xor\ a_{l1}\ xor\ a_{l2}\ xor...\ xor\ a_{r-1}xal xor al1 xor al2 xor... xor ar−1x且x≤arx\leq a_rx≤ar那么我们可以从ara_rar中取走ar−xa_r-xar−x个石头然后使得arxa_rxarx那么这样轮到后手开始时所以的异或起来就为0了。
那么我们如何求最小值呢分块套Trie暴力
因为数据水所以能够过不过需要加两个优化
当brbrbr时直接让lll取rrr这个十分显然因为要使异或和最小所以自己异或自己就是0当ar0a_r0ar0时输出-1依旧十分显然
日后可能会将正解补上有生之年 codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N110000;
int n,w[N],m;
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,w[i]);scanf(%d,m);while(m--){int x0,ans2147483647,a,b,r;scanf(%d%d%d,r,a,b);if(w[r]0){printf(-1\n);continue;}if(rb){printf(%d\n,w[r]);w[r]0;continue;}for(int ir-1;ia;i--){xx^w[i];if(ib) ansmin(ans,x);}if(w[r]-ans0) printf(%d\n,w[r]-ans),w[r]ans;else printf(-1\n);}
}
