#P6475. [thoi2014]印刷电路板

    ID: 5069 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS暴力枚举排列枚举全子集枚举树形 DP最小割有限候选集缩减状态编码消除被支配候选对称性去重字典序排名与反排名

[thoi2014]印刷电路板

题目描述

给定一组电子元件的整数坐标。用若干水平或竖直的铜线段把所有元件连通。线段可以在元件以外的点相交或分叉。求铜线总长度的最小值。

每组输入包含 TT 块相互独立的电路板,每块板上有 nn 个元件。元件坐标由两条序列生成。

输入格式

第一行两个正整数 T,nT,n。第二行六个正整数 a,c,Mx,My,seedx,seedya,c,M_x,M_y,\mathrm{seedx},\mathrm{seedy} 和一个字符 datatype\mathrm{datatype},其值为 A 或 B。

令 X0=seedxX_0=\mathrm{seedx},Y0=seedyY_0=\mathrm{seedy}。对于 j≥1j\ge1,递推

$$X_j=\left\lfloor\frac{aX_{j-1}+c}{2^{16}}\right\rfloor\bmod 2^{16}, \qquad Y_j=\left\lfloor\frac{aY_{j-1}+c}{2^{16}}\right\rfloor\bmod 2^{16}.$$

从 00 开始给电路板与每块板上的元件编号。第 ii 块板的第 jj 个元件先取坐标 (Xin+j mod Mx, Yin+j mod My)(X_{in+j}\bmod M_x,\ Y_{in+j}\bmod M_y)。当 datatype\mathrm{datatype} 为 B 时,每块板前 33 个元件的横坐标各加 MxM_x、纵坐标各加 MyM_y。

输出格式

依次输出 TT 行,每行一个整数,表示相应电路板最短的铜线总长度。

样例 1

3 3
903527 47001 10 10 675 293 A
11
5
9

样例 2

8 5
903527 47001 5 5 190 338 A
9
8
7
7
8
7
8
4

样例 3

5 7
903527 47001 1000 1000 190 338 B
3364
3305
4076
3714
2969

数据范围

所有测试点满足 n≤7n\le7、T≤106T\le10^6、a,c≤231−1a,c\le2^{31}-1、Mx,My≤216M_x,M_y\le2^{16}。

原测试点编号 nn TT 上界 额外限制 类型
1–2 5 Mx,My≤100M_x,M_y\le100 A
3 7 1 Mx,My≤5M_x,M_y\le5
4–5 20
6–7 10610^6
8–9 6 1000 B
10–13 7 10610^6
14–16 6 A
17–20 7

原题共 2020 个测试点,每个 55 分。原 PDF 附有两种语言的坐标生成示例。

原 PDF 第 4 页 · 第 5 页 · 第 6 页 · 第 7 页 · 第 8 页