srm 622

我觉得正常人打tc的开题顺序都是从level1到level2再到level3吧。
这场tc有着浓浓的sereja风。学校的网也是令人感动。
总之考挂自己弱。

level1

我不知道这题都能写挂的人是怎么做到进div1的。。。

level2

贪心。
实际上我是不会做这题的。
但是做过原题……嘛不a掉也说不过去。
@长郡众……还记得去年unis cup1.0的C么
当时的题目见这里:
https://www.contesthunter.org/contest/Unis%20Cup%201%EF%BC%8E0/Tree
虽然说这题边不带权,但是做法还是可以套到带权的情况的。

大概就是说,我们dfs这棵树,
然后假定dfs完u子树后,这个子树被分成了最少的块数,满足每块直径都小于常数D。
那么考虑如何实现这个dfs。。。
假设我们现在已经dfs过了u的所有子节点。
那么现在将u的所有子节点那些块都连向v。
首先如果现在u所在的块的直径小于等于D的话,那么我们什么都不干。显然这样是最优的。
否则的话,肯定是有两个子树i,j,它们里面有两个点连起来的长度大于D。
那么我们取向下最长链较长的那一个,不妨设为i,将u->i这条边砍掉(多一个块)
然后不停砍,直到u所在块的直径小于等于D就好了。

这个贪心的正确性?其实很显然。yy一下就好了。。

考场上我写得非常暴力,而且很冗长。。。实际上实现可以很简洁。

level3

数位dp。
毕竟是傻逼题,感觉比level2还简单。
首先注意到一个显然的性质——fib表示法里,数字i的字典序小于j的字典序等价于i<j
然后注意到一个二进制数能对应一个合法的fib表示当且仅当它不存在两个相邻二进制位同时为1。
这样子就足够dp了。
其实也根本算不上数位dp……
反正是傻逼题。

最后一点就是这题求异或和。。。
异或的数字可能有数字是超过64位的。。
我的解决办法是直接上bitset,糙快猛。

situation

tc打了多少场就滚粗了多少场。
智商什么的能抢救么。
手速什么的能抢救么。
看了一下榜,榜里面过500的人里面,我的分数好像是垫底几个(一百九十多)
代码应该也是全房间最长。
感觉按这rating变化趋势,变红毫无希望啊。

Comments

comments powered by Disqus