Codeforces Round #434 (Div. 1, based on Technocup 2018 Elimination Round 1)做题记录

A. Did you mean…

模拟一下,能断就断,把题目限制的条件判一判就好了。

B. Polycarp’s phone book

据说暴力就行了QAQ,那我还写什么Trie。。。我的做法是这样的,把所有串的后缀插入一棵Trie里面去,然后字典树节点记录一下这个节点是否只被一个字符串访问过,查询的时候也是这么做的。为了保证最短,所以我们找到一个这样的节点就返回。

C. Tests Renumeration

这道题就是一个模拟贪心题,但是细节很多而且实现的思路也有很多地方需要注意,最后是在qwertier聚聚的指导下才调过去。

我们统计出来example和test都分别还剩多少个空位,以及有多少个example放到了应该放test的位置上和有多少个test放到了应该放example的位置上去。我们可以发现如果当前需要调整但是已经没有example和test的空位,也就是两部分都卡死了,那么我们把一个test(也可以是example)拿出来,这样就有空位了,然后就可以放东西而不是发生交换了。这样可以保证答案最多为不在自己位置上的文件数目+1。

具体看代码吧。。。

D. Wizard’s Tour

一个贪心的构造题目。qwertier聚聚告诉我这叫做边的最大二分匹配问题。把边画成点,点画成表貌似亭显然的。。。但是这其实没啥用。。

我们对于每个连通块用dfs找到一颗树,然后非树边随便归到某个节点。然后回溯的时候判断一个儿子当前有多少个边属于他。如果是奇数那么把这条父亲和儿子的边给儿子,否则归到父亲上去。这样每个连通块只有当为奇数的情况下会损失一条边(但是这是不可避免的),否则就肯定把所有边的构造好了。

 

发表评论

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