P3484 [POI 2009] WYS-Isles in a Triangular Grid

 图 1.1、1.2 和 1.3 中的形状是岛屿。图 1.4 中的形状不是岛屿。图 2.2、2.3 和 2.5 中的形状是全等的。 我们的目标是系统地描述每个 $n \leq 10$ 的所有不全等的岛屿，这些岛屿可以由边长为 1 的 $n$ 个三角形组成，并计算出这样的岛屿有多少个。 由最多十个三角形组成的每个岛屿的边界是由网格的单位线段组成的多边形链。它可以旋转，即可以在不将笔从纸上抬起的情况下进行轮廓描绘，使得每个线段都被依次经过一次，并回到起始点。然而，可能会出现某些点必须多次经过的情况（见图 2.4）。 幸运的是，由最多十个三角形组成的岛屿的形状的周长是连通的（因此可以在不将笔从纸上抬起的情况下进行轮廓描绘），不像图 1.2 中的那样。 在围绕周长旋转时，每经过一个单位线段，我们会进行以下类型的转向之一： - a - 向左 120 度， - b - 向左 60 度， - c - 0 度（即实际上不转向）， - d - 向右 60 度， - e - 向右 120 度。 围绕岛屿的每个循环可以用一个由集合 {a,b,c,d,e} 中的字母组成的单词来描述，其中每个字母表示在组成周长的每个连续单位线段之后应进行的转向。循环描述的字母数量与这样的单位线段数量相同。这意味着我们也描述了多边形链最后一个线段之后的转向，即使这不是唯一确定形状所必需的。然而，这个冗余的字母在将一个形状的循环描述转换为仅在起始点不同的另一个描述时非常有用。 单词 cdddcddd、dcdddcdd、cbbbcbbb 描述了图 2.1 形状的不同循环。 单词 cbeddcde、adcabcbb、abcbbadc 描述了图 2.2 形状的不同循环。 单词 acdabbcb 和 cddebced 描述了图 2.3 形状的不同循环。 如果在围绕某个形状的循环中形状的内部始终在右手边，我们称这样的循环为顺时针循环。 可以确定每个岛屿的所有与之全等的岛屿及其顺时针循环的集合。岛屿的代码是这样的一个单词： 1. 它是围绕与后者全等的某个岛屿的轮廓的顺时针循环的描述， 2. 在满足上述条件的所有单词中，它是字典序最小的。 对于图 2.2 和 2.3 中描绘的岛屿，它们是全等的，我们考虑围绕每个岛屿的所有顺时针循环： beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde 和 bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd 因此它们的公共代码是：bcedcdde，这是上述所有单词中字典序最小的。 图 2.4 中描绘的岛屿的代码是：aadecddcddde。 编写一个程序： 对于给定的大小为 $k$ 的岛屿代码，生成通过在其上添加一个三角形可以从中获得的所有大小为 $k+1$ 的岛屿的代码； 对于给定的整数 $n$，生成由 $n$ 个三角形组成的所有岛屿的代码。

标准输入的第一行给出一个整数 $t$（$1 \leq t \leq 5$），表示查询的数量。接下来的 $t$ 行中的每一行包含一个某种类型的查询。类型 1 的查询由字母 K 和一个由最多十个三角形组成的岛屿的代码组成，中间用一个空格分隔。类型 2 的查询由字母 N 和一个整数 $n$（$1 \leq n \leq 10$）组成，中间用一个空格分隔。

查询的答案应输出到标准输出。 对于类型 1 的查询，可以通过从与给定代码描述的岛屿全等的岛屿中添加一个三角形获得的不同代码的数量。在下一行中，所有这些代码应按字典序排列并用空格分隔。 对于类型 2 的查询，应打印由 $n$ 个三角形组成的不同岛屿代码的数量。在下一行中，所有这些代码应按字典序排列。

题面翻译由 ChatGPT-4o 提供。