没有一个冬天不可逾越
也没有一个春天不会来临
所有美好的食物,都会有一个等待的过程
低谷时蛰伏,静默时沉淀
做三四月的事,在八九月自有答案
目录
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 {//不可行,求解max
max=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 3 1 2 3 4 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;
}
}