Codeforces Round #481


A. Remove Duplicates

题意

对于相同的数字只保留最右边的。

分析

记录每一个数字出现的最后依次位置,只输出该位置上的数即可。

B. File Name

题意

去掉最少的字符,使得字符串中不包含连续的三个 \(x\) 。

分析

显然,对于连续的一段长度为 \(len(len\ge 3)\) 的字符串 \(x\) ,我们要保证连续的少于 \(3\) 个,至少需要删除 \(len-2\) 个字符,即保留两个 \(x\) 。

找出所有连续的 \(x\) 计算即可。

C. Letters

题意

按照楼的顺序依次给每一个信箱编号,求一个编号的信箱是第几栋楼的第几个信箱。

分析

前缀和统计出每一栋楼开始的信箱编号。

二分找出小于等于当前给出编号的最大开始编号,楼的编号即为这个开始编号所代表的楼。

这栋楼的第几个信箱,直接可以有开始编号和当前编号的差得到。

D. Almost Arithmetic Progression

题意

每一个数 \(x\) 可以变成 \(x+1\) 、\(x-1\) 或者不变,要求最少的变换次数,使得数列变成一个等差数列。

分析

对于数列的前两个数一共有 \(9\) 种变换方式。

等差数列只需要前两个数固定,后面的数就会全部固定。

于是只需要枚举 \(9\) 种情况下的最小变幻次数即可。

E. Bus Video System

题意

给出每一站公交车的上下客情况,求初始的时候公交车上的人数有多少种不同的情况。

分析

对于公交车我们逆向推出人数范围的区间大小。

公交车最后的时候车上的人数范围是 \([0,m]\) 。

如果在这一站下车 \(x\) 人,则之前人数的范围应该是 \([x,m+x]\) 。

显然 \(x\) 可以是正的也可以是负的,我们并不允许此时公交车上的人数非法,所以此时公交车上人数的范围应该是 \([max\{0,x\},min\{m,m+x\}]\) 。

以此方式倒推求出初始人数范围即可。

F. Mentors

题意

给出每个人的权值和一些关系,如果 \(x\) 可以成为 \(y\) 的导师,当且仅当

  • \(x\) 的权值大于 \(y\) ;
  • \(x\) 和 \(y\) 无关系。

求每一个人可以成为多少人的导师。

分析

显然,我们可以很容易的求得比一个人权值大的人有多少(直接排序即可)。

那么对于这些人中,显然分为两类:

  • \(x\) 和 \(y\) 无关系;
  • \(x\) 和 \(y\) 有关系。

而有关系的人数最多只有 \(10^5\) 对,显然有关系的而且满足大于关系的很容易求得,于是就很容易求的无关系且大于的数量了。

G. Petya’s Exams

题意

一共 \(n\) 天有 \(m\) 门考试,给出每一场考试可以开始复习的时间、需要复习的时间和考试的时间,合理安排 \(n\) 天,给出一种能够完成每一场考试的复习安排。

分析

对于每一天而言的策略是显然的:复习当前能复习的科目中最早要考的科目。

于是我们使用优先队列来维护当前需要复习的科目,需要的信息有:

  • 科目还需要复习的天数;
  • 科目考试的日期;

我们按照考试日期从小到大维护在优先队列中,每一天都拿取最早要考试的还没复习完的科目复习,即还需要复习的天数 \(-1\) ,如果还需要复习的天数归零了,显然是复习完了,就不再入队,否则重新入队。

而每一天也需要将当前新的可以开始复习的科目加入队列。

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 108,230

Categories

Archive

Comments