#P6475. [thoi2014]印刷电路板
[thoi2014]印刷电路板
题目描述
给定一组电子元件的整数坐标。用若干水平或竖直的铜线段把所有元件连通。线段可以在元件以外的点相交或分叉。求铜线总长度的最小值。
每组输入包含 块相互独立的电路板,每块板上有 个元件。元件坐标由两条序列生成。
输入格式
第一行两个正整数 。第二行六个正整数 和一个字符 ,其值为 A 或 B。
令 ,。对于 ,递推
$$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}.$$从 开始给电路板与每块板上的元件编号。第 块板的第 个元件先取坐标 。当 为 B 时,每块板前 个元件的横坐标各加 、纵坐标各加 。
输出格式
依次输出 行,每行一个整数,表示相应电路板最短的铜线总长度。
样例 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
数据范围
所有测试点满足 、、、。
| 原测试点编号 | 上界 | 额外限制 | 类型 | |
|---|---|---|---|---|
| 1–2 | 5 | A | ||
| 3 | 7 | 1 | ||
| 4–5 | 20 | |||
| 6–7 | ||||
| 8–9 | 6 | 1000 | B | |
| 10–13 | 7 | |||
| 14–16 | 6 | A | ||
| 17–20 | 7 | |||
原题共 个测试点,每个 分。原 PDF 附有两种语言的坐标生成示例。
原 PDF 第 4 页 · 第 5 页 · 第 6 页 · 第 7 页 · 第 8 页