[WC2018]即时战略

题目大意

这是一道非常有趣的题,也是我第一次在现场遇到的交互题。
给定一棵树(选手并不知道),一开始只有1号点是已知的。交互库中提供了一个函数explore(x,y),给这个函数一个已知节点x和(未知)节点y(x!=y),它会返回x到y的链上的第二个点,如果返回的点未知,可以让它变为已知。
要求调用<=T次explore函数,使得树上所有点都变为已知节点。
具体看题目链接
Windows的同学建议看LOJ的题面

Solution

赛场上,我只会写暴力,好像连一条链的都写挂了,然后成功拿到25分的好成绩(大众分70),然后离Ag线差了一分(此处应有加热饱和$NaHCO_3$溶液的声音,咕咕咕咕咕咕咕……)。
但是树的形态都不知道,究竟该怎么做呢?

动态点分治

如果给定一个未知节点,能够找到在树上离它最近的已知节点的话,那么就可以把一个未知点变为已知点了。怎么找呢?
类似于点分治的方法,先以整棵树的重心,看这个未知点在哪棵子树中,再以这棵子树的重心为子树的根……
然后一个未知点变为已知点,就相当于加入一个点。这就是动态维护点分树,裸的紫荆花之恋了。代码也很好写。

LCT

还有一种做法。就是考虑轻重链剖分。从包含1号节点的重链开始。一定可以二分找到一条重链与选择的未知点到根的路径相交最下面的节点,记为u。如果选择的节点p,二分到一个答案x,如果explore(x,p)在x的上方,那么u也在x上方,否则u在x下方。到最后一条重链找到的u,就是要找的离p最近的已知点了。
然后把一个未知点改为已知点后,也相当于在树上加一个点。要维护加点的轻重链剖分,只需要LCT就可以。代码也很短。
关于询问次数的复杂度,看起来要在每条重链上二分,是$O(nlog^2)$的。但只要新加入一个节点后都access一下,由于在所有重链上二分的复杂度和access的复杂度是完全相同的,所以总询问数也是O(nlogn)的。


Tips:由于第9到第13个点(一条链)过于毒瘤,比一棵树的限制紧很多,所以一条链的要分开来写(暂时未写)。
不加特判的话可以拿到80~85的好成绩。
UPD:然后特判一条链的情况,只要记录下已知链的左右端点。直接随机找到一个未知点,把这个到已知点的端点的那条未知链都标记为已知。询问次数复杂度为$O(n+\ln n)$,只有$\frac{144}{10000}$的错误率。

Code

4 条评论
  1. My husband and i were so happy when Raymond managed to deal with his investigations using the precious recommendations he discovered out of the web pages. It is now and again perplexing to just be giving for free instructions some other people could have been making money from. Therefore we fully grasp we need the writer to be grateful to because of that. Those illustrations you’ve made, the straightforward site menu, the relationships your site make it possible to instill – it’s got many sensational, and it is helping our son in addition to us feel that this idea is thrilling, and that is tremendously mandatory. Thanks for all!

  2. I precisely needed to thank you so much all over again. I’m not certain the things I would’ve gone through in the absence of the entire creative concepts discussed by you concerning that area of interest. It previously was a frightful matter for me, but understanding the very specialised strategy you resolved that took me to weep over contentment. I am just grateful for your information and trust you realize what a powerful job you were putting in training other individuals through the use of your web blog. Probably you have never met any of us.

  3. I want to show my thanks to this writer just for rescuing me from this particular situation. As a result of checking throughout the search engines and obtaining advice which were not beneficial, I was thinking my entire life was well over. Being alive without the solutions to the issues you’ve sorted out by means of the report is a critical case, and the kind that would have in a wrong way affected my entire career if I hadn’t discovered the website. Your good knowledge and kindness in taking care of all areas was excellent. I am not sure what I would’ve done if I had not discovered such a point like this. I can at this time relish my future. Thanks a lot very much for the reliable and result oriented help. I won’t be reluctant to recommend the blog to anybody who should have guidance about this situation.

  4. Thank you a lot for providing individuals with an exceptionally superb possiblity to read critical reviews from this website. It is always very enjoyable and full of a lot of fun for me and my office colleagues to search the blog the equivalent of three times per week to learn the fresh stuff you have got. And of course, I’m so always astounded for the terrific tips and hints you serve. Selected two points in this article are in truth the most effective I have had.

发表一条评论