codeforces round #614 题解

A. ConneR and the A.R.C. Markland-N

对于每个楼层,按照和ConneR在的楼层的差,按照绝对值进行排序。
该序列应该大致符合0,-1,1,-2,2……
注意一点:如果不符合该序列,要考虑两种情况:
一是越界,S+差值可能已经小于1或大于n,这个时候要略过该序列的这一位。
二是此处并没有在装修,因此这里符合条件,输出即可。

B. JOE is on TV!

1+1/2+1/3+……+1/n

C. NEKO’s Maze Game

野猫的题最简单啦!(该用户已被禁言)

障碍只有两种情况:
第一种是斜着的:
01
10

10
01
第二种是横着的:
11
只要满足任意一种的个数>0,就无法逾越。
在每次修改的时候,统计这种修改会使这两种障碍增加或减少了几个,然后判断是否能够逾越即可。

D. Aroma’s Search

PAFF谋害我……被hack了 QAQ
首先点的坐标以指数级别增长,不超过1e16,所以其实点数很少,最多也就54个
这些点的坐标都是严格递增的,因此,如果从i走到j(x[i] < x[j]),可以用最小步数(曼哈顿距离)把i,j之间所有的点都取走。证明很简单。 所以最终考虑的就是“取哪一段区间(i,j)”,因为点数很少,所以O(n^2)枚举左右端点 再判断一下区间长度+从原点到某个端点i或j的长度,是否<=体力,如果可以就更新答案,取点数最多的区间。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注