在此处输入标题

未分类

day3上午

刷题班题解

题解

t1

n,m,都是奇数，那么，先手必败
否则先手必胜。

推出的图

t2

二进制数
部分分1：
k=1 找两个数使最高位异或==1，排序找到最大的，
分治
将所有的数分成两部分，一部分的最高的位为1，另一部分最高位为0；
查找两部分是否都有数，判断是否可以
1023
可以开一个数组记录到1023的数有多少个。
for (int a=0; a<1024; ++a)
for (int b=0; b<1024; ++b)
cnt2[a^b] = cnt[a]cnt[b];
正解：
trie树+二分
二进制trie树。右儿子1，左儿子0
前k大的和，先求先k大的数。
之后把比k大的数加起来。
给定序列：a1,a2,a3...an
两两异或：b1,b2,b2......bn(n-1)/2
二分可以求出第k大的 在b中，开不下b
二分v
ai*aj -> b　　 i <ｊ
枚举i，x = ai
有多少j x^aj > v

x = 0011
v = 0011

aj^x最高位==1，那么找跟的右子树的节点有多少。
aj^x最高位==0，aj = 0????...，进入左儿子

看次高位，==1 ，+右子树的节点
==0进入左子树 aj = 00???...

然后第三位异或后一定只能是1，aj的第三位一定是0，进入左儿子。

T3

做一颗线段树维护区间前10大
合并：最暴力的方法：暴力排序抽出20个数（左右儿子的前10大），取前10大
区间前10大要么是左边的最大值
要么是右边的最大值，那么模仿归并排序，每次取出两个指针的最大值
，那么就可以线性求前10
修改：带修改前10大；要是修改区间就是直接修改前k大把节点信息改成结构体
就可以搞了

在此输入正文