算法提高
编号： ADV-1 题目： 两条直线 关键字：排序 类型：普通试题 问题描述：
给定平面上n个点。
求两条直线，这两条直线互相垂直，而且它们与x轴的夹角为45度，并且n个点中离这两条直线的曼哈顿距离的最大值最小。
两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和，一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。
输入格式
第一行包含一个数n。
接下来n行，每行包含两个整数，表示n个点的坐标（横纵坐标的绝对值小于10^9）。
输出格式
输出一个值，表示最小的最大曼哈顿距离的值，保留一位小数。 样例输入 4 1 0 0 1 2 1 1 2
样例输出 1.0
数据规模与约定
对于30%的数据，n<=100。
对于另外30%的数据，坐标范的绝对值小于100。
对于100%的数据，n<=10^5。
参考代码：
该题暂时没有人完全正确，暂时没有该语言的参考程序。
编号： ADV-2 题目：矩阵翻转
关键字：枚举 贪心 类型：普通试题 问题描述：
Ciel有一个N*N的矩阵，每个格子里都有一个整数。
N是一个奇数，设X = (N+1)/2。Ciel每次都可以做这样的一次操作：他从矩阵选出一个X*X的子矩阵，并将这个子矩阵中的所有整数都乘以-1。
现在问你经过一些操作之后，矩阵中所有数的和最大可以为多少。
输入格式
第一行为一个正整数N。
接下来N行每行有N个整数，表示初始矩阵中的数字。每个数的绝对值不超过1000。
输出格式
输出一个整数，表示操作后矩阵中所有数之和的最大值。 样例输入 3
-1 -1 1 -1 1 -1 1 -1 -1 样例输出 9
数据规模与约定
1 <= N <= 33，且N为奇数。
参考代码：
import java.io.IOException; import java.io.InputStream;
public class Main { private static class MyScanner { private InputStream is = System.in; public int nextInt() { try { int i; while ((i = is.read()) < 45 || i > 57) { }
}
}
int mark = 1, temp = 0; if (i == 45) { mark = -1; i = is.read(); }
while (i > 47 && i < 58) { temp = temp * 10 + i - 48; i = is.read(); }
return temp * mark; } catch (IOException e) { e.printStackTrace(); } return -1;
private static int x;
private static int[][] map, symbol; private static int[][][][][] dp; private static int calculate(int j) { int sum = 0;
for (int i = 0; i < x; ++i) { if (dp[symbol[i][x] + 1][symbol[x][j] + 1][symbol[x][x] + 1][i][j] > 0) { sum += dp[symbol[i][x] + 1][symbol[x][j] + 1][symbol[x][x] + 1][i][j]; continue; } }
int i2 = x + i + 1; int j2 = x + j + 1; int temp = map[i][j];
temp += map[i][j2] * symbol[i][x]; temp += map[i2][j] * symbol[x][j];
temp += map[i2][j2] * symbol[i2][x] * symbol[x][j2]; sum += Math.abs(temp);
dp[symbol[i][x] + 1][symbol[x][j] + 1][symbol[x][x] + 1][i][j] = Math .abs(temp);
}
return sum;
public static void main(String[] args) { MyScanner sc = new MyScanner(); int n = sc.nextInt(); map = new int[n][n]; symbol = new int[n][n]; dp = new int[3][3][3][n][n];
for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { map[i][j] = sc.nextInt(); symbol[i][j] = 1; } }
x = n / 2;
int maxSum = Integer.MIN_VALUE;
for (int count = (int) Math.pow(2, x + 1) - 1; count >= 0; --count) { int k = count; int center = (k & 1) > 0 ? 1 : -1; k >>= 1; symbol[x][x] = center;
int sum = map[x][x] * center;
for (int j = 0; j < x; ++j) { int t = (k & 1) > 0 ? 1 : -1; symbol[j][x] = t; symbol[x + j + 1][x] = t * center; sum += map[j][x] * t; sum += map[x + j + 1][x] * t * center; k >>= 1; }
for (int j = 0; j < x; ++j) { int j2 = x + j + 1; symbol[x][j] = 1; symbol[x][j2] = center; int temp = calculate(j) + map[x][j] + map[x][j2] * center;
}
}
}
}
symbol[x][j] = -1;
symbol[x][j2] = -1 * center;
sum += Math.max(temp, calculate(j) - map[x][j] + map[x][j2] * -1 * center);
maxSum = Math.max(maxSum, sum);
System.out.println(maxSum);
编号： ADV-3
题目：金属采集
关键字：树形动态规划 类型：普通试题 问题描述：
人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 n 个节点，这些节点被编号为 1~n 。人类将 k 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着落点， S 号节点。每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息，包括它的两个端点 x 和 y，以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。
输入格式
第一行包含三个整数 n, S 和 k ，分别代表节点个数、着落点编号，和机器人个数。
接下来一共 n-1 行，每行描述一条道路。一行含有三个整数 x, y 和 w ，代表在 x 号节点和 y 号节点之间有一条道路，通过需要花费 w 个单位的能量。所有道路都可以双向通行。
输出格式
输出一个整数，代表采集所有节点的金属所需要的最少能量。 样例输入 6 1 3 1 2 1 2 3 1 2 4 1000 2 5 1000 1 6 1000 样例输出 3004