2017第八届蓝桥杯国赛JAVA B组真题解析（带源码及解析）

爱被打了一巴掌 2022-11-21 14:12 202阅读 0赞

## [蓝桥杯历年真题及解析][Link 1]. ##

### 目录 ###

*   *  蓝桥杯历年真题及解析.
     *   *   *  A：平方十位数（难度：★）.
             *   *  分析：
                 *  AC代码：
             *  B：生命游戏（难度：★★★★）.
             *   *  分析：
                 *  AC代码：
             *  C：树形显示（难度：★）.
             *   *  分析：
                 *  AC代码：
             *  D：小计算器（难度：★★）.
             *   *  分析：
                 *  AC代码：
             *  E：填字母游戏（难度：★★★）.
             *   *  分析：
                 *  AC代码：
             *  F：区间移位（难度：★★★★★）.
             *   *  分析：
                 *  AC代码：

#### A：平方十位数（难度：★）. ####

由0~9这10个数字不重复、不遗漏，可以组成很多10位数字。  
这其中也有很多恰好是平方数（是某个数的平方）。

比如：1026753849，就是其中最小的一个平方数。

请你找出其中最大的一个平方数是多少？

注意：你需要提交的是一个10位数字，不要填写任何多余内容。

##### 分析： #####

全排列枚举出所有排列情况，  
对每一种情况进行Check即可

##### AC代码： #####

![在这里插入图片描述][20201101223254444.png_pic_center]

public class Main { 
    	public static long ans = 0;
    	public static int arr[] = {  0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    	public static void tolong() { 
    		long t = 0;
    		for (int i = 0; i < 10; i++) { 
    			t *= 10;
    			t += arr[i];
    		}
    		long x = (long) Math.sqrt(t);
    		if (x * x == t)
    			ans = Math.max(ans, t);
    	}
    
    	public static void qpl(int k) { 
    		if (k >= arr.length)
    			tolong();
    		else { 
    			for (int i = k; i < arr.length; i++) { 
    				int t = arr[i];
    				arr[i] = arr[k];
    				arr[k] = t;
    				qpl(k + 1);
    				t = arr[i];
    				arr[i] = arr[k];
    				arr[k] = t;
    			}
    		}
    	}
    
    	public static void main(String[] args) { 
    		qpl(0);
    		System.out.println(ans);
    	}
    }

#### B：生命游戏（难度：★★★★）. ####

康威生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。  
这个游戏在一个无限大的2D网格上进行。

初始时，每个小方格中居住着一个活着或死了的细胞。  
下一时刻每个细胞的状态都由它周围八个格子的细胞状态决定。

具体来说：

1.  当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少）
2.  当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。
3.  当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
4.  当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖）

当前代所有细胞同时被以上规则处理后, 可以得到下一代细胞图。按规则继续处理这一代的细胞图，可以得到再下一代的细胞图，周而复始。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]

本题中我们要讨论的是一个非常特殊的模式，被称作"Gosper glider gun"：

![...............................................................X...................................X.X.........................XX......XX............XX.............X...X....XX............XX..XX........X.....X...XX................XX........X...X.XX....X.X.......................X.....X.......X........................X...X..................................XX.............................................................][]

假设以上初始状态是第0代，请问第1000000000(十亿)代一共有多少活着的细胞？

注意：我们假定细胞机在无限的2D网格上推演，并非只有题目中画出的那点空间。  
当然，对于遥远的位置，其初始状态一概为死细胞。

注意：需要提交的是一个整数，不要填写多余内容。

##### 分析： #####

这个题比较复杂，需要有敏锐的观察力，还有一些数论的基础才可以搞。  
首先我们将状态迭代几百次，然后观察规律  
然后就可以轻松的发现每30次迭代是一个周期（这TM谁能发现？？？）  
然后将周期数组储存下来，按照十亿次计算即可。

##### AC代码： #####

![在这里插入图片描述][20201106145008673.png_pic_center]  
//以下程序分两段  
//第一段求周期  
//第二段求结果

import java.util.HashSet;
    public class B生命游戏mod { 
    	public static int maxn=1000;
    	public static char map[][]=new char [maxn][maxn];
    	public static char now[][]=new char [maxn][maxn];
    	public static char c[][]={ 
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','X','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.','.','.','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','X','.','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.',},
    			{ '.','X','X','.','.','.','.','.','.','.','.','X','.','.','.','.','.','X','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','X','X','.','.','.','.','.','.','.','.','X','.','.','.','X','.','X','X','.','.','.','.','X','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','.','.','X','.','.','.','.','.','.','.','X','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','X','.','.','.','X','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
    			{ '.','.','.','.','.','.','.','.','.','.','.','.','.','X','X','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',}
    	};
    
    	public static HashSet<String> set=new HashSet<String>();
    	public static String tos(){ 
    		StringBuilder sBuilder=new StringBuilder();
    		for(int i=0;i<maxn;i++){ 
    			for(int j=0;j<maxn;j++){ 
    				sBuilder.append(map[i][j]);
    			}
    		}
    		return sBuilder.toString();
    	}
    	public static void next(){ 
    		for(int i=1;i<maxn-1;i++){ 
    			for(int j=1;j<maxn-1;j++){ 
    				int cnt=0;
    				for(int x=-1;x<2;x++){ 
    					for(int y=-1;y<2;y++){ 
    						if(x==0&&y==0)continue;
    						if(map[i+x][j+y]=='X')cnt++;
    					}
    				}
    				if(map[i][j]=='X'){ 
    					if(cnt==2||cnt==3)now[i][j]='X';
    					else now[i][j]='.';
    				}else{ 
    					if(cnt==3)now[i][j]='X';
    					else now[i][j]='.';
    				}
    			}
    		}
    		for(int i=1;i<maxn-1;i++){ 
    			for(int j=1;j<maxn-1;j++){ 
    				map[i][j]=now[i][j];
    			}
    		}
    	}
    	public static int comput(){ 
    		int sum=0;
    		for(int i=0;i<maxn;i++){ 
    			for(int j=0;j<maxn;j++){ 
    				if(map[i][j]=='X')sum++;
    			}
    		}
    		return sum;
    	}
    	public static void main(String[] args) { 
    		for(int i=0;i<maxn;i++){ 
    			for(int j=0;j<maxn;j++){ 
    				map[i][j]='.';
    			}
    		}
    		for(int i=0;i<c.length;i++){ 
    			for(int j=0;j<c[i].length;j++){ 
    				map[maxn/2+i][maxn/2+j]=c[i][j];
    			}
    		}
    		String string=tos();
    		int cnt=0,sum=0,cur=0;
    		while(!set.contains(string)){ 
    			set.add(string);
    			cnt++;
    			sum=comput();
    			next();
    			string=tos();
    			cur=comput();
    			System.out.print(cur-sum+",");
    			
    			if(cnt%30==0){ 
    				System.out.println();
    			}
    		}
    		System.out.println(cnt+" "+set.size());
    	}
    }

public class Main { 
    	public static int mod[] = {  3, 4, 5, 3, -7, 7, -3, 13, -19, 6, 2, 4, 1, 1, -14, 2, 3, 6, 1, 0, 0, -5, 11, -17, 7,
    			-3, 0, 3, -2, -7 };
    	
    	public static void main(String[] args) { 
    		long ans = 36;
    		for (int i = 1; i < mod.length; i++)
    			mod[i] += mod[i - 1];
    		ans += (1000000000 / 30) * mod[mod.length - 1];
    		ans += mod[1000000000 % 30 - 1];
    		System.out.println(ans);
    	}
    }

#### C：树形显示（难度：★）. ####

对于分类结构可以用树形来形象地表示。比如：文件系统就是典型的例子。

树中的结节具有父子关系。我们在显示的时候，把子项向右缩进（用空格，不是tab），并添加必要的连接线，以使其层次关系更醒目。

下面的代码就是为了这个目的的，请仔细阅读源码，并填写划线部分缺少的代码。

import java.util.*;
    
    class MyTree
    { 
    	private Map<String, List<String>>  map_ch = new HashMap<String, List<String>>();
    	private Map<String,String> map_pa = new HashMap<String,String>();
    	
    	public void add(String parent, String child)
    	{ 
    		map_pa.put(child, parent);
    		
    		List<String> lst = map_ch.get(parent);
    		if(lst==null){ 
    			lst = new ArrayList<String>();
    			map_ch.put(parent, lst);
    		}
    		lst.add(child);
    	}
    	
    	public String get_parent(String me){ 
    		return map_pa.get(me);
    	}
    	
    	public List<String> get_child(String me){ 
    		return map_ch.get(me);
    	}
    	
    	private String space(int n)
    	{ 
    		String s = "";
    		for(int i=0; i<n; i++) s += ' ';
    		return s;
    	}
    	
    	private boolean last_child(String x){ 
    		String pa = map_pa.get(x);
    		if(pa==null) return true;
    		
    		List<String> lst = map_ch.get(pa);
    		return lst.get(lst.size()-1).equals(x);
    	}
    	
    	public void show(String x){ 
    		
    		String s = "+--" + x;
    		
    		String pa = x;
    		while(true){ 
    			pa = map_pa.get(pa);
    			if(pa==null) break;
    			s = ___________________________________ ;  // 填空
    		}
    		
    		System.out.println(s);
    	}
    	
    	public void dfs(String x){ 
    		show(x);
    		
    		List<String> lst = map_ch.get(x);
    		if(lst==null) return;
    				
    		for(String it: lst){ 
    			dfs(it);
    		}
    	}
    }
    
    public class TreeView
    { 
    	public static void main(String[] args)
    	{ 
    		MyTree tree = new MyTree();
    		tree.add("root", "dog");
    		tree.add("root", "cat");
    		tree.add("root", "duck");
    		tree.add("dog", "AAdog");
    		tree.add("dog", "BBdog");
    		tree.add("dog", "CCdog");
    		tree.add("AAdog", "AAdog01");
    		tree.add("AAdog", "AAdog02");
    		tree.add("cat", "XXcat");
    		tree.add("cat", "YYcat");
    		tree.add("XXcat","XXcat-oo");
    		tree.add("XXcat","XXcat-qq");
    		tree.add("XXcat-qq", "XXcat-qq-hahah");
    		tree.add("duck", "TTduck");
    		tree.add("TTduck", "TTduck-001");
    		tree.add("TTduck", "TTduck-002");
    		tree.add("TTduck", "TTduck-003");
    		tree.add("YYcat","YYcat.hello");
    		tree.add("YYcat","YYcat.yes");
    		tree.add("YYcat","YYcat.me");		
    		
    		tree.dfs("root");
    	}
    }

对于题目中的测试数据，输出结果:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 2]

注意，只填写划线部分缺少的代码，不要抄写已有的代码或符号。

##### 分析： #####

观察题目发现我们只需要做一个字符串拼接的工作，  
而且我们观察图发现，  
当本节点是父结点的最后一个节点时，不需要有|，其他情况有|  
所以我们推测拼接方式为s=(last\_child(pa)?" “:”|")+space(4)+s;

##### AC代码： #####

不能交题，但是运行结果是正确的

package JAVA2017;
    
    import java.util.*;
    
    public class C树形显示 { 
    	public static void main(String[] args) { 
    		MyTree tree = new MyTree();
    		tree.add("root", "dog");
    		tree.add("root", "cat");
    		tree.add("root", "duck");
    		tree.add("dog", "AAdog");
    		tree.add("dog", "BBdog");
    		tree.add("dog", "CCdog");
    		tree.add("AAdog", "AAdog01");
    		tree.add("AAdog", "AAdog02");
    		tree.add("cat", "XXcat");
    		tree.add("cat", "YYcat");
    		tree.add("XXcat", "XXcat-oo");
    		tree.add("XXcat", "XXcat-qq");
    		tree.add("XXcat-qq", "XXcat-qq-hahah");
    		tree.add("duck", "TTduck");
    		tree.add("TTduck", "TTduck-001");
    		tree.add("TTduck", "TTduck-002");
    		tree.add("TTduck", "TTduck-003");
    		tree.add("YYcat", "YYcat.hello");
    		tree.add("YYcat", "YYcat.yes");
    		tree.add("YYcat", "YYcat.me");
    
    		tree.dfs("root");
    	}
    }
    
    class MyTree { 
    	private Map<String, List<String>> map_ch = new HashMap<String, List<String>>();
    	private Map<String, String> map_pa = new HashMap<String, String>();
    
    	public void add(String parent, String child) { 
    		map_pa.put(child, parent);
    
    		List<String> lst = map_ch.get(parent);
    		if (lst == null) { 
    			lst = new ArrayList<String>();
    			map_ch.put(parent, lst);
    		}
    		lst.add(child);
    	}
    
    	public String get_parent(String me) { 
    		return map_pa.get(me);
    	}
    
    	public List<String> get_child(String me) { 
    		return map_ch.get(me);
    	}
    
    	private String space(int n) { 
    		String s = "";
    		for (int i = 0; i < n; i++)
    			s += ' ';
    		return s;
    	}
    
    	private boolean last_child(String x) { 
    		String pa = map_pa.get(x);
    		if (pa == null)
    			return true;
    		List<String> lst = map_ch.get(pa);
    		return lst.get(lst.size() - 1).equals(x);
    	}
    
    	public void show(String x) { 
    
    		String s = "+--" + x;
    
    		String pa = x;
    		while (true) { 
    			pa = map_pa.get(pa);
    			if (pa == null)
    				break;
    			//也对
    // s=(map_pa.get(pa)==null||get_child(map_pa.get(pa)).indexOf(pa)==get_child(map_pa.get(pa)).size()-1?" ":"| ")+s;
    			s=(last_child(pa)?" ":"|")+space(4)+s;
    			// s = ___________________________________ ; // 填空
    		}
    
    		System.out.println(s);
    	}
    
    	public void dfs(String x) { 
    		show(x);
    
    		List<String> lst = map_ch.get(x);
    		if (lst == null)
    			return;
    
    		for (String it : lst) { 
    			dfs(it);
    		}
    	}
    }

#### D：小计算器（难度：★★）. ####

模拟程序型计算器，依次输入指令，可能包含的指令有

1.  数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
2.  运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
3.  进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
4.  输出指令：‘EQUAL’，以当前进制输出结果
5.  重置指令：‘CLEAR’，清除当前数字

指令按照以下规则给出：  
数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出  
运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令  
重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令  
进制转换指令可能出现在任何地方

运算过程中中间变量均为非负整数，且小于2^63。  
以大写的’A’'Z’表示1035

\[输入格式\]  
第1行：1个n，表示指令数量  
第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则

\[输出格式\]  
依次给出每一次’EQUAL’得到的结果

\[样例输入\]  
7  
CLEAR  
NUM 1024  
CHANGE 2  
ADD  
NUM 100000  
CHANGE 8  
EQUAL

\[样例输出\]  
2040

补充说明：

1.  n 值范围: 1<= n < 50000
2.  初始默认的进制是十进制

##### 分析： #####

简单的计算器处理问题，  
对于数据的存储，我们只采用十进制存储即可  
如果需要输出，再把十进制转成对应的R进制  
然后我们定义两个变量nums\[2\]用来存放数据即可  
对于每次不同的操作采取不同的措施+ - \* / % 运算

不过要注意的是，输出的多进制要采用大写输出，否则结果不正确，  
如abc应该写成ABC

##### AC代码： #####

![在这里插入图片描述][20201106153627216.png_pic_center]

import java.util.Scanner;
    //大小写敏感
    public class Main { 
    	public static long nums[]=new long[2];
    	public static int p=0,r=10;
    	public static String op;
    	public static void comput(){ 
    		if(op.equals("ADD")){ 
    			nums[0]+=nums[1];
    		}else if(op.equals("SUB")){ 
    			nums[0]-=nums[1];
    		}else if(op.equals("MUL")){ 
    			nums[0]*=nums[1];
    		}else if(op.equals("DIV")){ 
    			nums[0]/=nums[1];
    		}else if(op.equals("MOD")){ 
    			nums[0]%=nums[1];
    		}
    		nums[1]=0;
    		p=0;
    	}
    	public static void oper(String s[]){ 
    		if(s[0].equals("NUM")){ 
    			nums[p]=Long.parseLong(s[1], r);
    			if(p==1) comput();
    		}else if(s[0].equals("CHANGE")){ 
    			r=Integer.parseInt(s[1]);
    		}else if(s[0].equals("EQUAL")){ 
    			System.out.println(Long.toString(nums[0], r).toUpperCase());
    		}else if(s[0].equals("CLEAR")){ 
    			nums[p]=0;
    		}else{ 
    			p=(p+1)%2;
    			op=s[0];
    		}
    	}
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();sc.nextLine();
    		String s[];
    		while(n-->0){ 
    			s=sc.nextLine().split(" ");
    			oper(s);
    		}
    	}
    }

#### E：填字母游戏（难度：★★★）. ####

小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：  
“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。

K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。

并且：

1.  轮到某人填的时候，只能在某个空格中填入L或O
2.  谁先让字母组成了“LOL”的字样，谁获胜。
3.  如果所有格子都填满了，仍无法组成LOL，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。

本题的输入格式为：  
第一行，数字n（n<10），表示下面有n个初始局面。  
接下来，n行，每行一个串，表示开始的局面。  
比如：![在这里插入图片描述][20201106153943407.png_pic_center]  
![在这里插入图片描述][20201106153958475.png_pic_center]

要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。  
1 表示能赢  
\-1 表示必输  
0 表示可以逼平

例如，  
![在这里插入图片描述][20201106154051656.png_pic_center]

##### 分析： #####

我们定义一个Map，用来存储状态和结果，  
对于每一个没解决的问题，我们针对每个位置可以采取两个方案，  
方案1，放置L  
方案2，放置O  
然后顺次迭代下去，  
理论上分析时间复杂度极高，不过却通过了全部数据。。。

##### AC代码： #####

![在这里插入图片描述][20201106154135421.png_pic_center]

import java.util.*;
    
    public class Main { 
    	static Map<String, Integer> map = new HashMap<String, Integer>();
    
    	// -1: 必输，0: 平局, 1: 必赢
    	static int f(char[] x) { 
    		String s = new String(x);
    		if (map.get(s) != null)
    			return map.get(s);
    
    		if (s.contains("LOL")) { 
    			map.put(s, -1);
    			return -1;
    		}
    		if (s.contains("*") == false) { 
    			map.put(s, 0);
    			return 0;
    		}
    
    		boolean ping = false;
    
    		for (int i = 0; i < x.length; i++) { 
    			if (x[i] == '*') { 
    				try { 
    					x[i] = 'L';
    					int t = f(x);
    					if (t < 0) { 
    						map.put(s, 1);
    						return 1;
    					}
    					if (t == 0)
    						ping = true;
    					x[i] = 'O';
    					t = f(x);
    					if (t < 0) { 
    						map.put(s, 1);
    						return 1;
    					}
    					if (t == 0)
    						ping = true;
    
    				} finally { 
    					x[i] = '*';
    				}
    			}
    		}
    
    		if (ping) { 
    			map.put(s, 0);
    			return 0;
    		}
    
    		map.put(s, -1);
    		return -1;
    	}
    
    	static int game(String s) { 
    		map.clear();
    		return f(s.toCharArray());
    	}
    
    	public static void main(String[] args) { 
    		Scanner scan = new Scanner(System.in);
    
    		int n = Integer.parseInt(scan.nextLine().trim());
    		for (int i = 0; i < n; i++) { 
    			System.out.println(game(scan.nextLine().trim()));
    		}
    	}
    }

#### F：区间移位（难度：★★★★★）. ####

数轴上有n个闭区间：D1,…,Dn。  
其中区间Di用一对整数\[ai, bi\]来描述，满足ai < bi。  
已知这些区间的长度之和至少有10000。  
所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖\[0, 10000\]——也就是说\[0, 10000\]这个区间内的每一个点都落于至少一个区间内。  
你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。

具体来说，假设你将Di移动到\[ai+ci, bi+ci\]这个位置。你希望使得maxi\{|ci|\} 最小。

【输入格式】  
输入的第一行包含一个整数n，表示区间的数量。  
接下来有n行，每行2个整数ai, bi，以一个空格分开，表示区间\[ai, bi\]。  
保证区间的长度之和至少是10000。

【输出格式】  
输出一个数字，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。

【样例输入】  
2  
10 5010  
4980 9980

【样例输出】  
20

【样例说明】  
第一个区间往左移动10；第二个区间往右移动20。

【样例输入】  
4  
0 4000  
3000 5000  
5001 8000  
7000 10000  
【样例输出】  
0.5  
【样例说明】  
第2个区间往右移0.5；第3个区间往左移0.5即可。

【数据规模与约定】  
对于30%的评测用例，1 <= n <= 10；  
对于100%的评测用例，1 <= n <= 10000，0 <= ai < bi <= 10000。

##### 分析： #####

区间压缩算法，待更新  
以后忘了记得催我。。。。

##### AC代码： #####

![在这里插入图片描述][20201031221138562.png_pic_center]

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[20201101223254444.png_pic_center]: /images/20221120/48967d8e5d3c42c48a1b93c65cfd5bc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/54dc943e39f843d5a04a1ecca9124de8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/469237f339f1401a9d2bd90bf074575f.png
[...............................................................X...................................X.X.........................XX......XX............XX.............X...X....XX............XX..XX........X.....X...XX................XX........X...X.XX....X.X.......................X.....X.......X........................X...X..................................XX.............................................................]: /images/20221120/625bd31f68df40eba10762c026d6bd97.png
[20201106145008673.png_pic_center]: /images/20221120/102e7abf6006477a8e1ba9c3454c42d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/69236212a167448598c178474ebed501.png
[20201106153627216.png_pic_center]: /images/20221120/38831d3495a14ef98a28baf5b30c211c.png
[20201106153943407.png_pic_center]: /images/20221120/04b122a8b91f49a8a0ac09051ce960ed.png
[20201106153958475.png_pic_center]: /images/20221120/8ae7139fcac34ebb99530c2a668572ae.png
[20201106154051656.png_pic_center]: https://img-blog.csdnimg.cn/20201106154051656.png#pic_center
[20201106154135421.png_pic_center]: https://img-blog.csdnimg.cn/20201106154135421.png#pic_center
[20201031221138562.png_pic_center]: https://img-blog.csdnimg.cn/20201031221138562.png#pic_center