ioid1t3

先拼盘。

Sub 1,2

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

Sub 3,4

所有点都和 1 有连边。用 1 填满网格，留出一些

1\times 2

的空格。每条和 1 无关的边就填进这个空格。显然整个图应该联通，这样不会出现有些点和 1 没连上。

30 到手。

Sub 5

考虑扩展这个模式：

CPP

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

比如：

CPP

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)怎么办？

在下面拼一个：

CPP

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 相邻，那就填：

CPP

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 序个，因此这个对角线是放得下的。

做完了。哎。

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

文章操作