2019-2020 ACM-ICPC Latin American Regional Programming Contest

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Solved by Xiejiadong. 03:25 (+)

题意:固定每个月的涨动,每次询问开始月份和结束月份以及初始值,浮动有一个上下限,不能超过这两个限制,求结束月份的价格。

题解:离线处理所有的询问。

用线段树维护每一个位置,初始月份开始前,将该对应的询问位置改成对应的初始值。

每个月队友所有的位置,进行相应的更改,对应涨动。

对于每一个 $\ge R$ 的位置,全部修改成 $R$ ;对于每一个 $\le L$ 的位置,全部修改成 $L$ ,完成了上下限的设置。

当到达对应月份的时候,记录最终答案即可。

维护的那部分全部用 Segment Beats 维护。

Problem D

Solved by Kilo_5723. 01:44 (+)

Problem E

Solved by Xiejiadong. 00:27 (+)

题意:环形串中找出长度 $\le r$ 且至少包含一个字母 `E` 的字符串。

题解:枚举开头位置:

  • 至少包含一个字母 `E` 相当于,结束位置的开始必须是之后第一个 `E` 的位置;
  • 环形串中找出长度 $\le r$ ,相当于规定了结束为止的最后位置。

这两个直接相减,就是固定开头情况下的可能情况总数。

Problem F

Solved by Kilo_5723. 04:14 (+)

Problem G

Solved by Weaver_zhu. 01:48 (+1)

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 01:02 (+)

题意:消息逐层跳转传递,求每一个尾端服务器接受消息的总次数和接受消息的尾端服务器数量。

题解:第一部分,每一个尾端服务器接受消息的总次数:

从被接收方向发送方连边,题目保证了是一个 DAG ,默认尾端服务器为 $1$ ,其余的利用拓扑排序递推每一个服务器发送到尾端的次数,最后服务器 $1$ 的次数就是总次数。

第二部分,接受消息的尾端服务器数量:

从发送方向接收方连边,统计服务器 $1$ 能够达到的服务器总数即可。

Problem J

Unsolved.

Problem K

Solved by Kilo_5723. 01:09 (+)

Problem L

Solved by Kilo_5723. 02:27 (+)

Problem M

Solved by Xiejiadong. 00:16 (+)

温暖的签到。