前：ay1下午——交互

衢州
2018.7.28
2018.7.29

T1 Majority

绝对众数
解释，答案的次数大于一半。

T2 US Open 2018 Train Tracking

?

T3 UR #4 元旦激光炮

(k - 1) / 3

T4 寻找山峰

竖着询问中间的一条，取出最大的，判断两边是否比它大，
如果是：找到了，
不是：最大的数的左边大，那么在左边横着找中间的一条最大的，否则在右边。
大的一侧一定有一个山峰，为什么？

T5 Technocup 7 2017 1 ER1 C. Guess the Array

a1,a2,a3解方程。
a1+ai->求出ai

T6 AIM Tech Round 4 B. Interactive Lowerbound

随机1000个点，往后跳1000次。

没看懂题意。

T7 CF 810 D Glad to see you

举例：集合为（4，12），查询(x=5,y=10)，返回[1<=2]

题解+代码 SovietPower

怎么确保能找到答案。我们可以将（1～n）分成两份（1～mid）（mid+1～r），显然要猜的数肯定是在这两个区间内。
然后怎么判断我们可以找mid和mid+1两个数来判断，如果|mid-a|<=|mid+1-b|，那么显然要猜的数肯定是mid或者mid的左侧。如果|mid-a|>|mid+1-b|很显然要猜的数肯定是mid+1或者mid+1的右侧然后就是二分，根据题目的回答进行二分

T8 CF862 D Mahmoud and b Ehab and the binary string

T9 CF744 B Hongcow's Game

整体二分
按位分类？

T10 CF 835 E The penguin's game

题解
按位分类
枚举y只有两个，而且坐标不同。
枚举坐标的每一位，分成两个集合：当前这一位，坐标二进制为0的为一个集合，坐标二进制为1的为一个集合。查询一个集合的异或和，然后自然的得知另一个集合的异或和。
此时，根据两个和，可以判断两个y是否在同一集合里，还是分别在两个集合里。
如果在同一集合里，跳过。
否则，说明两个y的集合的坐标二进制在这一位不同，将不同的二进制位记下，放到diff集合里，
然后在diff集合里找到最小的数（两个y坐标的二进制，最小的一位不同的数）。可以二分出一个y的位置。设当前找到的二进制位是1010000，是第3个1，因为第3位为1的集合里只有一个y，所以可以二分出y的位置。
1010000~1011111，在这里二分。然后另一个y就是异或上diff

T11 Effulgence

一个图和这个图的重构图。还有原图中的点独立集A，重构图的团B。
团：任意两点有边，

重构图不影响点的度数，只修改了编号。

结论：最多一个点相交。

所以每次在A中找度数最大的，B中找度数最小的。
如果是答案，完成。
否则：这两个点中一定会有大于n/2的，所以可以将点数缩小一半。问题规模缩小一半。

T12 Good Bye 2016 F New Year and Finding Roots

二叉树，找根。

找长度为4的链，然后从4的父节点遍历。最后一个点不需要询问，总共16次。

T13 CNTTTT 2015 Flea

T14 IOI2015 towns

T15 IOI2016 Messy

对p进行整体二分。
xxxx xxxx
xxxx|xxxx
然后分别求出左边，右边对应那些数，集合。

依次插入
01111111
10111111
11011111
11101111
询问
01111111
10111111
11011111
11101111
11110111
11111011
11111110
哪些出现了，就是左边对应的集合。
二分下去。

7.29

T16

T17 IOI 2014 Game

n个点的无向图，A每次询问给出两个点之间是否有边，B每次回答，必须让A询问n*(n-1)/2次，可以指定点之间是否有边，但不能与前面的违背。

T16 secret

线段树，维护每段的中点，向左的和，和向右的和。

T17

2操作改为 查询历史版本的和。
每个点维护后缀。

T18

每18位传29位。

T19 us camp 16

T20 Coins

坑：按位分类