JOI2018春季合宿communication题简要做法

Airline Route Map

简要题意

通信题。

Alice得到一个带标号的个点的无向图,希望发送给Bob。

Alice只能发送一个不带标号的无向图给Bob,并且这个无向图只能比原图多最多个点。

题目分析

我的初步想法是原图保持不动,用多出来的个点给他们做标记。

发现大约是的级别,而且额外多

可以考虑其中个点和原图的点的二进制位相连,剩下两个点给这个点打标记。

假设这个点命名,剩下两个叫

为了直接辨认所有点,我先把和所有点相连,再把相连。

这个时候的度数只有可以考虑利用度数直接找到它。不过要考虑误判,原图号点的度数可能都是,给他们做一下映射,连二进制位的时候把他们看作点连,保证他们度数至少是

这时候我们可以判断出,紧接着得到和所有,但是并不知道的顺序。

单独拉出来看作一个特殊点,接着把顺次连成一条链。为了辨认特殊点和链首,我把连了起来,这样在所有点构成的子图中,拥有度数的点一定是,没有和相连的是,从开始dfs得到

最后通过把原编号还原,注意把映射回去。

代码

Alice:

 

Bob:

 

其他分析

注意到如果按照题目给出的方式对你发送的无向图进行随机打乱(随机一个排列替换掉所有入点和出点),并没有改变任何一条边的方向,那么这道题可以视为你在发送一个有向图。

有向图使用个点(或更少)比用无向图解决这个问题更加简单。

Codeforces上的一位用户azneyes提供了一种非常简单的只添加一个点的有向图做法。

 

 

Library

简要题意

交互题。

给一个长度的排列,你可以做次询问,每次可以询问中一些数字在排列上的所在位置构成的连续段个数。要求确定这个排列,正序或逆序都算对。

题目分析

首先确定这个排列等价于确定每个数左右两侧的数。

对于一个数和一个不包含的集合

即每两次询问可以得到中与相邻的数的个数。

如果我们对于每一个,二分有数与相邻的区间,那么可以在的询问里找到一个与相邻的数。

枚举的时候,由于前面的邻接关系已经被确定,可以直接从开始二分。

因为有个邻接关系,所以总的次数是,大约就是

经过测试,我的代码极限询问次数是(好险!)。

注意特判

代码