2021.5.12 asdfas
K
签到
C
签到
H
签到
D
交互
题意：
x和y都在0到1e6之间的平面上有n<=7个宝藏（整点上），每次你询问时给定一个平面上的一个点，交互程序会给出最近的宝藏的距离的平方。要求在1000次询问以内找到所有点。
ZRC解：
首先询问第一行的连续八个点，则由抽屉原理，八个点中至少有两个对应的是同一个宝藏。且由两个点和各自距离可以计算出可能的宝藏位置。枚举八个点的所有点对，询问可能的宝藏位置；找到第一个后以同样方式继续寻找。
题解1：
相邻的两个点有很大概率对应的是同一个宝藏。随机选取相邻点不断重复这个过程。
题解2：
随机撒点，尝试探测所有对应的格点。
题解3：
用一些数据结构和一些我没看懂的做法
F
题意：
数轴上有n1e5架drone，他们有各自的速度和出发点，一旦他们相遇就会双双坠机。问最后能留多少飞机。
LYF&ZRC解：
考虑画一张x-t图像，可以发现，相撞的drone一定是在当前未相撞drone中出发点相邻的两个。用优先队列维护相邻两drone的相撞时间即可。每次两架撞了就在链表中删除，在优先队列中加入新的相邻drone的相撞时间。同时若优先队列顶上取出的相撞事件包含了已坠机drone，那就忽略它。
A
DP
补E
博弈论壳子，随机题内核
题意：
n1e5大小的棋盘
Alice Bob，每一轮能在种操作中选一个：
- 把棋子走两步，并把路上的对方棋子都吃掉
- 将棋子任意移动到棋盘任何位置
- 不走
棋子的走法给定，有n种（例：2 1即可理解为马向其中一个方向的走法）。同时给定Alice和Bob的位置，问谁胜 或是平局。平局需要输出Alice这一步瞬移到的位置
解：
1.首先，如果走两步能吃，那就是Alice胜；
2.否则，判断能否找到一个Bob两步走不到的地方。
问题1很好做，将Alice走一步能到的地方(最多n个点)与能一步吃到Bob的地方(同样最多n个点)都求出来并比较是否有重复即可。
问题2乍一看没有什么办法
但是，对稍大的数据手推即可发现，由于走法只有n种，在n大时走两步能到的地方占盘面的比例很小。因此，对于小数据搜索答案；对于大数据，随机k次，问每个点是否能被Bob两步走到。题解说盘面上只有约二分之一的点能被吃到，所以找平局点的操作期望只会进行不到2次。