day3上午

清北学堂--刷题班

题解

t1

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

t2

二进制数
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

1、30分大暴力，区间的
取出来排序，输出第k大
2、k=1,求区间的最大值，区间修改，
3、没有修改操作：主席树可以做，
可以离线操作，莫队+堆
4、正解，线段树，
所有询问k<=10
维护区间前十大
合并：
左区间的前十大l1,l2,l3...
右区间的前十大r1,r2,r3...
最暴力的方法取出排序，放入
双指针：（归并排序的）比较，线性。
修改：
全都加v
ps：query的函数返回10个值，返回结构体（节点->结构体）
可以在结构体中重载'+'（作用是合并），pushup函数不用不用不用变了。

突然的思路（没证明，），查询[l,r]的第k大，查询最大的maxnum,及其位置pos，然后在[l,pos-1],[pos+1,r]同样查询最大值，乱想的。。。

解题报告

t1

t2

以后要多读两遍题目，推一下样例。
第一遍读，读错了，以为给定n*(n-1)/2个异或之后的数，异或运算很麻烦，也没推样例，然后不会做，100也不会，先做第三题了
剩下半小时回来看第二题，也没读题，直接推结论，，。。。直到发现交卷前再也写不出了之后，，，

之后考完发现读错了题目，，，
原题：给定n个数，

t3