hdu 6048 | 2017 Multi-University Training Contest – Team 2 D Puzzle (结论题)

http://acm.hdu.edu.cn/showproblem.php?pid=6048

题意:

 

有 n * m – 1 个数,每次选择第 1,p + 1,p * 2 + 1…..
的顺序选择数,先按左到右,再按从上到下的顺序填入n * m 的格子,空格子可以和相邻的数字交换位置,问最后能否在格子中形成 1~ n * m – 1的数按从左到右,从上到下的顺序。

思路:

傻逼结论题。

根据九宫格问题的结论:将矩阵中的数按先从左到下右再从上到下排成一列,其逆序对如果为偶数则一定有解,否则一定无解

根据九宫格问题的结论:将矩阵中的数按先从左到下右再从上到下排成一列,其逆序对如果为偶数则一定有解,否则一定无解

根据九宫格问题的结论:将矩阵中的数按先从左到下右再从上到下排成一列,其逆序对如果为偶数则一定有解,否则一定无解

然后我们可以观察发现,按照题目中填数的策略

按照填入的顺序,每个数对逆序对的贡献分别是0,p-1,2(p-1)… 0,p-1,2(p-1)…

注意到当总数小于等于p时,所有数对逆序对就没有贡献了。

然后直接算等差数列就好了。

$$ sum = na_{1} + \frac{n(n-1)}{2}*d $$

由于首项一直为0,所以只要算后面那部分就好了。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz