专栏文章

P12911 [POI 2020/2021 R2] 棋盘 / Projekt planszy

RRigel
P12911题解参与者 8已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mip15w29
此快照首次捕获于
2025/12/03 04:28
3 个月前
此快照最后确认于
2025/12/03 04:28
3 个月前
查看原文
有趣的构造题。
看了两位金钩大神写的进制拆分，颇受启发。
在此提供一种有点暴力但是简单易懂、具有普遍性的构造方案。
题目要求 1≤n≤1001 \leq n \leq 100，我们直接将网格开到 100×100100 \times 100。
定义 ai,ja_{i,j} 表示格子 (i,j)(i,j) 的状态，当 ai,j=1a_{i,j}=1 时 (i,j)(i,j) 被封锁，否则未被封锁。
初始时除起点与终点外的所有格子均被封锁。
考虑将 KK 条路径拆分。设 KK（K≤1018K \leq 10^{18}）的第 ii 个数位（定义个位为第 00 位）的数值为 wiw_i，则：
K=∑i=018(wi×10i).K = \sum\limits_{i=0}^{18}(w_i \times 10^i).
例如，1949=0×1018+⋯+0×104+1×103+9×102+4×101+9×1001949 = 0 \times 10^{18} + \cdots + 0 \times 10^4 + 1 \times 10^3 + 9 \times 10^2 + 4 \times 10^1 + 9 \times 10^0。
定义『块』为 3×43 \times 4 的网格。
一个从左上角走至右下角有 nn 条合法路径的『块』被称为『nn 类块』。
下面给出『00 类块』至『1010 类块』的一种构造方案。
CPP
#...  ....  ....  ...#  ....  ...#  ....  ....  ...#  ....  ....
....  ###.  .##.  #..#  .#..  #...  #...  ....  ....  ....  ....
....  ###.  ....  #...  ....  #...  #...  ##..  #...  #...  ....
容易证明，将一个『nn 类块』的右下角与一个『mm 类块』的左上角连接后，从『nn 类块』的左上角走至『mm 类块』的右下角的合法方案数为 n×mn \times m。
开始构造。我们在图的顶部放置 1919 个『块』（红色），其中第 ii 个『块』为『wiw_i 类块』。（i∈[0,18]i \in [0,18]，设最右边的为第 00 个『块』，即 KK 的个位所对应的『块』）
在底下放置 1818 个『1010 类块』（蓝色）。
将这些『块』按上图方式连接。
从起点开始走，经过上面的第 ii 个『块』之后，还会经过 ii 个『1010 类块』，因此走到右下角的合法路径数为 wi×10iw_i \times 10^i。
整个结构的合法路径数为每种走法的合法路径数之和，也就是 ∑i=018(wi×10i)=K\sum\limits_{i=0}^{18}(w_i \times 10^i) = K。
结构的长度（横向）为 18×2+7=4318 \times 2 + 7 = 43，宽度（纵向）为 18×5+4=9418 \times 5 + 4 = 94，符合题目要求。
最后将结构的右下角连接至终点即可。
Submission。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...