蓝桥冲刺31天之315

没有一个冬天不可逾越

也没有一个春天不会来临

所有美好的食物，都会有一个等待的过程

低谷时蛰伏，静默时沉淀

做三四月的事，在八九月自有答案

目录

A：0的个数

题目描述:

输入格式

输出格式

样例输入

样例输出

评测用例规模与约定

延伸之字符串：

题解思路：

参考代码：

B：超级质数

题目描述：

题解思路：

答案：

C：卡牌

题目描述：

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

题解思路：

参考代码：

D：染色时间

题目描述：

输入格式

输出格式

样例输入

样例输出

评测用例规模与约定

题解思路：

参考代码：

---

A：0的个数

题目描述:

给定一个正整数 n ，请问 n 的十进制表示中末尾总共有几个 0 ？

输入格式

输入一行包含一个正整数 n。

输出格式

输出一个整数，表示答案。

样例输入

20220000

样例输出
 

4

评测用例规模与约定

对于所有评测用例，1 <= n <= 1000000000

延伸之字符串：

public char charAt(int index)：根据下标获取字符

public int length()：返回字符串的长度

public boolean contains(String str)：判断字符串是否包含特定str

public String trim()：去除前后空格

public String toUpperCase：转换成大写

public String toLowerCase：转换成小写

public String[] split(String str)：根据str做拆分

题解思路：

这题输入数据比较小，可以直接用int型然后每一次取最后一位数即可

但是如果这题变成1<=n<=10^1e5的时候，那么就需要通过字符串进行判断

我们用字符串存储，每一次读取最后一个字符：charAt(i),然后判断它是否等于‘0’即可，等于就计数，不等于就输出结束

参考代码：

import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);String ss=scan.nextLine();int s=0;for(int i=ss.length()-1;i>=0;i--){//从最后一位往前判断if(ss.charAt(i)=='0') s++;//计数else{System.out.println(s);//输出return;//强制结束}}scan.close();}
}

B：超级质数

题目描述：

如果一个质数 P 的每位数字都是质数, 而且每两个相邻的数字组成的两位 数是质数, 而且每三位相邻的数字组成的三位数是质数, 依次类推, 如果每相 邻的 k 位数字组成的 k 位数都是质数, 则 P 称为超级质数。

如果把超级质数 P 看成一个字符串, 则这个超级质数的每个子串都是质 数。

例如, 53 是一个超级质数。

请问, 最大的超级质数是多少?

题解思路：

10以内的质数只有：2，3，5，7

因为每两位也是质数，所以2和5最多只能出现在第一位数

且 AA形式的数不为质数，也就是说从第二位开始为：373737...或者737373....
第一种方案中，将2   5   7带入得到最大为：73

第二种方案中，将2   3   7带入得到最大为：373

答案：

373

C：卡牌

题目描述：

这天, 小明在整理他的卡牌。

他一共有 n 种卡牌, 第 ii 种卡牌上印有正整数数 i(i∈[1,n]), 且第 i 种卡牌 现有 ai​ 张。

而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 n 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 i, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 ii 种牌最多手写 bi 张。

请问小明最多能凑出多少套牌?

输入格式

输入共 3 行, 第一行为两个正整数 n,m。

第二行为 nn 个正整数 a1,a2,…,an。

第三行为 nn 个正整数 b1,b2,…,bn。

输出格式

一行, 一个整数表示答案。

样例输入

4 5
1 2 3 4
5 5 5 5

样例输出

3

样例说明

这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,4 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。

评测用例规模与约定

对于 30%30% 的数据, 保证 n≤2000;

对于 100%100% 的数据, 保证 n≤2×10^5;ai,bi≤2n;m≤n^2。

题解思路：

这题用到一点贪心思维，简称：贪一下

我们在不考虑有多少张空白纸的情况下(即空白纸无限量),那么最多能凑出：Min(ai+bi)

ai+bi的值最小数量就是可以凑出来最多的数量

现在考虑怎么花费最少的空白纸得到某一个数量成套卡牌
假设我现在需要5套卡牌，是不是每种数量小于5的卡牌数都需要补充到5，而比5大的我们就不需要去浪费卡牌填充

假设当前卡牌位置 ax，需要凑齐ax套卡牌，那么总共会填补多少张？

x*ax-sum(a1+a2+...+ax)

其中 x*ax表示把a1，a2，a3....ax全部补到与ax相同数量时，总共会有x*ax张卡

sum(a1+a2+...+ax)表示在不补充时总共有sum张卡，两者相减表示需要补充的卡量

如果这个值小于给定的m值，则表示可以，继续往后判断，不然的话直接判断(sum+m)/x，表示平均下来每一种可以补充到的值，即为最终值

最后，与一开始不考虑空白纸的情况下的值比较，选取小的值输出即可

参考代码：

import java.util.*;
import java.io.*;
public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws Exception{int n=nextInt();long m=nextLong();long []arr=new long[n+1];long []brr=new long[n+1];long []crr=new long[n+1];for(int i=1;i<=n;i++) arr[i]=nextInt();for(int i=1;i<=n;i++) brr[i]=nextInt()+arr[i];Arrays.sort(arr);//按照已有值排序Arrays.sort(brr);//直接找到不考虑空白卡情况最多能凑齐几套long min=brr[1];long max=0;//最多能凑齐max套for(int i=1;i<=n;i++){crr[i]=crr[i-1]+arr[i];//前面数总和，前缀和一下if(arr[i]*i<=crr[i]+m) max=arr[i];//表示可行else {//不可行，求解maxmax=Math.max(max,(crr[i]+m)/i);break;}}pw.println(Math.min(min,max));//输出小的pw.flush();}public static int nextInt() throws Exception {//int型st.nextToken();return (int) st.nval;}public static long nextLong() throws Exception {//long型st.nextToken();return (long) st.nval;}
}

D：染色时间

题目描述：

小蓝有一个 nn 行 mm 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。

每个方格有一个染色时间 tijtij​, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 tijtij​ 秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。

给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。

输入格式

输入的第一行包含两个整数 n,mn,m, 分别表示棋盘的行数和列数。

接下来 n 行, 每行 mm 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 ii 行第 jj 个整数表示 tijtij​, 即第 ii 行第 jj 列的方 格的染色时间。

输出格式

输出一行包含一个整数, 表示整个棋盘完成染色的时间。

样例输入

2 31 2 34 5 6

样例输出

12

评测用例规模与约定

对于 30% 的评测用例, 1≤n,m≤10

对于 60% 的评测用例, 1≤n,m≤50

对于所有评测用例, 1≤n,m≤500,1≤tij≤1000

题解思路：

简单说明：我是用的bfs模板直接强行解，最终选择所有数中的最大值，在测试有50%几率通过（卡在1s上下，比赛的测试时间是3s）

通过bfs每一次增加对应时间，然后判断该位置当前的时间和之前的时间相比，是否有所减小，是的话就将该位置加入队列中，以确保当前位置的值为可以走到的最小值

参考代码：

import java.util.*；
import java.io.*;
public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static int n;static int m;static  int [][]arr;//记录每个格子需要的染色时间static int [][]brr;//记录染色到对应格子需要的时间static int [][]d={{-1,0},{1,0},{0,-1},{0,1}};public static void main(String[] args) throws Exception{n=nextInt();m=nextInt();arr=new int[n][m];brr=new int[n][m];for (int i=0;i<n;i++){//每一个位置需要的时间String[] mm = br.readLine().split(" ");for (int j=0;j<m;j++)arr[i][j]=Integer.parseInt(mm[j]);}brr[0][0]=arr[0][0];int max=0;bfs();for (int i=0;i<n;i++){//求得最大值Arrays.sort(brr[i]);max=Math.max(max,brr[i][m-1]);}System.out.println(max);//输出}static void bfs(){Queue<int []> q = new LinkedList<>();q.add(new int[] {0,0});//把起点加入队列int xa,ya,t;int []ss=new int[2];while (!q.isEmpty()){ss=q.poll();int x=ss[0],y=ss[1];//取出t=brr[x][y];//当前位置的花费时间for (int i=0;i<4;i++){//左右移动xa=x+d[i][0];ya=y+d[i][1];if (pd(xa,ya,t)){//判断q.add(new int[]{xa,ya});brr[xa][ya]=brr[x][y]+arr[xa][ya];//下一个位置的时间=上一个位置时间+该位置需要花费时间}}}}static boolean pd(int x,int y,int z){//判断if (x>=0&&x<n&&y>=0&&y<m){return z + arr[x][y] < brr[x][y]||brr[x][y]==0;}return false;}public static int nextInt() throws Exception {//int型st.nextToken();return (int) st.nval;}public static long nextLong() throws Exception {//long型st.nextToken();return (long) st.nval;}
}