2022 腾讯程序设计竞赛(一)
作者:
| 更新日期:差3秒就可以再次过一道题。
本文首发于公众号:天空的代码世界,微信号:tiankonguse
零、背景
这周某天晚上参加了腾讯举办的 2022 TPC 程序设计竞赛第一场比赛。
我的能力只能做出三道题,最终只通过两道题。
第三道题会做,但是敲错一个地方。
找到原因提交代码时,比赛恰好结束了,就差不到5秒。
一、王者荣耀
题意:有 n 个战队,两两进行比赛,每轮比赛有 3 局比赛,即 3 打 2 胜。
这里有两个概念:3打2胜胜利的次数,称为轮数;所有局比赛胜利的次数,称为局数。
现在告诉你所有对局的结果,求排名 TOP M 的战队。
排名优先按轮数从大到小排序,相等的再按局数排序。
如果两个都相等,则认为排名相同。
思路:按照题意保存下每个站队的编号、赢的轮数、赢的局数。
然后排序,求出排名前 M 的战队即可。
注意事项:由于有相等的排名,排名的数字是跳跃的。
例如前两个人并列第一,下个人就是第三名,不存在第二名。
二、负载均衡
题意:如下图,有 n 个任务与服务器,每个任务需要消耗若干资源,服务提最大提供若干的资源。
任务可以使用编号相同或者编号加一的那个服务器的资源(最后一个任务使用第一个服务器)。
问通过某种调度,任务是否可以同时运行。
数据范围:每个资源最大值是 10^7
,所有任务的资源和所有服务的资源之和不大于 10^7
思路:典型的网络流问题,可惜我不会网络流。
贪心解法:
我推理了下,发现可以谈心来做这道题。
由于每个任务只能使用两台服务器,一旦第一个任务在第一个服务器使用的资源确定了,后面的所有任务在所有服务器上使用的资源都会确认。
1)先假设第一个任务使用第一个服务器的所有资源,之后的任务依次计算,判断除了最后一个任务,中间的任务都是否完成分配。如果存在无法资源不足,则没有答案。
2)对于最后一个任务,在最后一个服务器分配资源后,看任务剩余的资源是否可以使用第一个服务器剩余的资源来分配(第一个服务器资源大于第一个任务资源的情况)。如果可以,则存在答案。
3)正常情况下,我们需要枚举第一个任务使用第一个服务器的资源,即一步步让资源给最后一个任务。目前已经预先计算出最后一个任务至少需要多少任务了,直接让对于的资源给最后一个任务。
4)根据第三步计算出第一个服务器让了多少资源,第一个任务使用剩余的资源重新计算,循环一遍。中间遇到资源无法满足的情况,则任务没有答案。
5)第二层循环再次到达最后一个任务后,判断最后一个任务是否使用最后一个服务器完成任务。如果可以,则有答案,否则没有答案。
枚举解法:
贪心的过程中,可以看到,需要枚举第一个任务使用第一个资源的各种情况。
复杂度:O(R * N)
R 的最大值是 10^7
,直接枚举第一个肯定会超时。
我们知道枚举哪个都一样,所以可以先循环找到最小值,枚举最小值。
这样会不会超时呢?
根据题目限制,所有资源之和不大于 10^7
,所以 n 个资源的最小值不大于 10^7/n
。
枚举的综合复杂度就是 10^7/n * n=10^7
三、翻转字符串
题意:如果一个字符串字典序严格大于字符串的反转,则称字符串是美丽的。
现在可以不断的对字符串追增自身某个后缀的反转,问最少追增几次形成的字符串是美丽的。
思路:
如果字符串所有字符都相等,则不可能形成美丽字符串。
如果字符串大于整个字符串的反转,则答案是需要 0 次。
一个字符串长度为 n,则有 n 个后缀。
所以一次操作可以形成 n 个新的字符串。
如果 n 个字符串只有有一个是美丽字符串,则答案是需要 1 次。
另外,如果字符串第一个字符不是最小值,则选择最小值开始的后缀,一定可以形成美丽字符串。
可以证明,两次操作一定可以构造出一个美丽字符串。
构造前,我们已经证明,第一个字符一定是最小的字符。
构造方法:
1)第一次选择整个字符串,形成一个回文字符串。
2)第二次选择最后一个字符(一定是最小的字符),新的字符串。
3)新的字符串与反转相比,相当于左移,并在前面插入了一个最小值。故一定大于反转字符串。
现在,我们需要判断字符串是否可以一次操作就得到美丽字符串。
找一个例子分析一下,发现可以先按整个字符串操作,形成一个回文串。
然后求回文串的后缀数组,判断当前回文串是不是最小的即可。
四、树上的逆序对
题意:给一个有根树,树的节点值要么是 0 要么是 1。
现在求一个树的 DFS 序列,要要求这个序列的逆序数最大。
思路:分析一下,可以发现不同的遍历,只会使相同根的不同子树的先后顺序发生变化。
并且每个子树的序列是连续的。
所以很容易想到,多个子树之间可以通过预先统计 0 与 1 的个人,然后比较排序,从而得到最优答案。
假设两个子树的根节点分别为 a 和 b,子树 0与1 的个数分别为 a0、a1、b0、b1。
如果 a 在 b 前面,则形成逆序数 a1 * b0
。
如果 b 在 a 前面,则形成逆序数 b1 * a0
。
谁在前面取决于这两种情况的大小关系。
所以我们可以通过这个大小关系,来对同一个根的所有子树进行排序,从而确定子树的遍历顺序。
五、回文数
题目没看,好像没人做出来。
六、最后
这次比赛有点小遗憾,虽然进入前百名,但是没能进入前 50 名。
第二场比赛也快开始了,看下下次比赛的表现吧。
《完》
-EOF-
本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号ID:tiankonguse-code
本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。