《蓝桥杯算法提高题与官方答案》由会员分享，可在线阅读，更多相关《蓝桥杯算法提高题与官方答案（292页珍藏版）》请在金锄头文库上搜索。
1、算法提高算法提高编号： ADV-1题目： 两条直线 关键字：排序类型：普通试题问题描述：给定平面上 n 个点。求两条直线，这两条直线互相垂直，而且它们与 x 轴的夹角为 45 度，并且 n 个点中离这两条直线的曼哈顿距离的最大值最小。两点之间的曼哈顿距离定义为横坐标的差的绝对值与纵坐标的差的绝对值之和，一个点到两条直线的曼哈顿距离是指该点到两条直线上的所有点的曼哈顿距离中的最小值。输入格式第一行包含一个数 n。接下来 n 行，每行包含两个整数，表示 n 个点的坐标（横纵坐标的绝对值小于 109）。输出格式输出一个值，表示最小的最大曼哈顿距离的值，保留一位小数。样例输入41 00 12 11 2
2、样例输出1.0数据规模与约定对于 30%的数据，n 57) int mark = 1, temp = 0;if (i = 45) mark = -1;i = is.read();while (i 47 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 + 1symbolx
3、j + 1symbolxx + 1ij = Math.abs(temp);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 = 0; -count) int k = count;int center = (k k = 1;symbolxx = center;int sum = mapxx * center;
4、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 57) i
5、nt mark = 1, temp = 0;if (i = 45) mark = -1;i = is.read();while (i 47 public Node() dp = new intk + 1;nodes = new HashMap();stack.push(i);while (!stack.isEmpty() i = stack.pop();Node root = nodeListi;for (Iterator it = root.nodes.keySet().iterator(); it.hasNext();) int j = it.next();Node sub = nodeL
6、istj;sub.nodes.remove(i);if (!sub.nodes.isEmpty() stack.push(i);stack.push(j);break;int cost = root.nodes.get(j);for (int num = k; num = 0; -num) root.dpnum += sub.dp0 + 2 * cost;for (int l = 1; l Bi 的单向通行。实际上，如果现在有一条航路是从 Ai 到 Bi 的话，那么意味着肯定没有通行方案从 Bi 回到 Ai。农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛
7、？配送中心位于城镇 S 中（1 countdp; i-) countdp + 1 = i;Dp(dp + 1);private static int getbig(int dp) for (int i = 1; i = countj) Valuei = Math.min(Valuei, Valuei - countj + 1);if (Valuei N) if (i sum0) sum0 = i;for (int j = 1; j round = 0 while A is not sorted round := round + 1 for i := 1 to n - 1 if (Ai Ai +
8、 1) swap(Ai, Ai + 1)求 1 n 的排列中，有多少个排列使得 A 被扫描了 K 遍，亦即算法结束时 round = K。答案模 20100713 输出。输入格式输入包含多组数据。每组数据为一行两个整数 N，K。输出格式对每组数据，输出一行一个整数表示答案。样例输入33 03 13 2样例输出132数据规模和约定T = arr.length - 1 - ii) System.out.println();for (int i = 0; i 9 ? h : (“0“ + h) + “:“+ (m 9 ? m : (“0“ + m) + “:“ + (t 9 ? t : (“0“ +
9、 t);编号：ADV-13题目：最小乘积(提高型) 关键字：算法类型：vip 试题问题描述给两组数，各 n 个。请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。例如两组数分别为:1 3 -5 和-2 4 1那么对应乘积取和的最小值应为：(-5) * 4 + 3 * (-2) + 1 * 1 = -25输入格式第一个行一个数 T 表示数据组数。后面每组数据，先读入一个 n，接下来两行每行 n 个数，每个数的绝对值小于等于 1000。n one = new PriorityQueue();public static void main(Strin
10、g args) throws IOException StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in);st.nextToken();int t = (int) st.nval;while (t- 0) st.nextToken();n = (int) st.nval;one.clear();two.clear();for (int i = 0; i onelist = new LinkedList();LinkedList twolist = new Lin
11、kedList();while (!one.isEmpty() onelist.add(one.poll();twolist.add(two.poll();int maxo, mino, maxt, mint, result = 0;while (!onelist.isEmpty() maxo = onelist.getLast();mint = twolist.getFirst();mino = onelist.getFirst();maxt = twolist.getLast();if (maxo * mint #include#includechar mm10515;char s115,
12、s215;int link1052;int length105=0;int in105;int N;typedef structchar name15;int num;girl;void fun(int x)int i,y;for(i=0;i=lengthy?lengthx+1:lengthy;fun(y);int comp(const void *a, const void *b)return (*(girl *)a).num(*(girl *)b).num?1:-1;int main()int i,j,T,n,f,x,y,sum=0;girl g105;scanf(“%d“,while(T
13、-)memset(mm,0,sizeof(mm);memset(link,0,sizeof(mm);memset(in,0,sizeof(in);memset(length,0,sizeof(length);scanf(“%d“,n=0;for(i=0;i 0) s = 0x80000000;t-;int n = in.nextInt();int m = in.nextInt();int num = new intn;for (int i = 0; i s)s=sum;if(i=0)count(num,i+1,m-1,n,sum*numi);count(num,i+1,m,n,sum);pub
14、lic static void main(String args) new Main().input();编号：ADV-16题目：和最大子序列 关键字：算法类型：vip 试题问题描述对于一个给定的长度为 N 的整数序列 A，它的“子序列”的定义是：A 中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。输入格式输入文件的第一行包含一个整数 N，第二行包含 N 个整数，表示 A。其中1 hm = new LinkedHashMap();public static void mai
15、n(String args) throws IOException BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in);String str = bfr.readLine();str = str.replace(“,“,“);str = str.replace(“.“,“);/System.out.println(str);method(str);printAll();public static void method(String str)if (!str.contains(“ “)hm.put(str,1);return;String arr = new String2;while(str.contains(“ “)arr = str.split(“ “);Integer i = hm.get(arr0.toUpperCase();if( i = null)hm.put(arr0.toUpperCase(), 1)
