TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2930
  • 题目
  • P2930【THOI2014】印刷电路板
    限制 : 时间限制 : 60000 MS   空间限制 : 565536 KB
    评测说明 : 3s,512MB
    问题描述

    \(\texttt{Printed Circuit Board}\) (简称 \(\texttt{PCB}\) ),印刷电路板,他可以固定各种电子元器件,然后将它们连接起来,是的整个系统能够实现我们所需要的功能。因此,“焊板子”是一个很多工科学生(尤其是电子、自动化系的同学)都需要掌握的技能。

    现代电路板多用印刷技术制成。印刷线路板的最大特点是装配的原件紧凑、美观,并且适合于工厂的大规模生产。当然也适合各种电子小制作。这种线路板的基板是矩形的,用环氧板或纸质板制成。在基板上面用热压工艺贴上一层很薄的铜箔。用印刷法把电路印在铜箔上,再用腐蚀法把不需要的铜箔去掉,留下的铜箔便构成电路,最后钻上小孔,涂上助焊保护剂,电路板便制成了。

    由于技术限制,电路板上的铜线的宽度是确定的,并且铜线必须平行于电路板的边界(也就是说铜线必须平行于坐标轴)。

    例如以上两幅图都是可行的电路板。

    现在 \(\mathbf{R}\) 同学需要制作很多很多电路板,每个电路板上有若干个电子元件。他需要合理布置电路是的铜箔将所有电子元件都连通,并且消耗的铜最少。

    输入格式

    第一行输入两个正整数 \(T,n\) ,表示 \(\mathbf{R}\) 同学需要制作的电路板数量和每块电路板上的电子元件数。

    由于输入数据规模庞大,因此采用输入种子后随即生成的方式。

    第二行输入 \(6\) 个正整数 \(a,c,M_x,M_y,seed_x,seed_y\) ,以及一个字符 \(datatype\) ,并按照以下方式生成序列 \(X_i,Y_i\)

    \[ \begin{align} X_0&=seed_x\\ X_i&=\big((aX_{i-1}+c)/2^{16}\big)\bmod 2^{16}\\ Y_0&=seed_y\\ Y_i&=\big((aY_{i-1}+c)/2^{16}\big)\bmod 2^{16} \end{align} \]

    \(datatype\)\(\texttt{A}\) ,则第 \(i(0\leq i\lt T)\) 组数据中的 \(n\) 个电子元件的坐标:

    \[ \begin{align} &(X_{in}\bmod M_x,\ Y_{in}\bmod M_y)\\ &(X_{in+1}\bmod M_x,\ Y_{in+1}\bmod M_y)\\ &\cdots\\ &(X_{in+n-1}\bmod M_x,\ Y_{in+n-1}\bmod M_y)\\ &\end{align} \]

    \(datatype\)\(\texttt{B}\) ,则第 \(i(0\leq i\lt T)\) 组数据中的 \(n\) 个电子元件的坐标(即前三个点的横纵坐标分别加上 \(M_x\)\(M_y\) ):

    \[ \begin{align} &(X_{in}\bmod M_x+M_x,\ Y_{in}\bmod M_y+M_y)\\ &(X_{in+1}\bmod M_x+M_x,\ Y_{in+1}\bmod M_y+M_y)\\ &(X_{in+2}\bmod M_x+M_x,\ Y_{in+2}\bmod M_y+M_y)\\ &(X_{in+3}\bmod M_x,\ Y_{in+3}\bmod M_y)\\ &\cdots\\ &(X_{in+n-1}\bmod M_x,\ Y_{in+n-1}\bmod M_y)\\ \end{align} \]
    输出格式

    每组数据输出一行,仅包含一个数,表示最短的铜线长度。

    样例输入

    样例输入1:
    3 3
    903527 47001 10 10 675 293 A

    样例输入2:
    8 5
    903527 47001 5 5 190 338 A

    样例输入3:
    5 7
    903527 47001 1000 1000 190 338 B

    样例输出

    样例输出1:
    11
    5
    9

    样例输出2:
    9
    8
    7
    7
    8
    7
    8
    4

    样例输出3:
    3364
    3305
    4076
    3714
    2969

    提示

    样例解释

    样例1:
    case0: \((5,3) (6,0) (4,9)\)
    case1: \((2,1) (1,4) (2,0)\)
    case2: \((1,3) (0,7) (3,1)\)

    样例2的前三个数据分别为:
    case0: \((0,3) (0,0) (1,1) (4,4) (0,1)\)
    case1: \((3,1) (2,3) (2,4) (4,3) (1,0)\)
    case2: \((3,2) (2,1) (0,2) (0,4) (3,1)\)


    数据范围

    对于 \(100\%\) 的数据 \(n\leq 7\)\(T\leq 10^6\)\(a,c,seed_x,seed_y\leq 2^{31}-1\)\(M_x,M_y\leq 2^{16}\)

    测试点编号 \(n\qquad \qquad\) \(T\qquad \qquad\) 备注 数据类型
    \(1-2\) \(=5\) \(\leq 5\) \(M_x,M_y\leq 100\) \(\texttt{A}\)
    \(3\) \(=7\) \(=1\) \(M_x,M_y\leq 5\) \(\texttt{A}\)
    \(4-5\) \(=7\) \(\leq 20\) \(M_x,M_y\leq 5\) \(\texttt{A}\)
    \(6-7\) \(=7\) \(\leq 10^6\) \(M_x,M_y\leq 5\) \(\texttt{A}\)
    \(8-9\) \(=6\) \(\leq 10^3\) \(\texttt{B}\)
    \(10-13\) \(=7\) \(\leq 10^6\) \(\texttt{B}\)
    \(14-16\) \(=6\) \(\leq 10^6\) \(\texttt{A}\)
    \(17-20\) \(=7\) \(\leq 10^6\) \(\texttt{A}\)

    小贴士

    为了方便大家编写程序,在这里提供一个上述的数据生成的代码,仅供大家参考(不必以此为模板)。

    对于 \(\texttt{C/C++}\) 语言:

    int X[7000010], Y[7000010];
    int n, T, a, c, Mx, My;
    long long seedx, seedy;
    char datatype[4];
    
    //生成数据,并将其对Mx,My取模后的值保存在X,Y这两个数组中
    void createList() {
        int i, AD = (1 << 16) - 1;
        for (i = 0; i < n * T; i ++){
            X[i] = seedx % Mx;
            Y[i] = seedy % My;
            if (i % n < 3 && datatype[0] == 'B')
                X[i] += Mx, Y[i] += My;
            seedx = (((a * seedx + c) >> 16) & AD);
            seedy = (((a * seedy + c) >> 16) & AD);
        }
    }
    int main() {
        scanf("%d%d%d%d%d%d%lld%lld%s", &T, &n, &a, &c, &Mx, &My, &seedx, &seedy, datatype);
        createList();
        
        //你的计算代码
        
        return 0;
    }
    

    对于 \(\texttt{Pascal}\) 语言:

    var
        ax,ay: array[0..7000000] of longint;
        n,T,a,c,Mx,My: longint;
        seedx,seedy: int64;
        datatype: char;
        i,j: longint;
    
    //生成数据,并将其对Mx,My取模后的值保存在ax,ay这两个数组中
    procedure createList;
    var
        AD,i: longint;
    begin
        AD := (1 shl 16) - 1;
        for i:= 0 to n * T - 1 do
        begin
            ax[i] := seedx mod Mx;
            ay[i] := seedy mod My;
            if ((i mod n < 3) and (datatype = 'B')) then
            begin
                ax[i] := ax[i] + Mx;
                ay[i] := ay[i] + My;
            end;
            seedx := (((a * seedx + c) shr 16) and AD);
            seedy := (((a * seedy + c) shr 16) and AD);
        end;
    end;
    
    begin
        read(T,n,a,c,Mx,My,seedx,seedy);
        read(datatype);
        while (datatype = ' ') do 
            read(datatype);
        createList;
        
        //你的计算代码
        
    end.