DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

网格排序

返回题目

题解

奇数行从左向右读取,偶数行从右向左读取,构成长度为 K=N2K=N^2K=N2 的蛇形路径。路径上相邻的格子在网格中也相邻。

将路径看成一维数组,输出逐次缩小未确定范围的冒泡排序比较序列,无需读取实际值。向右的路径边使用类型 222,向下使用类型 111,向左使用类型 444。向左时应指定左侧格子的坐标。

第一阶段用 K(K−1)/2K(K-1)/2K(K−1)/2 次操作将路径升序排列。每行已经包含该行应有的所有值,但偶数行顺序相反。再用类型 222 的冒泡排序将每个偶数行升序排列。

总操作数为

X=N2(N2−1)2+⌊N2⌋N(N−1)2≤N42+N34≤N4.X=\frac{N^2(N^2-1)}2+\left\lfloor\frac N2\right\rfloor\frac{N(N-1)}2\leq\frac{N^4}{2}+\frac{N^3}{4}\leq N^4.X=2N2(

输出时间为 O(N4)O(N^4)O(N4),路径占用 O(N2)O(N^2)O(N2) 空间。N=30N=30N= 时 。,检查预算的分子为 ,全部算术都在有符号 位整数范围内。

子任务 1 的朴素实现沿整条路径执行 KKK 轮冒泡排序,再修复偶数行。N=2,3,4N=2,3,4N=2,3,4 时分别使用 13,75,25213,75,25213,75,252 次操作,满足限制。完整范围则应跳过已经确定的后缀,将第一阶段比较数减少至 K(K−1)/2K(K-1)/2。

检查器使用 O(X)O(X)O(X) 空间存储操作。检查耗时 O(⌊108/N4⌋(N2+X))O(\lfloor10^8/N^4\rfloor(N^2+X))O(⌊108/N4⌋(N。

Solution written by GPT6

N
2
−
1
)
​
+
⌊2N​⌋2N(N−1)​≤
2N4​+
4N3​≤
N4.
30
X=411 075X=411\,075X=411075
N4≤810 000N^4\leq810\,000N4≤810000
10810^8108
646464
K
(
K
−
1)/2
2
+
X))