【Java】蓝桥杯算法提高ADV（二）

待我称王封你为后i 2023-05-21 15:14 9阅读 0赞

###  ###

*  ADV-99 算法提高 栅格打印问题（模拟）
 *  ADV-126 算法提高 扫雷（模拟）
 *  ADV-302 算法提高 秘密行动（dp）
 *  ADV-305 算法提高 输出二进制表示（API）
 *  ADV-327 算法提高 研究兔子的土豪（斐波那契循环节）

# ADV-99 算法提高 栅格打印问题（模拟） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T210][http_lx.lanqiao.cn_problem.page_gpid_T210]

--------------------

**【问题描述】**

编写一个程序，输入两个整数，作为栅格的高度和宽度，然后用“+”、“-”和“|”这三个字符来打印一个栅格。  
输入格式：  
输出格式：  
输入输出样例

--------------------

**【输入格式】**

输入只有一行，包括两个整数，分别为栅格的高度和宽度。

--------------------

**【输出格式】**

输出相应的栅格。

--------------------

**【样例输入】**

3 2

--------------------

**【样例输出】**

+-+-+
    | | |
    +-+-+
    | | |
    +-+-+
    | | |
    +-+-+

--------------------

**思路：** 题不难，就是有个坑，如果行或者列为 0 ，就直接结束。

**Code：**

import java.util.Scanner;
    public class Main { 
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt(), m = cin.nextInt();
          	if(n==0 || m==0)	return;
    		for(int i=1;i<=2*n+1;i++) { 
    			for(int j=1;j<=2*m+1;j++) { 
    				if(i%2==1) { 
    					if(j%2==1)	System.out.print("+");
    					else	System.out.print("-");
    				}
    				else { 
    					if(j%2==1)	System.out.print("|");
    					else	System.out.print(" ");
    				}
    			}
    			System.out.println();
    		}
    	}
    }

# ADV-126 算法提高 扫雷（模拟） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T264][http_lx.lanqiao.cn_problem.page_gpid_T264]

--------------------

**【问题描述】**

扫雷游戏你一定玩过吧！现在给你若干个n×m的地雷阵，请你计算出每个矩阵中每个单元格相邻单元格内地雷的个数，每个单元格最多有8个相邻的单元格。 0<n,m<=100

--------------------

**【输入格式】**

输入包含若干个矩阵，对于每个矩阵，第一行包含两个整数n和m，分别表示这个矩阵的行数和列数。接下来n行每行包含m个字符。安全区域用‘.’表示，有地雷区域用’\*'表示。当n=m=0时输入结束。

--------------------

**【输出格式】**

对于第i个矩阵，首先在单独的一行里打印序号：“Field \#i:”,接下来的n行中，读入的’.'应被该位置周围的地雷数所代替。输出的每两个矩阵必须用一个空行隔开。

--------------------

**【样例输入】**

4 4  
*…  
…  
.*…  
…  
3 5  
\*\*…  
…  
.\*…  
0 0

--------------------

**【样例输出】**

Field \#1:  
*100  
2210  
1*10  
1110

Field \#2:  
\*\*100  
33200  
1\*100  
（注意两个矩阵之间应该有一个空行，由于oj的格式化这里不能显示出来）

--------------------

**【数据规模和约定】**

0<n,m<=100

--------------------

**思路：** 水题，对于空白的点直接计算周围的地雷数，并存入数组。

**Code：**

import java.util.Arrays;
    import java.util.Scanner;
    public class Main { 
    	static char[][] ch = new char[105][105];
    	static int[][] a = new int[105][105];
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner cin = new Scanner(System.in);
    		int t=1;
    		while(cin.hasNext()) { 
    			int n = cin.nextInt();
    			int m = cin.nextInt();
    			if(n==0 || m==0)	break;
    			for(int i=1;i<=n;i++)
    				for(int j=1;j<=m;j++)
    					a[i][j]=0;
    			for(int i=1;i<=n;i++) { 
    				String str=cin.next();
    				for(int j=1;j<=m;j++)
    					ch[i][j] = str.charAt(j-1);
    			}
    			for(int i=1;i<=n;i++) { 
    				for(int j=1;j<=m;j++) { 
    					if(ch[i][j]=='.') { 
    						if(ch[i-1][j-1]=='*' && i-1>=1 && j-1>=1)	a[i][j]++;
    						if(ch[i-1][j]=='*' && i-1>=1)		a[i][j]++;
    						if(ch[i-1][j+1]=='*' && i-1>=1 && j+1<=m)	a[i][j]++;
    						if(ch[i][j-1]=='*' && j-1>=1)		a[i][j]++;
    						if(ch[i][j+1]=='*' && j+1<=m)		a[i][j]++;
    						if(ch[i+1][j-1]=='*' && i+1<=n && j-1>=1)	a[i][j]++;
    						if(ch[i+1][j]=='*' && i+1<=n)		a[i][j]++;
    						if(ch[i+1][j+1]=='*' && i+1<=n && j+1<=m)	a[i][j]++;
    					}
    				}
    			}
    			System.out.println("Field #" + t + ":");
    			for(int i=1;i<=n;i++) { 
    				for(int j=1;j<=m;j++) { 
    					if(ch[i][j]=='.')	
    						System.out.print(a[i][j]);
    					else
    						System.out.print(ch[i][j]);
    				}
    				System.out.println();
    			}
    			System.out.println();
    			t++;
    		}
    	}
    }

# ADV-302 算法提高 秘密行动（dp） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T581][http_lx.lanqiao.cn_problem.page_gpid_T581]

--------------------

**【问题描述】**

小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。

--------------------

**【输入格式】**

第一行包含一个整数n，代表楼的高度。

接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。

--------------------

**【输出格式】**

输出1行，包含一个整数，表示所需的最短时间。

--------------------

**【样例输入】**

5  
3  
5  
1  
8  
4

--------------------

**【样例输出】**

--------------------

**【数据规模和约定】**

对20%的数据,n<=10  
对40%的数据,n<=100  
对60%的数据,n<=5000  
对100%的数据,n<=10000

--------------------

**思路：**

假设现在小D到达了第 i 层,那么他有三种途径到达第 i 层

1.  从第 i - 1层爬到第 i 层
2.  从第 i - 1层跳到第 i 层
3.  从第 i - 2层跳到第 i 层

其实可以分为两种情况：是爬到第 i 层还是跳到第 i 层。用二维数组 dp\[i\]\[0\] 表示爬到第 i 层的最小花费时间，dp\[i\]\[1\] 表示跳到第 i 层的最小花费时间。

*  如果是爬到第 i 层，那么肯定要花费 a\[i\] 的时间。由于这次是爬的，那么上一次可以是跳到第 i - 1 层，也可以是爬到第 i - 1 层，取两者最小值。即 dp\[i\]\[0\] = Math.min(dp\[i-1\]\[0\], dp\[i-1\]\[1\])+a\[i\]
 *  如果是跳到第 i 层，那么这次不花费时间，同时上一次肯定是爬到第 i - 1 层。而跳可以跳一层也可以跳两层，取两者的最小值 dp\[i\]\[1\] = Math.min(dp\[i-1\]\[0\], dp\[i-2\]\[0\])

**Code：**

import java.util.*;
    public class Main { 
    	static int[] a = new int[100010];
    	static int[][] dp = new int[100010][2];
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt();
    		for(int i=1;i<=n;i++)
    			a[i] = cin.nextInt();
    		dp[1][0]=a[1];	dp[1][1]=0;
    		for(int i=2;i<=n;i++) { 
    			dp[i][0] = Math.min(dp[i-1][0], dp[i-1][1])+a[i];
    			dp[i][1] = Math.min(dp[i-1][0], dp[i-2][0]);
    		}
    		System.out.println(Math.min(dp[n][0], dp[n][1]));
    	}
    }

# ADV-305 算法提高 输出二进制表示（API） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T588][http_lx.lanqiao.cn_problem.page_gpid_T588]

--------------------

**【问题描述】**

输入\[-128，127\]内的整数，输出其二进制表示。提示，可使用按位与&

--------------------

**【输入格式】**

例：7

--------------------

**【输出格式】**

例：00000111

--------------------

**【样例输入】**

一个满足题目要求的输入范例。  
例：  
7

--------------------

**【样例输出】**

与上面的样例输入对应的输出。  
例：  
00000111

--------------------

**【数据规模和约定】**

输入数据中每一个数的范围。  
例：0<n,m<100, 0<=矩阵中的每个数<=1000。

--------------------

**思路：** 直接调用 java 的 api ，Integer.toBinaryString(n) 可直接将 n 转换为二进制数。如果 n 是负数，可直接用 s.substring(24) 将二进制数转换为补码。

**Code：**

import java.util.*;
    import java.math.*;
    public class Main { 
    	public static void main(String[] args) { 
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt();
    		String s = Integer.toBinaryString(n);
    		for(int i=s.length();i<8;i++)
    			s = "0" + s;
    		if(n<0) s = s.substring(24);
    		System.out.println(s);
    	}
    }

# ADV-327 算法提高 研究兔子的土豪（斐波那契循环节） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T623][http_lx.lanqiao.cn_problem.page_gpid_T623]

--------------------

**【问题描述】**

某天，HWD老师开始研究兔子，因为他是个土豪，所以他居然一下子买了一个可以容纳10^18代兔子的巨大笼子（好像比我们伟大的地球母亲大一点点？），并开始研究它们，之后，他了解了兔子的繁衍规律：即fibonacci数列。

兔子繁殖了n代后，HWD老师很开心。  
　　  
但是，HWD老师有密集恐惧症，所以，他只能去卖了兔子，他找到了一个好的雇主，但是这个雇主有强迫症，他只每次收购1007只兔子，HWD老师为了避免自己的密集恐惧症，要尽量多的卖了兔子。  
　　  
但是即便是密集恐惧症，也打击不了HWD老师研究兔子的决心，他数着数着自己剩下的兔子……

--------------------

**【输入格式】**

HWD老师让兔子繁衍了几代（一个整数，没有其他字符）。

--------------------

**【输出格式】**

HWD老师剩余（残余？）的兔子（一个整数，忽略行尾回车及空格）。

--------------------

**【样例输入】**

--------------------

**【样例输出】**

--------------------

**【数据规模和约定】**

兔子的总量最大时小于HWD老师笼子的大小。

f\[1\]=1，f\[2\]=1，f\[3\]=2 ……

--------------------

**思路：** 有几点要注意的。

*  数据规模很大，所以最好定义为 long 型。
 *  要找出斐波那契数列的循环节，不然肯定会超时。
 *  同时，不要用数组要存，数组肯定定义不了那么大的，会溢出。

**Code：**

import java.util.Scanner;
    public class Main { 
    	static int mod = 1007;
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner cin = new Scanner(System.in);
    		long n = cin.nextLong();
    		if(n == 1 || n == 2) { 
    			System.out.println(1);
    			return;
    		}
    		long a = 1, b = 1,c = 0;
    		long len = 0;
    		n %= 108;
    		for (int i = 3; i <= n; i++) { 
    			c = (a + b) % mod;		
    			/*在这里可以求出循环节长度 len == 108 if(c == 1 && b == 1) { len = i - 2; break; } */		
    			a = b;
    			b = c;		
    		}
    		//System.out.println(len);
    		System.out.println(c % mod);
    	}
    }

[http_lx.lanqiao.cn_problem.page_gpid_T210]: http://lx.lanqiao.cn/problem.page?gpid=T210
[http_lx.lanqiao.cn_problem.page_gpid_T264]: http://lx.lanqiao.cn/problem.page?gpid=T264
[http_lx.lanqiao.cn_problem.page_gpid_T581]: http://lx.lanqiao.cn/problem.page?gpid=T581
[http_lx.lanqiao.cn_problem.page_gpid_T588]: http://lx.lanqiao.cn/problem.page?gpid=T588
[http_lx.lanqiao.cn_problem.page_gpid_T623]: http://lx.lanqiao.cn/problem.page?gpid=T623