随机数生成器
生成棋盘排列后,按数值从小到大尝试选格;维护每行可选列区间,得到排序后字典序最小的右上/右下路径序列。来源 Luogu P2354 · 标签 贪心 / 构造 / 模拟 / 区间
题目描述
给定随机种子 ,先按
生成随机序列。令 ,初始排列 。对 ,交换 与 ;再进行 次额外交换。
把最终的 逐行填入 行 列的棋盘。从 出发,每次向右或向下走到 。把路径上的 个数排序,得到路径序列。
求字典序最小的路径序列。
,。
题解
先生成排列 和棋盘,并记录每个数所在的格子。
答案序列已经排序,因此按数值 依次尝试:若当前数所在的格子还能出现在某条合法路径上,就选它;否则跳过。这样每一步都取当前能取的最小值,得到的就是字典序最小的序列。
为了判断“还能出现在路径上”,维护每一行当前允许的列区间 ,初始为 。设当前数为 ,位置为 :
- 若 ,跳过;
否则选中 ,并更新:
- 对所有 ,令 ;
- 对所有 ,令 。
原因是路径经过 后,它上方的行不能走到 的右侧,下方的行不能走到 的左侧。区间被不断收缩,后续数是否可选只需查它所在行的区间。
选到 个数后停止,按选中的顺序输出。
复杂度
生成排列和棋盘为 。贪心最多选 个数,每次更新 行,总时间为 ,空间为 。