A 读不懂古神语的程序员不是一个合格的探险家

题意:交互题,给一个环,环上每个点的值为1 to 2^n的排列,保证从1出发不管顺时针还是逆时针总是单增到最大值。给2^n个机会询问某个点是多少,找到最大值的位置。

解:询问相邻两个点就可以知道最大值的方向,因此每次询问两个点,二分查找即可。细节稍微有点多因此来不及A掉,想补的但是密码条忘拿了又懒得重新写…

C 不会吧不会吧不会这道题还有同学答案错误吧

题意:提交答案题。给定一种分治一颗树的方式:每次遍历每条边,取分割后两颗新树的大小最接近的边删除。要求构造一棵树,使得按照你的分治方式,迭代层数小于上面的方法。

解:考虑长链+菊花。最优解肯定是把链剖开之后把链二分,菊花一个一个切。但是给定方法会把菊花和一大段链切走,就差了。

D 关于小方的爆款桌游还没面世就要夭折这回事

题意:Cram 游戏,初始给定n乘m的方块棋盘,每次填满一个日字格,问必胜情况。n保证偶数。

解:可以发现,当nm皆为偶数时,棋盘中心对称且没法在最中央放东西,因此后手只需要下在先手的对称位置即可获胜。若m为奇数,则先手者第一步下在棋盘中央即可把局面变成中心对称且不能放中央的情况,即先手必胜。

E 蟹老板的梦幻传送门真的能让宅男走出家门吗

题意:数轴上有n1000000个房子,放置两个传送门,效果是两个传送门之间距离为0,问最优放置方案下最远的两个房子的距离。

解:枚举左传送门管到的位置,设为i,则左传送门必定放在a[1]和a[i]的中间,右传送门同理。计算最远距离即可。(考试时题目的提示有误,坑读题,因此wa了4发)

LYF用了二分的方法。赛后证出只要把传送门放在两端即可。方法是研究传送门移动过程中某几个特殊点之间距离的最大值,应该写出来往这个方向推一推就能看出来吧?

由于没有密码条交不了题,所以B不补了