CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

pmxm：有眼缘

==== D ====

题意很简单，有一个6*6的方格，每次可以从任意一个格子的最顶上，往下或者往右放若干个数，要你对初始在(1,1)的$n \le 40000$个数排序，最后放在(6,6)这个位置。

思考：先考虑2*2的问题，那么可以先把两个数在$(1,2)$排好序，把两个数在$(2,1)$排好序，然后将$(1,2)$，$(2,1)$，$(1,1)$上有序的数全部归并到(2,2)。这样发现可以使得5个数有序。

那么对于坐标为$(x,y)$的格子，记该格子最多可以使得$f(x,y)$个数有序，有递推式

$$
f(x,y) = \sum_{xx<x \ or \ yy<x} f(xx,yy)
$$

起点是$f(1,1) = 1, f(1,2) = f(2,1) = 2$

这样打表发现$f(6,6)$恰好是4w多。

于是按照这个思路，每个格子都按照其最多能有序的数量从起点开始选数，多路归并排序即可。


xsy：从(1,1)一口气选了很多数，憨批。

CVBB ACM Team

用户工具

站点工具

页面工具