这次泉城赛三人三机,队友发挥的非常好,抱大腿啦~
队友A了三道,我A了一道(主要是我A完最简单的那道题之后,选的题竟然都是难的,我无了个大语了)
鉴于不知道其他三题具体难度,今天补了一下这几个题(有个拓扑排序的题没补,有机会出个专题总结一下拓扑排序)
下面来总结一下 B D I
我做的是b题,也是所有赛题中最简单的一个。
大意就是给出 26个英文字母的顺序,根据其作为大小规则,然后给出n个字符串,求第k个字典序(规则)小的字符串
这个题就很简单了,我看见就直接map存关系,写个cmp,然后直接去套sort,完美ac
然后就是D题,一个数论的题,大概就是给出n个数,求任意两个数模除的最大值。时间一秒。
n^2的暴力肯定是行不通的
基本上就是 排序,然后对每一个i ,做倍数的遍历,二分来找到第一个位置的数(我这里忘记了找到的是排前第一个)
这样整个流程下来 就是 nlog + n(logn+logn) <n^2
最后是I题,这个题我做的不太好。第一遍没有用埃式筛 tle 了,然后第二遍没有 二分还是 tle
最后想了想,因为p<q ,所以越靠里,组成的这个数就越小,所以我们只需要找到两边即可,通过 r - l,就可能算出,然后这里面所有的素数都可以组成这样的数。答案还是二分。
对于我来说能做的题差不多就这三个了,其中二个用到了二分思想,拓扑排序那个感觉很难想明白。主要是拓扑排序的题做的很少,并不清楚它能解决什么问题。