ioid1t3

· · 个人记录

先拼盘。

Sub 1,2

树。好办的，把欧拉序一字排开，往下复制直到成为方块。

Sub 3,4

所有点都和 1 有连边。用 1 填满网格，留出一些 1\times 2 的空格。每条和 1 无关的边就填进这个空格。显然整个图应该联通，这样不会出现有些点和 1 没连上。

30 到手。

Sub 5

考虑扩展这个模式：

1 1 1 1 1 1 1 1
* * 1 * * 1 * *
1 1 1 1 1 1 1 1

比如：

1 1 1 1 1 1 1 1 1 1 1
2 3 1 3 4 1 2 4 1 5 5
1 1 1 1 1 1 1 1 1 1 1

就能解决 (1,2)(1,3)(1,4)(1,5)(2,3)(3,4)(2,4)。

那再加一个 (3,6)(3,7)(6,7)(6,8)怎么办？

在下面拼一个：

3 3 3 3 3 3 3 3 3 3 3
6 7 3 3 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3 3 3 3
6 6 6 6 6 6 6 6 6 6 6
8 8 8 8 8 8 8 8 8 8 8

棒。

显然一行如果过于长了可以截断往下拼，到底截多少可以算总共的组数，使长宽尽量均匀。

这样最多有 n(n-1)/2 组，对于同一个颜色框，长 x 组宽 y 组的时候边长是 (2y-1)\times (3x-1) 。所以尽量让这个分组的 x,y 接近 2:3。那么 x=n(n-1)/5,y=3n(n-1)/10，边长是 3n(n-1)/5-1，比例是 3(n-1)/5 左右。对于 n\le 15 能过。

44pts。不过这个可能有点难写，细节咧。

Sub 6

重新想了下，好像还是那个欧拉序有前途。

抠出最长链，作为欧拉序的末选，这样可以让欧拉序最短，可以少从最长链跑回根。

dfs。每次跑到一个点（第一次经过）就把和他相邻的点全跑一遍。比如 1 和 2,4,5,7 相邻，那就填：

1 1 1 1 1 1 1 1
1 2 1 4 1 5 1 7
1 1 1 1 1 1 1 1

不是第一次经过就填一行的 1 完事。

这样绝对能塞进 4n 里，因为主要开销在行，每个点第一次经过经过多花 2n 行，欧拉序最多 2n，所以是 4n 行。

72 咯。

这种策略的列数是 2n，有前途啊！

看题解。

我草怎么又是差一步脑电波啊啊啊啊。

你发现我们现在最多需要 4n 行，2n 列。

那么一个正方形，什么东西有 4n 条呢？啊哈！对角线！

结束了。你把欧拉序丢到对角线上然后在第一次经过的时候搞一个 3 条对角线的夹层。因为对角插入，不存在相邻的数会打架的问题，直接插入所有往 dfs 序更小的点连的边，这显然不会超过它当前的 dfs 序个，因此这个对角线是放得下的。

做完了。哎。

但是回想起来，确实是天才啊！