2017 Multi-University Training Contest 1 总结

2017 年第一场多校,各种开黑最后 4 题,表现中规中矩,不过还是小失误连连。读题速度偏慢,细节看不见。在写代码的时候有些地方想当然的漏写一些符号之类的等粗心错误。并且,一些高端的算法思想也不熟练,导致一些题目不敢写。这些问题都有待改进。
官方题解
 

1001 Add More Zero

找出最大 k 满足 10 ^ k < 2 ^ m 两边取对数移项得 k < m \frac{log(2)}{log(10)}. 所以答案为  \lfloor m \frac{log(2)}{log(10)} \rfloor.

 

1002 Balala Power!

每一个字母对答案的贡献都可以看成一个 26 进制数,统计好这个并且按照这个排序。可证明贡献次数越高的字符对应的数越大越好。为了防止出现前导 0,我们先将最小的对应为 0,再去从大到小对应 25, 24, 23 ... 1.最后算出答案。

 

1003 Colorful Tree

参考了一位大牛的博客,他的代码十分详细且有注释图例。博客链接
首先理解官方题解里的问题转换,再去理解如何一遍 DFS 求解。在求当前节点的时候,利用以前统计的信息分块。维护的信息是以每种颜色为根的子树中有多少个节点。利用差分,得到在当前树中,以跟树根一样颜色的树根的子树一共有多少节点。用总结点减去这些节点则得到了每个区域中的可行的块,统计块对答案的贡献。

 

1006 Function

首先考虑 \{a_n \}\{ b_n\} 的性质,作为排列,他们的拓扑结构一定是若干个环组成,且环上没有分叉(口头语。。。。并不专业😅😅😅😅😅😅😅) 并且,在 \{a_n \} 的一个环中,只要有一个与 b_i 对应,那么这个环上的的其他节点也依次对应到 b_i 的环上,因为是环,所以在循环对应后还要能依次对应到原来的位置。也就是说,如果第一个环长度为 n' 对应的环的长度为 m' 那么只有 n' \ mod\ m' = 0 才可以对应上,并且有 m' 中对应方法。所以对于 \{a_n \} 中的每一个环,我们可以穷举 \{b_n \} 的每一个环,用加法原理计数。用乘法原理计算所有的环的情况。

 

1011 KazaQ's Socks

在前 n 天每天对应编号一样的袜子,之后的 n - 1 天中,奇数周期为 1, 2, 3, 4, ... n-2, n-1,偶数周期为 1, 2, 3, 4, ... n-2, n.特判即可。

 

完结

One thought on “2017 Multi-University Training Contest 1 总结

发表评论

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