atcoder abc 第 241 场算法比赛

作者: | 更新日期:

abc 比赛有八道题,100 分钟根本做不完。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

之前说 leetcode 题目太简单,朋友推荐可以做 atcoder,时间都是周末晚上八点,时间很好。

于是做了一次,这次恰好题目也简单,但是题目太多了,100 分钟内做 8 道题,完全敲不完。

一、A - Digit Machine

题意:给 0 到 9 10个数字的映射关系。
起初位置在 0,问按照映射关系跳转三次后的值。

思路:按照题意,循环三次即可。

小技巧:看第一名直接是s[s[s[0]]] 输出答案的。

二、B - Pasta

题意:给 N 个面条的长度,M 天每天吃一根固定长度的面条。
问 M 天是否每天都可以吃到自己的面条。

思路:两个 map 统计,然后判断 M 天的统计是否是 N 天统计的子集。

小技巧:使用一个 map, N 天分别加一,M 天分别减一,看最后是否有负值。

三、C - Connect 6

题意:给一个黑白棋地图,问是否可以修改两个点,使得地图存在一个长度为 6 的黑色棋子组成的直线。
直线定义:水平、垂直、45度斜线。

思路:枚举每个位置为起点,向下、向右、向下右、向下左四个方向分别走 6 步黑子的个数,只要有一个方向的黑子大于 4 个,则有答案。

四、D - Sequence Query

题意:给一个空的集合,有三个操作。

-)插入一个值
-)询问小于等于 x 的集合里,第 k 大的值是多少。
-)询问大于等于 x 的集合里,第 k 小的值是多少。

边界: k 不大于 5.

思路:由于 k 不大于 5,直接使用一个 map 维护这个集合,然后使用 upper_bound 和 lower_bound 用来快速找到边界,然后循环 k 次进行判断即可。

思考题:假设 k 是任意值,这道题又该如何做呢?

五、E - Putting Candies

题意:桌子上起初有 0 个球,有 N 个数字。
循环执行规则:若桌子上有 X 个球,则在桌子上增加与第 X%N 个数字相等的球。
问执行 K 次后,桌子上求的个数。

思路:看题意数据范围很大,K 最大是 10^12,不过分析后,发现也不难。

把 N 个数字当做一个环。
在第 i 个位置往桌子上加 a[i] 个球后,下个位置必然是 (i+a[i])%N
当这样循环 N 次后, N 个数字里部分数字必然形成一个环。

所以可以预处理,求出起初位置、环的入口、环的大小、环中球的总个数。

之后分三部分来处理。

1)环前面的一步步模拟,直到环的入口。
2)根据环的大小,计算出会转几圈,直接计算出整环球的个数。
3)最后不足一圈的操作,模拟一步步模拟即可。

复杂度:O(n)

六、F - Skate

题意:山顶上建了一个H*W 的滑雪场坐标,其中有 N 个障碍物,用于辅助选手停下来。
如果一个选手垂直或水平方向撞到障碍物的时候,会在障碍物前面的一个坐标停下来。
现在告诉你选择的起始位置、目标位置、障碍物的位置,问选择是否可以到达目标?

思路:典型的搜索题,使用队列来搜索即可。

每个障碍物有四个方向,所以选手可以停留的位置最多是 4N,搜索不会超时。

那如何根据一个位置找到上下左右四个方向的停留位置呢?

维护 map<x, set<y>>map<y, set<x>> 即可。
这样就可以分别在 X 坐标轴与 Y 坐标轴快速找到最先遇到的障碍物。

七、G - Round Robin

题意:N 个选手在进行循环赛,即任意两个选手都会进行一场比赛,总共N*(N-1)/2 场比赛。
现在已经知道 M 场比赛的成绩,问接下里哪些选手可能获得第一名(不能并列第一)。

思路:比赛的时候我没有思路,赛后看了其他人的题解,发现所有人都是套用最大流模板直接通过的。

所以这里主要讲解下,对于最大流,怎么构图。

有 N 名选手可能得第一名,所以需要构造 N 个最大流的图。

假设第 i 个选手最终是第一名,则未来的比赛,显然这名选手需要全部胜利。
这样我们就可以计算出第 i 个选手可以得到的最大得分。

此时,如果已经有其他选手等于或超过第 i 个选手的得分,显然第 i 个选手不可能得第一名。

如果不确定是否可以得第一名,就需要进行构图了。

1)对于剩余的选手,根据已经确定的成绩,可以计算出未来每个选手最多可以胜利的场次。
这样,超源就可以到这些选择之间分别增加一个边,权重就是最多允许胜利的场次。

2)对于所有两两未确定成绩的选手组合,假设有 K 个,增加 K 个中间节点代表需要有一次比赛。
中间节点指向超级终点,权重都为 1,代表一场比赛只能有一个人胜出。

构图大概如下

最大流构图

这样,使用最大流模板运算,计算出的最大流等于 K 则代表有答案可以让枚举的选手获得最高分。

八、最后

其实还有一道附加题,我还不会做。
如果有谁做了这场比赛,会最后一道附加题的话,可以加我微信 tiankonguse,我学会了给你发个红包。

综合来看这场比赛,设计简单计算、模拟、复杂计算、搜索、最大流等。

少了一个动态规划,如果题的数量少两道,再包含动态规划题,就完美了。

加油,算法人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号ID:tiankonguse-code

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

关注公众号,接收最新消息

tiankonguse +
穿越