第98场周赛
1、大整数
题目
给定两个整数 n,k。
请你输出一个 n 位数，要求其各位数字均为 k。
输入格式
共一行，包含两个整数 n,k。
输出格式
一个整数，表示满足要求的 n位数。
数据范围
前三个测试点满足 1≤n≤3。
所有测试点满足 1≤n≤100，1≤k≤9。
输入样例：
3 2
输出样例：
222
简单题直接看代码吧！
代码
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int k=sc.nextInt(); for (int i=0;i<n;i++){ System.out.print(k); } } }
2、大乘积
题目
我们规定，如果一个非负整数 a 满足以下两个条件之一，则称 a为美丽数：
a=0
a=10ˣ，其中 x为任意非负整数。
给定 n 个非负整数 a1,a2,…,an这其中有至少 n−1 个数是美丽数。
请你计算并输出 a1×a2×…×an的结果。
输入格式
第一行包含整数 n。
第二行包含 a1,a2,…,an。
输出格式
共一行，输出一个不含前导 00 的整数，表示 a1×a2×…×an 的结果。
前 3 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤10⁵，a1∼an 均为不含前导 00 的非负整数，并且这 n个数的总长度不超过 10⁵。
输入样例1：
3 5 10 1
输出样例1：
50
输入样例2：
4 1 1 10 11
输出样例2：
110
输入样例3：
5 0 3 1 100 1
输出样例3：
0
解题思路
10⁵个数相乘，建议使用BigInteger，直接暴力就完事了，不熟悉BigInteger可以看看下面这篇文章
代码
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); BigInteger sum=new BigInteger("1"); BigInteger x=new BigInteger("1"); while (n-->0){ x=sc.nextBigInteger(); sum=sum.multiply(x); } System.out.println(sum); } }
3、末尾连续0
题目
给定一个正整数 m，请你统计一共有多少个正整数 n 满足，n 的阶乘的末尾连续 0 的数量恰好为 m。
输出满足条件的 n 的数量以及所有满足条件的 n。
例如，当 m=1时，满足条件的正整数 n共有 55 个，分别是 5,6,7,8,95,6,7,8,其中 5!=120,6!=720,7!=5040,8!=40320,9!=3628805!=120,6!=720,7!=5040,8!=40320,
9!=362880。
输入格式
共一行，一个正整数 m。
输出格式
如果存在满足条件的 n，则第一行输出满足条件的 n 的数量，第二行按从小到大的顺序输出所有满足条件的 n。如果不存在满足条件的 n，则输出一行 0 即可。
数据范围
前 55 个测试点满足 1≤m≤10。
所有测试点满足 1≤m≤10⁵。
输入样例1：
1
输出样例1：
5 5 6 7 8 9
输入样例2：
5
输出样例2：
0
解题思路
5！=120， 10！=3628800， 15！=1307674368000，20！=2432902008176640000
25！=15511210043330985984000000
阶乘后面有几个零就是看这个阶乘里面有多少个5，25！里有6个五5，2*5=10，3*5=15，4*5=20，5*5=25。
代码
import java.util.Scanner; public class Main { public static int calc(int x) { int res = 0; while (x!=0){ res += x / 5; x /= 5; } return res; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int m=sc.nextInt(); for (int i = 0; i <= 5e5; i += 5 ) if (calc(i) == m) { System.out.println(5); System.out.println(i+" "+(i+1)+" "+(i+2)+" "+(i+3)+" "+(i+4)); return; } else if (calc(i) > m) break; System.out.println(0); } }
第99场周赛
1、四则运算
题目
给定三个整数 a,b,c，请你计算并输出 （a×b）/（b+c） 的值。
输入格式
共一行，包含三个整数 a,b,c。
输出格式
一个实数，表示结果。
结果保留四位小数。
数据范围
所有测试点满足 1≤a,b,c≤1000。
输入样例1：
100 50 50
输出样例1：
50.0000
输入样例2：
199 60 40
输出样例2：
119.4000
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int a=sc.nextInt(); int b=sc.nextInt(); int c=sc.nextInt(); System.out.printf("%.4f",(double)(a*b)/(b+c)); } }
2、整理账本
题目
账本中记录了一种产品的 n条买卖记录。
记录分为两种，格式如下：
B p q，表示以 p 元/件的价格，买入 q 件该种商品。
S p q，表示以 p 元/件的价格，卖出 q 件该种商品。
任何卖出记录的交易价格都高于任何买入记录的交易价格。
也就是说，不会存在卖出记录和买入记录的交易价格相同的情况。
现在，请你对账本进行整理，对所有交易价格相同的记录进行合并，使得每个交易价格只存在一条记录，新记录的交易数量等于所有参与合并的旧记录的交易数量之和。
具体来说，如果账本中有 k 条记录的交易价格为 p，它们的交易数量分别为 q1,q2,…,qk，则将它们合并为一条新记录，新记录的交易价格仍为 p，交易数量为 q1+q2+…+qk。
注意：
合并为新记录后，参与合并的旧记录就从帐本中抹除了。
新纪录的交易类型（买入或卖出）保持不变，即与参与合并的旧记录保持一致。
不会存在卖出记录和买入记录的交易价格相同的情况。
整理完毕后，对于现有的所有记录，请你找到其中交易价格最低的 s 条卖出记录和交易价格最高的 s 条买入记录。
输入格式
第一行包含两个正整数 n,s。
接下来 n 行，每行包含一个记录，格式如题目描述。
输出格式
首先，按照交易价格从高到低的顺序，输出交易价格最低的 s 条卖出记录，每行一条，格式与输入相同。如果不足 s 条，则有多少输出多少。
然后，按照交易价格从高到低的顺序，输出交易价格最高的 s 条买入记录，每行一条，格式与输入相同。如果不足 s 条，则有多少输出多少。
数据范围
前 4 个测试点满足 1≤n≤6。
所有测试点满足 1≤n≤1000，1≤s≤50，0≤p≤10⁵，1≤q≤10⁴。
输入样例：
6 2 B 10 3 S 50 2 S 40 1 S 50 6 B 20 4 B 25 10
输出样例
S 50 8 S 40 1 B 25 10 B 20 4
解题思路
典型的HashMap题目，使用两个HashMap分别存储 买入和卖出记录，并都按照 交易价格从高到低进行排序。输出交易价格 最低的 s 条 卖出记录和交易价格 最高的 s 条 买入记录。
代码
import java.security.KeyStore; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String l=sc.nextLine(); int n= Integer.parseInt(l.split(" ")[0]); int s= Integer.parseInt(l.split(" ")[1]); LinkedHashMap<Integer,Integer> mapS=new LinkedHashMap<>(); LinkedHashMap<Integer,Integer> mapB=new LinkedHashMap<>(); //输入添加进对应的LinkedHashMap while (n-->0){ String S=sc.nextLine(); String[] ss=S.split(" "); if (ss[0].equals("B")){ mapB.put(Integer.valueOf(ss[1]),mapB.getOrDefault(Integer.parseInt(ss[1]),0)+Integer.parseInt(ss[2])); }else if (ss[0].equals("S")){ mapS.put(Integer.valueOf(ss[1]),mapS.getOrDefault(Integer.parseInt(ss[1]),0)+Integer.parseInt(ss[2])); } } //按要求进行排序 ArrayList<Map.Entry<Integer, Integer>> listS = new ArrayList<>(mapS.entrySet()); listS.sort((o1, o2) -> o2.getKey() - o1.getKey()); ArrayList<Map.Entry<Integer, Integer>> listB = new ArrayList<>(mapB.entrySet()); listB.sort((o1, o2) -> o2.getKey() - o1.getKey()); //按要求进行输出 Iterator<Map.Entry<Integer, Integer>> iter = listS.iterator(); int i=0; while(iter.hasNext()){ Map.Entry<Integer, Integer> item = iter.next(); if (i>=mapS.size()-s){ int key = item.getKey(); int value = item.getValue(); System.out.println("S "+key+" "+value); } i++; } Iterator<Map.Entry<Integer, Integer>> iter1 = listB.iterator(); i=s; while(iter1.hasNext()){ Map.Entry<Integer, Integer> item = iter1.next(); if (i==0) break; int key = item.getKey(); int value = item.getValue(); System.out.println("B "+key+" "+value); i--; } } }
3、扩展区间
题目
给定 n个区间，编号 1∼n。
其中，第 i 个区间为 [xi,xi]。
初始时，任意两个区间的交集为空。
对于每个区间，你都可以选择一个方向（向左或向右）对其进行扩展，当然也可以选择不对其进行扩展。每个区间最多只能扩展一次。
第 i 个区间的固定扩展长度为 lᵢ。
具体来说，对于第 i 个区间，你有三个选择：
具体来说，对于第 i 个区间，你有三个选择：
如果你选择使其向左扩展，那么它变为 [xᵢ−lᵢ,xᵢ]。
如果你选择使其向右扩展，那么它变为 [xᵢ,xᵢ+lᵢ]。
如果你选择不对其进行扩展，那么它仍保持 [xᵢ,xᵢ]不变。
我们希望尽可能多的区间能够得到扩展，但是必须保证所有扩展结束后，任意两个区间的交集为空仍然成立。请问，最多可以扩展多少个区间？
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 xᵢ,lᵢ。
所有区间按照 xᵢ 从小到大的顺序给出。
数据范围
前 66 个测试点满足 1≤n≤⁵。
所有测试点满足 1≤n≤10⁵，1≤x1<x2<…<xn≤10⁹，1≤lᵢ≤10⁹。
输出格式
一个整数，表示可以扩展的最大区间数量。
输入样例1：
5 1 2 2 1 5 10 10 9 19 1
输出样例1：
3
输入样例2：
5 1 2 2 1 5 10 10 9 20 1
输出样例3：
4
解题思路
贪心：尽量往左扩展，如果不行再尝试往右~尽可能多的扩展
第一个数和最后一个数肯定可以进行扩展，主要是考虑中间的数。
代码
import java.util.Scanner; public class Main { static int N = 100005; static int[][] dp = new int[N][2]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(), ans = 0; for (int i = 1; i <= t; i++) { dp[i][0] = sc.nextInt(); dp[i][1] = sc.nextInt(); } for (int i = 1; i <= t; i++) { if (i == 1 || i == t) ans++; else if (dp[i - 1][0] < dp[i][0] - dp[i][1]) ans++; else if (dp[i][0] + dp[i][1] < dp[i + 1][0]) { ans++; dp[i][0] += dp[i][1]; } } System.out.println(ans); } }
