船长的康复训练 I 之CF#562

粗粗一算,离开机房有一个多月啦。最近学考搞什么VB,都不知道还会不会写C++. 抱着试一试的心理,我挑选了一场300iq出题的Div.2,打算练一练手,却没想到…

哎,这个开场白写得跟悬疑小说样的。不过,果真是我太菜,VP的这场Div. 2,我就做出了A题。不过也不得不说,这套题,出得实在很妙,有些AtCoder的味道。

先写写Div. 2的五道题吧。

A. Circle Metro

A题还是会的。

B. Pairs

第一眼把题目看出了Paris,正想着题目到底跟巴黎有什么关系呢,原来是pairs…

首先出现组数最多的数肯定出现次数得在总数的一半以上嘛。于是我选了个最多的,把不包含它的选出来判一判,WA了。

我造了个这样的数据把自己叉了:

300 6
1 2
1 3
1 2
1 3
2 4
3 5

然而最后还是没能想出正解,怀着极差的心情去看了CDE,也没仔细想,于是去颓废了。

正解提示我注意到了这样一个性质:既然每对数都至少需要出现两个数中的一个,那么第一对数也一定满足。这样不就不会因为机械地去选出现次数最多的数而被hack了吗?

我总是不去注意一些最基本的东西,自以为找到了所有的通项规律就是伟大了。做数列题也是一样。这告诉我一个道理——最基本的东西往往能给自己最大的启示。

我今天下午去博库看到杨哥,跟杨哥讲了这题,想不到他一时半会儿也没想出来。

C. Increasing by Modulo

那晚会寝室觉得烦闷,不觉想起这题来,C题还是比较简单的。二分就可以了。

D. Good Triple

首先一个道理:找到“最小的”三元组,以此计数。(所谓“最小的”,意思与那些“最小性”这类意思基本相同,即不再包含其它三元组的三元组)

另外,很难发现一个性质:你能构造出来不含任何三元组的串不会太长,长度为1或2的当然不值得在此提起,我最长只能构造出长为8的10100101,再加一个0或者1都不行了,可能有更长的,不过都不会太大。因此这个题用暴力去找最小的三元组就行了,另外,还是请注意最小的,因此倒序寻找的右边界不会超过上一次找到三元组最右的点。

为此我和丁老师花了些时间去想,但是题解就给了这么一句话:

Lemma: there are no strings without such x,k of length at least 9.

我到现在都读不懂这句话是什么意思,看来得去请教哈佛毕业的班主任了。

E. And Reachability

E题其实想起来难度不大,只是很容易陷入到错误的解法中去,这道题的处理还是比较巧妙的。不过这里就不详说了。


Div2的题目激起了我对Div 1的兴趣,于是再写写Div1的题。

D. Anagram Paths

首先所有叶子的深度必须相等。

容易发现,如果树要是anagrammable的,那么对于它的每一个点 u,我们统计从 u 出发的到叶子所有路径中每个字符最多出现次数 max(u, ch),设 u 到叶子的距离为 h_u,则 sum max(u,ch) le h_u.

但是这样直接维护对我来说除了暴力并没有好方法。

注意到题目给出的是二叉树,而且没有分支的链上的边一条一条维护其实是很没有意义的,因此我们考虑缩这种链。可以证明缩链后树高最坏为 O(sqrt{n})(即每层点数是1, 2, …, sqrt{n} 这样的情况,一条链都缩不了)。那么暴力更新就可以了。

这题写好之后有个地方出了细节错误,WA在第5个点。后来才发现是在更新跳father的时候一开始找错了,没有用缩链后的新标号而用了原来的老点标。


博客貌似被ban了,这个D题这么毒瘤我还是先不看E了吧哈哈哈…

About The Author

2 thoughts on “船长的康复训练 I 之CF#562

发表评论

电子邮件地址不会被公开。 必填项已用*标注