CH Round #61 - 「Adera 10」冬令营热身赛

OI - Official

From lydrainbowcatlll6924 applepi


小时

尚未报名

兔子与樱花 41/52 From
取数游戏 47/80 From
粒子巡游 8/36 From
QY的魔盒 2/21 From

题解:第一题、第二题略。

第三题:非常抱歉……原题有Bug,需要加条件:保证发射器密度大于接收器,下面题解才是正确的:

首先,题目中的公式用半径差 / 圆心距,可以很容易地算出来那个角度,然后就可以用Rθ的弧长公式了。题目转化之后的模型是:规定起点、终点,所有从小密度到大密度的点之间有边,走这条边的代价已知,并且随时可以用扭曲平面方法到另一个点,所需代价只与到达的点有关,该方法只能用M次。然后求一条哈密顿路。。。

用最小费用最大流做,建立源、汇、附加源,每个点拆成左右两个,原图中的边从左部到右部连容量1费用为第一个公式,源点到每个左点容量1费用0,每个右点到汇点容量1费用0,源点到附加源容量m费用0,附加源到每个右点连容量1费用为扭曲平面代价的边。

需要注意的是由于规定了起点终点,所以建图时要忽略原图中终点出发的边和到达起点的边,并且从发射器到起点是不需要耗费扭曲平面的次数的(到右部起点的边要从源点发出,而不是附加源)。

第四题:插头DP。由于只有空地才有插头,所以轮廓线只有25/2+1=13这么长,直接二进制存每个位置有没有插头就好了。然后DP的时候枚举每个新格子以及周围的1圈构成的九宫格是什么状态(可以画一画,只有11种状态,带X的4种,直行的2种,转弯的4种,啥也没有1种)。不会插头DP的请网上参考陈丹琦课件。

-----------------------------------------------------------------------

使用IP访问,以获得更快的速度: http://162.105.80.126/contest

「Adera 10」冬令营热身赛

热身嘛。。。就没有什么正规的限制了。。。4小时4道题

由于出题菌发现题目水才可以有更多人参加……所以换了2道水题上来……

实际上是2道签到题+2道NOI级别题