OCI camp day 3

· · 个人记录

Game Design

可以发现，每次在横向移动与垂直移动之间切换的时候，可以将步长变为原先的两倍，这样一定不会与之前的任意一个格子相冲突。由于n \leq 20, 所以变化次数至多19次，并不会超过边界。（本质上就是构造一个有宽度的spiral）。

什么时候会impossible呢？除了最终一直水平或者垂直移动之外，都可以构造。但是如何判断一直水平和垂直移动有一些tricky。举个例子：可以先左再右，或者先右再左。也就是说，可以至多变换方向一次。

那么怎么知道最终坐标呢？其实直接从(0, 0)开始，然后将坐标偏移即可。

代码

Maximum Sum

线段树板子题，不说了。

Friends and Subsequences

尝试固定一个端点，比如左端点。

\max(l, r) - \min(l, r) \leq \max(l, r+1) - \min(l, r+1)

又要列不等式！

因为\max不降，\min不增，所以可以二分找到两个端点。

但是二分有一些细节，因为你不能确保找得到这样的两个端点。所以找端点可以直接枚举一个长度至少为6的区间，找到后l或者r再向对方靠近。

如果存在两个端点，答案增加R - L + 1。

Eliminating Balloons

反着遍历，对于所有H，是否存在H-1否则需要开一条新路。最终数路径数量就可以了。

Set to Max (Hard Version)

因为最值是可覆盖的。所以需要优先处理那些连续的，当前值最小的b的区间。同时对于这个区间，找到最左边和最右边（区间内的情况也得考虑）是否存在与b_i同值的a_j，这样的话就可以“拉过来”。但是需要确保拉过来的时候不能路过比b_i小的元素，在a中也不能路过比b_i大的值。

我当时用的很麻烦的标记做法，导致需要用线段树标记。现在看看直接用st表不就可以了？

Guess the Path （未补）

可以不断的将问题缩小至原先的一半，也就是divide and conquer.