NFLSPC #2 键 题解

2019-11-28 22:49:32 By wzy

题目名字起坏了 偏离了我的风格= =

首先有一个在5*n^2次操作内将一个n*(n-1)的长方形填入自己想要的数字的方法

我们以填好前n-1列为例

首先按从上到下 从左到右的顺序填前n-1行n-1列的数:

我们要填在第i行第j列的数字在第x行第y列 这么移呢?

1 i=x

把这两个数字都沿列移到第n行 平移第n行使数字从第y列移动到第j列 然后把两列按列推回原位即可

2 其他情况

把这两个数字都沿行推到第n列 平移第n列使数字从第x行移动到第i行 然后把第i行沿行推回原位即可

注意到这两种操作都没有改变已经填的数字

然后填第n行

我们从左到右填

1 这个数字现在在第n行

把这个数字移到第n列 把第n列上移一格 把现在的格子移到第n列 把第n列下移一格 把第n行移回原位即可

2 这个数字现在不在第n行

把现在的格子移到第n列 把数沿列移动道第n行 把第n行移回原位即可

但是 怎么处理原问题呢?

注意到 每行的key至多n/3下取整个 把这个数字乘上n 和key三个字母的最小出现次数取较小值就是key出现次数的理论最大值

我们将给出一种达到最大值的构造

我们将key从上到下 从左到右的依次画在我们的目标方格表中 剩下的随便填

观察目标方格表 有两种情况

1 第n行没有key

我们只要将前n-1行用上面介绍的方法填上目标方格表里希望的数字即可

最后一行没有key 长什么样无所谓

2 第n行有key

那么第一列一定全是k

我们只要将后n-1列用上面介绍的方法填上目标方格表里希望的数字即可

第一列全是k 所以是什么顺序也无所谓

所有情况都给出了达到理论最大值的构造 并且不会超过5*n^2次平移

注:上移x格和左移x格在输出时应分别改写为下移n-x格和右移n-x格

$by\ \text{skyline}$

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。