JOISC 2020 Day 3

日志

不存在的……今天偷懒了……只是简单的看了看题目……

stray

感觉这题是个Ad-Hoc题……干就完了!

\(A=3\)的情况

从\(0\)开始作bfs,点\(i\)到\(0\)的距离为\(dis_i\)。

为了讨论方便,不妨设原图是一条链,且\(fa_i\)是\(i\)的前驱。

对于一个点\(u\),只可能有这几种情况:

  1. \(u\)连向\(fa_u\)的。
  2. \(u\)连向\(v\),且\(dis_u\le dis_v\le dis_u+1\)。

因此,我们的染色方案如下:
对于点\(u\ne 0\),将\((u,f_u)\)染成\(dis_i\bmod 3\),将其它边染成\((dis_i+1)\bmod 3\)。

显然,对一个节点,它的边只可能有两种颜色。

我们的遍历方案如下:
对于一次Move,若只有一种颜色,则其只可能为惟一的\((u,fa_u)\),沿着它走即可。
否则,找较“前”的一种颜色,沿着它走即可。

\(A=2\)的情况

原图是一棵树,且最多允许走错\(3\)步。

我们先来考虑它的一个子问题:没有点的度数\(=2\)的情况。

此时,可以按之前的方法染色,选取出现次数较少的边即可。

我们再考虑它的一个子问题:原图是一条链的情况。

此时,按之前的方式染色是行不通的,但是我们注意到此时的\(B\ne 0\),只需要按照一种能够区分上下方向的方式染色即可。

我们考虑按照\(1,1,0,0,1,0,\dots\)这样循环染色。如果是向上的,则应该读出来是\(1,1,0,1,0,0\),可以区分!

我们可以进一步发现,这种方式可以通过\(B=6\)的子任务:

  1. 若最开始在两个\(1\)中间,可以在三步内得知当前的方向(\(1,1,0,0\)与\(1,1,0,1\))。
  2. 若最开始在一个\(1\)和一个\(0\)中间,也同理(\(1,0,1\)与\(1,0,0\))。

实际上,只需要随便走三步,然后

我们把这两个思路合在一起:对于一个点\(u\ne 0\),若它的度数为\(2\),则按照\(110010\)周期染色,否则按照深度染色。可以通过循环移位使得两个条件都满足。

实际上,只考虑长度为\(4\)的子串是完全不够的。然而神仙的zbw爷爷打了个补丁:只需要知道一个长度为\(5\)的子串就够了……然而,你可以走到第\(4\)个点时,不急着走,此时你可以获取一个\(5\)条边的序列!!可以通过在两倍\(110010\)上爆搜来知晓当前的方向。

%%%zbwyy tql

上一篇:QR扫码综合示例教程(十二)Qt5.15.2(qml)取出视频帧 原始帧


下一篇:【LOJ2831】「JOISC 2018 Day 1」道路建设(LCT+树状数组)