Implementation 合集

· · 个人记录

Matrix

因为要\max(a_i)个1fit进正方形内部，所以需要让它在第一行。令n = \max(a_i), 则正方形边长为n+1, 当0存在时，边长则为n+2。

有0的时候，不妨直接让外围一圈都是0，将问题转化成没有0的情况。

由于对称性，一行填入的时候，相对的一列也会被填入。所以第一行填入最大的之后，剩下的全部需要填充的行数都会-1。后续的每行可以不断填入直到最小的那个元素变为0。此时问题的规模已经缩小，我们将最大和最小的行数都构造了出来，需要构造的合法矩阵变成了一个更小的右下角的正方形。所以可以将矩阵按序构造。并采用双指针维护需要处理的头部和末尾。

但是为何这样能确保一定可以构造合法的矩形? 因为每次处理完一对(l, r)之后，至少有空余出来的一圈用不上。

a_{r+1} + 1 - x > a_r - x + 1

代码

Game Design

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

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

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

代码

Binary Table (Hard Version)

自己手玩样例可以发现，对于一格2 \times 2的格子，最多四次就可以变换成0。所以\frac{NM}{4} \times 4 = NM一定可以构造。

一种最暴力的写法如下:

这样，变换的操作次数上限为(nm-n-2m) + m-2 + 4 = nm-n-m+2 < nm, (n, m \geq 2)。

缩短代码的关键在于如何写好最终的特判以及取反函数。

代码

[Cutting with Lasers]()

深搜连通块即可，每一个格子有上下左右四个标记，标记它是否被切过。

代码

儒略日

Party Lamps

易语言

Chess Board Dance

虚拟内存

Paining the Fence

Hoof, Paper, Scissor G