@SovietPower
2018-09-04T14:44:36.000000Z
字数 6205
阅读 4623
正睿OI
由讲课orz
这还有一些不会的题orz
维护两个变量，和；枚举：
1. ：若，则，否则。
2. ：。
最后的为答案。因为绝对众数出现次数超过了一半。
https://www.cnblogs.com/SovietPower/p/9392651.html
...
交互库中有三个排好序的，长度分别为的数组。你需要求出所有元素中第小的数。你可以调用至多次询问某个数组中的第几个数的函数。
。
显然的做法是先枚举这个数在哪个数组中，再在三个数组中二分。这个次数是的。
我们如果每次确定一些数比第个数小，那我们可以直接将这些数删掉。
（可以假设数组是无限长的(补上INF)）这样每次访问三个数组的第个元素，把这个元素最小的数组的前个数删掉。这样每次缩小，当时我们就可以很容易得到答案。最多被缩小次变为，操作次数为。时直接询问三个数组前两个位置就可以得到答案。这样总操作次数不会超过。
https://www.cnblogs.com/SovietPower/p/9393308.html
有一个的网格，每个格子都有高度（每个点高度都不同）。你可以每次询问一个格子的高度，要求你找出任意一个山峰，它比它所有四连通的点都高。
询问次数不能超过。。
有一个每次询问周围所有点，然后选择最高点继续走的爬山算法。但是这样很容易卡掉，比如螺旋上升的山。
考虑答案可能会在哪。我们先求整个第列，找到其中高度最大的点，再询问它两边的山。若也比两边的山高，则就是一个山峰；否则在较高的点一侧一定存在一个山峰，这样我们成功地将问题缩小了一半。
如果我们行列交叉地二分，那么询问次数是。
有一个数组，下标为，你可以询问次两个数的和（这两个数的下标不能相同），求这个数组。
对前三个两两询问一次，可以算出，剩下的每次询问就可以了。
一个长的序列由组成，其中组成了一个单链表。链表从给定的开始，到结束。
保证若，则。
现在给定，你可以每次询问得到。你需要在次询问内求出大于等于的最小的数。
。
如果暴力的话就是从开始沿往后走。我们考虑缩短到要找的点的距离。
随机找个点，从其中最大的小于的位置开始走最多步。这样一个点不在前步的概率是，个点都没有在前步的点的概率就是。错误率很低。
有一个大小为的集合，元素两两不同且在内。你可以询问不超过次，每次询问你给出，交互库会返回是(TAK)否(NIE)为真。求任意两个一定在集合中出现过的数。
。
考虑对区间二分，若Check(mid,mid+1)==1，则区间中一定存在一个数；否则区间中一定存在一个数。这样用次可以确定一个数。
对于第二个数，可以在和中分别二分。
https://www.cnblogs.com/SovietPower/p/9383084.html
有一个长为的二进制串，保证都存在。你可以询问不超过次，每次询问你给出一个长为的二进制串，交互库会返回你的串和目标串的不同位的数目。求任意一个和的位置。
。
通过和就可以判断出第一个数是什么。然后二分，对每个区间判断是否全为，就可以找到另一个了。
https://www.cnblogs.com/SovietPower/p/9543866.html
一个的非负整数矩阵，保证。现在你要对每个求(每一行除的最小值)。你可以进行不超过次询问，每次询问你给出下标集合，交互库会对每个返回(每一行给出列的最小值)。
。
常见思路：即至少有一位不同。
对每一位枚举，求所有下标该位为的最小值。对于每个把与其某位不同的数全部取即可。
https://www.cnblogs.com/SovietPower/p/9544472.html
有一个长为的序列，其中有两个元素为，其余全为。你可以进行次询问，每次询问你给出一个下标集合，交互库会返回这些元素的异或和。给定，你需要求出两个的下标。
。
对连续区间询问得到的结果只有那么几种，可以直接判断的个数的奇偶性。但是区分不出来该区间有0个还是2个。
两个的下标不同。我们可以借此对下标某一位是计算其异或和，若不同，则两个的下标在这一位上不同。最后我们能得到两个下标的异或和。
找一个在某位不同且元素个数最少的位置，在较小的集合内（大小）二分，这里面只有一个，就可以得到它的位置，异或之前的和就得到另一个。次数正好。
当然也可以不二分。任找该位不同的一位，然后枚举不等于的每位，我们要判断是否有一个（另一个可以直接通过之前在该位的询问得到）在该位上是。只枚举位为1的下标，可以保证只有一个并判断出这个是否在这位上是，因为询问可以确定其中是否有。
https://www.cnblogs.com/SovietPower/p/9546002.html
有两个同构的图，有对应关系，在两个图中分别有一个集合，在第一个图中该集合是独立集，在第二个图中你该集合是团。你可以询问不超过次某一个点在另一个图中的编号，你需要确定两个集合有没有交。
如果有交，交的大小只可能为。
...
有一棵高度为的满二叉树，点从到编号（无序）。每次你可以询问一个点的编号，交互库会返回其所有邻接点的编号。你需要在次询问内确定这棵树根节点的编号。
。
考虑随便问一个点，然后任意找个相邻点走。这样如果不往回走，最差情况下是一直走到一个叶子，这样找走两遍，扩展出一条叶子到叶子的链，就可以往上扩展了。这样最多扩展个点，但是确定根节点就够了，即个。
还是不行。在深度比较浅时代价会比较高，但是深度浅了我们离根节点就更近。所以在离根足够近（距离为）直接BFS。这样代价为，但是最后一个点不需要查知道了，代价为。
思路很好理解，但是代码好难写啊。。弃疗了。参考个吧。orzyanQval.
要对初始点DFS两次，不管路径如何，我们记下两条路径经过点数c1,c2，其深度就是(c1+c2)/2+1。如果有一次是向根节点延伸(c1!=c2)，就可以直接跳到经过路径上最靠近根的点。
之后保证每次向上走，用之前的深度和新路径的点数同样可以跳。最后手动BFS。
https://www.cnblogs.com/SovietPower/p/9548465.html
有个的二次函数，。你需要通过不超过次询问求出。
每次询问你给出，交互库会返回点值最小的的三个参数。
。
先询问，然后找当前值最大的继续询问。
维护抛物线段，找到个不同的抛物线就停。这样一定能找到答案、
...
有一棵带边权树，有个叶子节点和若干非叶节点，保证非叶节点度数至少为。一个点是中心当且仅当它到最远点的距离最小，一个点是稳定的当且仅当把它删掉后所有子树的大小都不含超过个原先的叶节点。你可以进行不超过次询问，每次可以询问两个叶节点间的距离。你需要求出中心点到最远点的距离并确定是否存在稳定的中心节点。
。
一：树的中心一定在直径的中点上，先找直径。假设直径为AB，先求距任意一点S的最远点A，可以直接用个询问求S到每个叶子的距离；然后再用次询问求A到每个叶子的距离找出B。
后面记不太清了，大体思路，可能有点小问题。
找到中心后，我们要对每个叶子进行定位以确定删掉中心后的子树叶子个数。只需要在直径上相对中心的位置，再用次询问求出B到每个叶子的距离就可以了。这部分总共。
二：先特判有两个中心的情况，然后我们要求中心最大子树的叶子数。
通过两次查询比较到中点的距离，我们可以知道两个叶子是否属于同一棵子树。这样可以通过查找绝对众数来找到出现次数超过一半的子树。但是到最后时我们不确定当前答案大小是否超过了一半，还需要次操作检验。这样找数次检验次，一共。
考虑对第一步优化。我们需要叶子的位置，但是并不需要具体的B到每个点的位置，因为S一定在中心的一侧，只要有了S和A到每个叶子的距离是可以确定其相对位置的。这样从B的枚举就不用了，操作次数降为。（更具体忘了）
至于第二步，想办法把没用的优化掉：(枚举)查找时，若，不进行查询直接赋值；时，把的贡献加给，检查时跳过。而不会有负数，所以这两种情况至少有次。这样就优化到总共次了。
有一个数据结构维护集合。你需要先插入一个位二进制整数集合，之后进行若干次询问，每次查询一个数是否在集合内。现在有一个长为的置换，数据结构会在插入后查询前把每个数二进制位的顺序按照变换。你可以插入不超过个元素并查询不超过个元素，求。
。
（具体忘了，不想想了）
如果询问可以查某位最终的变换位置。
考虑对整体二分，因为对左边区间的查询不影响右边，所以左右的询问可以一起进行。
有一张个点的图。M每次询问，你需要回答图中间是否有边。如果M可以用次询问确定图中所有点是否连通，M赢；否则你赢。你可以根据M之前的询问任意改变图的连边情况。实现函数回答每次询问，使得你赢。
。
挺有意思的。
既不能早告诉当前点间右边(右边就不用问当前点了，问一个连通块的就行了)，也不能一直说没边。不到最后一刻不告诉她就行了。
如果对点的询问次数不足或次（看每条边统计编号小的还是大的），就不连边。
https://www.cnblogs.com/SovietPower/p/9549426.html
以下懵逼，各种多项式。反正这东西我不考。
操作一二可以调用多次运算，询问只能一次，总共可以调用不超过次运算。
Treap。每个节点维护右子树的和和中间到左边的后缀。期望平衡。
加密时把位看做一个次多项式，每次传个数据，相当于点。插值。