search

  • 7th November 2026

四色滑道:从博物馆的益智玩具到一道OI题

Palo Alto Junior Museum and Zoo的室内科学展区(Indoor science exhibits)墙上挂着一块大号的Montessori Slide Puzzle:下方是四条竖直滑槽,每条槽里叠着四颗彩色圆柱珠子;上方的卡片给出目标图案,玩家要通过滑动珠子把下面摆成卡片上的样子。 本文把它抽象成一道OI题,并给出题解和标准程序。

我只拍了两张照片,问了一句「能否根据这个益智玩具设计一道OI算法题?涉及编号时,从 0 开始。提供题解和C++标准程序」。 下面的题面、题解、标程、对拍程序,连同数据范围的取舍,都是Opus 5.5根据照片生成的,这篇文章也是它写的。 它自己从照片里读出了槽、木舌和滑道的结构,写暴力程序对拍,实测连通块大小来确定数据范围,还发现了「底层冻结」这个不变量。我大受震撼。

…

Read more →
  • 18th December 2011

八数码

八数码问题,已访问状态采用 factorial number system 表示,未访问的未使用(简化代码) 实现了 Breadth First Search 和 Heuristic Search 两种算法。 带上命令行选项 -g 能输出 Graphviz 的 dot 格式的状态树。 比较满意的地方是把两种搜索算法的共同部分抽象出来了,写成了单独的 search 函数。

…

Read more →