构造算法

Published: by Creative Commons Licence

  • Tags:

二维网格放置1x2和2x1方块问题

有一个n行m列的二维网格,你有a个1x2的方块和b个2x1的方块。问是否可以将这些方块不相互覆盖全部放置到网格上。

这是atcoder的一道题目

这个问题我也没法太清晰地证明,就只是讲讲做法就好了。

首先我们可以很自然地将两个1x2方块或两个2x1方块合并为一个2x2方块,这不是什么难事。

当n和m都是偶数的时候,将2x2的方块往上丢就可以了。

之后考虑当m为奇数的时候,我们可以将最左边那一行先用2x1的方块覆盖。

分两种情况讨论,若n是偶数,那么这意味这最左边那一行可以被完全覆盖(除非$2a<n$)。这种情况下问题就变成了在n行(m-1)列网格放置的问题。

同样如果n是奇数、m是偶数,问题也是同样解决。

下面说一下n是奇数、m是偶数的情况下。这时候不管如何放置都会出现至少一个空位。我们先将最左边那一列用2x1的方块覆盖,最上面的那一列用1x2的方块覆盖,当然我们最后一定会留出至少一个空位,推荐将空位让给第3行第1列。比如考虑5行3列的情况。

^<>
v..
...
^..
v..

我们要的效果就是这样。说一下这样的好处。当剩下的a和b都是奇数的情况下,原先我们会浪费1个2x2的空格。

^<>
v<>
...
^^.
vv.

但是,这里我们可以避免2x2空格的浪费,考虑下面的方法:

^<>
v.^
<>v
^..
v..

因此,当a为4,b为3的时候,正确的做法如下:

^<>
v.^
<>v
^<>
v<>

置换排序

给定一个$0$到$n-1$的置换$p_0,p_1,\ldots,p_{n-1}$,你每次操作可以选择一个下标$i$,并交互$p$序列中第$i$个和第$(i+p_i)\mod n$个元素。要求用少于$2\times 10^5$次操作,将序列排序。其中$1\leq n\leq 100$。

有一个比较简单的随机做法。我们可以不断随机操作,直到排列中只包含一个大环。假如数据是随机的情况下,排列中仅含一个环的概率为$\frac{1}{n}$。

在只有一个环后,之后对$0$位置做$n-1$次操作就会将序列排序。(此时$p_0$会交换到正确的位置,之后$p_0$会变成环上的下一个元素,且$0$处于环的末尾)。

提供一道题目

Floyd判环

有一个如下图的图,有十颗棋子一开始处于起点,只能沿着箭头移动。你不知道$t$和$c$,你每回合可以让任意颗棋子向前移动一步,移动后交互器会告诉你目前哪些棋子落在同一个位置。要求你最后将所有棋子都抵达终点(环的入口),使用的总回合数不能超过$3(t+c)$。

https://espresso.codeforces.com/af92f1219aedcbc53b754b15118dfe4ce5a1be84.png

一道题目

神奇的解法,以前确实做过类似的龟兔赛跑来判环的方法,但是确实从来不知道用三个棋子,3(t+c)步就可以得出t和c的所有信息。

首先,我们可以用棋子0和棋子1做龟兔赛跑,棋子0每次走两步,棋子1每次走一步。直到二者在环上距离入口$x$处相遇。这时候0走的距离为$t+x+kc$,1走的距离为$t+x$(1肯定没有走完整个循环)。而由于0走的距离是1的两倍,因此可以推出:$t+x=0\mod c$。这意味着当我们将所有棋子每次都向前移动一步,那么至少需要$t$步才能保证所有棋子都走到循环的入口,同时t步也正好能保证所有棋子来到循环的入口。