#|蓝桥杯31天冲刺打卡题解（Day10）蓝桥杯|算法|java|bfs|职场和发展

Day10 第一题第十届2019年蓝桥杯省赛
扫地机器人
JavaC组第10题
二分
首先我们分析，有N个方格，K个机器人，我们想让时间达到最短，那么每个机器人扫的区间要尽量达到平均值N/K，所以这道题是让我们求每个机器人实际清扫的范围，所以这道题其实是一道搜索的问题。
因为这道题是压轴题，必然不可能用dfs、bfs简单的求解，所以我们想到了二分搜索。
我们要使每个机器人搜索的范围尽可能的小，同时还要保证所有方格都被机器人扫到，我们可以遍历每个机器人的位置依次判断，写一个check(x)函数，x是当前选定的搜索范围，定义一个变量total = 0表示从左到右依次能够清扫的范围。
数组robot用来存储机器人的位置，如果robot[i] - x <= total的话，那么说明我们选择的x还是合适的，total是第i - 1个机器人所能扫描的右边界：

文章图片

如果不能满足上述条件，说明范围选小了，返回false重新确定区间：

文章图片

import java.util.Arrays; import java.util.Scanner; public class Main {static int N, K; static int[] robot; // 机器人的坐标public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); K = sc.nextInt(); robot = new int[K]; for (int i = 0; i < K; i++) robot[i] = sc.nextInt(); Arrays.sort(robot); // 给定的位置是乱序的int l = 0, r = N, ans = 0; while (l < r) { int mid = (l + r) / 2; if (check(mid)) { r = mid - 1; ans = mid; } else l = mid + 1; }System.out.print((ans - 1) * 2); // 还要返回原来的位置 }private static boolean check(int x){ int total = 0; // 记录机器人已经扫描过的范围 for (int i = 0; i < K; i++) { // 遍历这K个机器人 if (robot[i] - x <= total) { // 第i个机器人能够清扫到的左边界在第i-1个机器人能够清扫到的右边界的范围内 if (total >= robot[i]) { // 第i-1个机器人能够清扫的范围的右边界包含了第i个机器人的起始位置 total = robot[i] + x - 1; } else { // 当前扫描范围离下一个机器人有一段距离 total += x; } } else return false; // 说明边界选小了 } return total >= N; // 当最大扫描位置大于等于总区间则返回true } }

第二题第九届2018年蓝桥杯省赛
全球变暖
这题我之前写了题解，用的bfs，在最后一题，链接：蓝桥杯AcWing学习笔记 6-2宽搜BFS的学习
第三题第三届2012年蓝桥杯国赛
机器人行走
C++高职组第3题
模拟题，原谅我不是很会…直接给大家贴代码了

import java.util.Scanner; public class Main {static String left = "ULDR"; static String right = "URDL"; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); double[] result = new double[n]; for (int i = 0; i < n; i++) { String s = sc.next(); result[i] = getResult(s); } for (int i = 0; i < n; i++) { System.out.printf("%.2f\n", result[i]); } }private static double getResult(String s) { double r = 0, x = 0, y = 0; char way = 'U'; for(int i = 0; i < s.length(); i++) { int start = i; if(s.charAt(start) >= '0' && s.charAt(start) <= '9') { while(start < s.length() && s.charAt(start) >= '0' && s.charAt(start) <= '9') start++; int num = Integer.parseInt(s.substring(i, start)); if(way == 'U') y += num; else if(way == 'L') x -= num; else if(way == 'D') y -= num; else if(way == 'R') x += num; i = start - 1; } else { char temp = s.charAt(i); if (temp == 'L') { int p = left.indexOf(way + ""); p = (p + 1) % 4; way = left.charAt(p); } else if (temp == 'R') { int p = right.indexOf(way + ""); p = (p + 1) % 4; way = right.charAt(p); } } } r = Math.sqrt(x * x + y * y); return r; } }

第四题模板题
数的次幂
快速幂
【#|蓝桥杯31天冲刺打卡题解（Day10）】需要用快读才能AC这道题。

import java.io.*; public class Main {// 快读模板 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StreamTokenizer IN = new StreamTokenizer(br); public static void main(String[] args) throws IOException { int t = nextInt(); while(t-- > 0) { long n = nextInt(); long m = nextInt(); long p = nextInt(); long res = 1; while(m > 0) { // 快速幂模板 if(m % 2 == 1) { // 最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积 res = res * n % p; } m /= 2; n = n * n % p; }System.out.println(res % p); } }private static int nextInt() throws IOException { IN.nextToken(); return (int)IN.nval; } }