2018 TCO Semi 1 解题记录

### Easy Lilypads
题意：一个$n\times m$的池塘，每一个格子有一片荷叶，一只青蛙从$(x,y)$开始跳，每一次可以向四个方向中的任何一个方向跳任意距离，但是不能两次往同一个方向跳，输出一种方案让青蛙经过每个格子恰好一次。 $n,m\le 50$
题解：傻逼构造题，青蛙每一次可以反复横跳刷一行，刷完一行无论落在哪里都可以跳到任意一行的某一个位置继续刷。
唯一的坑是只有一列，考虑交换横纵坐标。

### Medium DominoTilings
题意：你需要输出一个带障碍物的$n\times m$矩形，满足用$1\times 2$的多米诺骨牌覆盖有$K$种方案。
$n\le 13,n\times m\le 14400,K\le 10^{18}$
题解：神仙构造题，服了。
发现让方案数产生乘法是简单的，怎么在方案数上做加法成为难题。可以先把$2^i$构造出来，例如$i=4$
```
........
..##..##
```
那么如何在$4$上加一个$2^0$呢？
```
.........
.#######.
.#######.
.........
..##..###
```
考虑对于"x"位置讨论
```
.........
x#######.
x#######.
.........
..##..###
```
若x是整的，那么总方案还是$4$种。
若x不是整的，相当于在最后一行的骨牌全部是横着放的时候为环添加一种方案。
如果要加一个$2^1$呢？
```
.........
####x###.
####x###.
.........
..##..###
```
同样考虑对于"x"位置讨论
如果"x"是整的，那么方案是$4$种。
如果"x"不是整的，发现会把当前这一个$2\times 2$卡一下。
使它只能放$2$位置。但是前面的不受影响
```
....1....
####1###.
####0###.
....0....
..##22###
```
更一般的来说，以$10$为例：
```
....1........
####1#######.
####0#######.
....0334466..
..##22##55###
```
发现如果中间不是整块，会卡掉后面的所有情况使得它们无法决策而前面的方案是$2$的幂。
好，我们来看看成果：
```
.................
0###1###2###3###4
0###1###2###3###4
.................
..##..##..##..###
```
如果$K$的二进制位$i$为$1$那么$i$位置就应该成为'.'

### Hard FillInTheGraph
时间限制：4s
题意：给一个$n$个点有向图，你要给每个点一个数字$a_i$，满足对于每一个存在的数字$x$，至少存在一条数字为$x$的点连向$x+1$的点的边。问方案数。$n\le 15$

题解：很简单可以想到一个$O(4^n)$算法，按数字一个一个放，记三进制状压区分出上一个数字的点是哪些。这样带子集枚举就是$O(4^n)$。再优化下转移，用总的减去不合法的。
然后题解告诉我，再卡卡常就过了。

Rockdu's Blog

导航

最近发表

大佬们的友链