用户工具

站点工具


2020-2021:teams:hotpot:200516-200522

这是本文档旧的修订版!


2020/05/16——2020/05/22周报

团队训练

由于周末三个人的时间没有凑好所以没有举办。

林星涵

专题

个人练习

陶吟翔

专题

郭衍培

专题

本周推荐

陶吟翔:EducationalCodeforcesRound 76 - E

题目大意:三个人在打ACM比赛,一共有$N$道题从$1$到$N$标号,每个人拿到了一些题目。现在他们三个希望第一个人拿到题目的一个前缀,第三个人拿到题目的一个后缀,第二个人拿到了剩下的。也就是说,第一个人拿到了题目$1$到$k$,第三个人拿到了题目$p$到$N$,其中$p \ge k$,当然也可以有一个人或两个人没有拿到题目。现在一次操作可以把某一道题从一个人移动到另一个人处,问最少操作多少次可以满足要求。

解题思路:首先每个人拿到的题目编号是乱序的,我们可以先排序。然后我们的要求是第一个人的最大标号小于第二个人的最小标号,第二个人的最大标号小于第三个人的最小标号。由于要最小化操作的次数,所以我们要找到最长的满足条件的序列,然后调整剩余的题目。显然一个单调递增的子序列是满足条件的,而我们显然对于每一个位置不对的题目都只用一次操作就可以放到正确的位置,所以我们直接求出整体的最长上升子序列,然后答案就是用$N$减去它。

林星涵:

郭衍培:

2020-2021/teams/hotpot/200516-200522.1590122557.txt.gz · 最后更改: 2020/05/22 12:42 由 misakatao