CUGBACM18 级训练#4 题解

B - Godfather Gym - 101649G #

题意: 给出一个有 n 个点的树,问去掉哪个点后剩下的树中最大的节点数最小(如果有多个按从小到大的顺序输出)。

思路: 一开始没看见“保证是一棵树”想复杂了,先跑一遍 dfs 序,这样就能知道每个点除了父节点之外所有的子树的大小了,父节点对应的“子树”的大小就是 n 减去所有子树的大小之和。遍历所有点,找出所有“子树”中最大的那个,将其大小和编号作为数对加入数组中,然后对所有点排序,输出最小的那几个就行了。

E - Wow! Such Doge! HDU - 4847 #

题意: 给出一篇文章,问其中出现过多少个”doge”(不区分大小写)。

思路: 先遍历文章,将所有大写之母转为小写,然后再用 find 或者暴力查找”doge”即可。

G - Theme Section HDU - 4763 #

题意: 给出一个字符串 n 找出一个最长的子串(theme),使其出现在开头中间和结尾(不允许重叠)

思路: 一开始被样例误导了,以为 theme 里面只能有一种字符,wa 了几发感觉不对,所以应该先跑前缀函数,然后从从第二位遍历到倒数第二位,如果某一位前缀函数大于其到第一位距离的一半,则取一半,找出其中的最大值,这样就得到了出现在中间的 theme 的最大长度。然后再判断最后一位的前缀长度是否大于整个字符串长度的三分之一,如果大于则取三分之一,这样就是出现在后面的 theme 的长度,输出中间和后面中比较小的一个即可。

I - Path HDU - 6582 #

不会网络流,有空再补。