《蓝桥杯算法提高题和官方的答案》由会员分享，可在线阅读，更多相关《蓝桥杯算法提高题和官方的答案（290页珍藏版）》请在金锄头文库上搜索。
1、 .wd.算法提高编号： ADV-1题目： 两条直线 关键字：排序类型：普通试题问题描述：给定平面上n个点。求两条直线，这两条直线互相垂直，而且它们与x轴的夹角为45度，并且n个点中离这两条直线的曼哈顿距离的最大值最小。两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和，一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。输入格式第一行包含一个数n。接下来n行，每行包含两个整数，表示n个点的坐标横纵坐标的绝对值小于109。输出格式输出一个值，表示最小的最大曼哈顿距离的值，保存一位小数。样例输入41 00 12 11 2样例输出1.0数据规模与约定对
2、于30%的数据，n=100。对于另外30%的数据，坐标范的绝对值小于100。对于100%的数据，n=105。参考代码：该题暂时没有人完全正确，暂时没有该语言的参考程序。编号： ADV-2题目：矩阵翻转 关键字：枚举 贪心类型：普通试题问题描述：Ciel有一个N*N的矩阵，每个格子里都有一个整数。N是一个奇数，设X = (N+1)/2。Ciel每次都可以做这样的一次操作：他从矩阵选出一个X*X的子矩阵，并将这个子矩阵中的所有整数都乘以-1。现在问你经过一些操作之后，矩阵中所有数的和最大可以为多少。输入格式第一行为一个正整数N。接下来N行每行有N个整数，表示初始矩阵中的数字。每个数的绝对值不超过1
3、000。输出格式输出一个整数，表示操作后矩阵中所有数之和的最大值。样例输入3-1 -1 1-1 1 -11 -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() 57) int mark = 1,
4、 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;
5、for (int i = 0; i 0) sum += dpsymbolix + 1symbolxj + 1symbolxx + 1ij;continue;int i2 = x + i + 1;int j2 = x + j + 1;int temp = mapij;temp += mapij2 * symbolix;temp += mapi2j * symbolxj;temp += mapi2j2 * symboli2x * symbolxj2;sum += Math.abs(temp);dpsymbolix + 1symbolxj + 1symbolxx + 1ij = Math.abs(t
6、emp);return sum;public static void main(String args) MyScanner sc = new MyScanner();int n = sc.nextInt();map = new intnn;symbol = new intnn;dp = new int333nn;for (int i = 0; i n; +i) for (int j = 0; j = 0; -count) int k = count;int center = (k & 1) 0 ? 1 : -1;k = 1;symbolxx = center;int sum = mapxx
7、* center;for (int j = 0; j 0 ? 1 : -1;symboljx = t;symbolx + j + 1x = t * center;sum += mapjx * t;sum += mapx + j + 1x * t * center;k = 1;for (int j = 0; j 6 ，在 6 号节点返回地球，花费能量为1000。第二个机器人的行走路径为 1-2-3-2-4 ，在 4 号节点返回地球，花费能量为1003。第一个机器人的行走路径为 1-2-5 ，在 5 号节点返回地球，花费能量为1001。数据规模与约定此题有10个测试点。对于测试点 12 ， n =
8、 10 ， k = 5 。对于测试点 3 ， n = 100000 ， k = 1 。对于测试点 4 ， n = 1000 ， k = 2 。对于测试点 56 ， n = 1000 ， k = 10 。对于测试点 710 ， n = 100000 ， k = 10 。道路的能量 w 均为不超过 1000 的正整数。参考代码：import java.io.IOException;import java.io.InputStream;import java.util.HashMap;import java.util.Iterator;import java.util.LinkedList;publ
9、ic class Main private static class MyScanner private InputStream is = System.in;public int nextInt() try int i;while (i = is.read() 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 class Node
