BZOJ1998 - [Hnoi2010]Fsk物品调度

BZOJ1998 - Click Here

  

Description

  现在找工作不容易,Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置,从0到n-1依次编号,一开始0号位置空,其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。 规则由5个数描述,q,p,m,d,s,s表示空位的最终位置。

  首先生成一个序列$c$,$c_0=0,c_{i+1}=(c_i \times q + p) \, mod \, m$。接下来从第一个盒子开始依次生成每个盒子的最终位置$pos_i$,$pos_i = (c_i+d \times x_i + y_i) \, mod \, n$,$x_i,y_i$是为了让第i个盒子不与之前的盒子位置相同的由你设定的非负整数,且$pos_i$还不能为s。如果有多个$x_i,y_i$满足要求,你需要选择$y_i$最小的,当$y_i$相同时选择$x_i$最小的。 这样你得到了所有盒子的最终位置,现在你每次可以把某个盒子移动到空位上,移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数。

  

Input

  第一行包含一个整数t,表示数据组数。接下来t行,每行6个数,n,s,q,p,m,d意义如上所述。

  所有数字的范围均<=1e5

  

Output

  对于每组数据输出一个数占一行,表示最少移动步数。

  

Solutions

  这题弄了好久,一开始以为是对剩余类分析,后来发现其实是对循环分析。

  

  这题有两个问题要处理,一是求$pos_i$,二是求最小步数。

  问题二:

  根据$pos_i$,我们可以得到盒子的置换。

  接着考虑置换的每个循环,若循环长度为1,则不需要交换;若循环内不包括空位,则需要$L+1$次交换;若循环内包含空位,则需要$L-1$次交换。

  

  问题一:

  由于题目是要求在$y_i$最小的情况下,$x_i$最小。因此可以固定一个变量,分析另外一个变量。另外,$c_i$计算过程独立于$pos_i$的计算过程,可以认为$c_i$是一个初始值

  在$y_i$固定的情况下,$x_i$的变换会使得初始值$+d$,也就是$a \rightarrow a+d$。显然,对于不同的$a$,其$a+d$也是不同的。换言之,这个过程是一个$0…n-1$向自身的双射,也就是一个置换!

  如果将这个置换循环分解,那么$x_i$的作用实际是寻找某个循环内还未被选择的元素,$y_i$的作用则是跳到下一个循环内。基于这个意义,寻找最小的$y_i$等价于寻找第一个含有未被选择的元素的循环,寻找最小的$x_i$等价于在循环内寻找第一个未被选择的元素。

  因此,我们需要某种数据结构去维护这些循环,且要求能够快速的寻找后继元素

  平衡树显然能完成这个操作,直接套用std::set即可解决。

  

  时间复杂度$O(TN \, log \, N)$

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang