Problem Set
1000
高精度
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ System.out.println(sc.nextBigInteger().add(sc.nextBigInteger())); } } }
1001
位运算防爆 1000题的阴影
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ long num= sc.nextLong(); System.out.println((1+num)*num>>>1); } } }
1002
还是开大数
记得输出没有空格
import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); long cnt=1; long n= sc.nextLong(); for (long i = 0; i < n; i++) { BigInteger b1=sc.nextBigInteger(); BigInteger b2=sc.nextBigInteger(); System.out.println("Case"+cnt+":"); System.out.println(b1+"+"+b2+"="+b1.add(b2)); cnt++; } } }
1003
将双层for循环替换成剪枝 还是没过
线性遍历过了 时间复杂度为O(2n)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int cnt = 1; long t = sc.nextLong(); for (long i = 0; i < t; i++) { int n = sc.nextInt(); long arr[] = new long[n + 1]; long ans[] = new long[n + 1]; for (int i1 = 1; i1 <= n; i1++) { arr[i1] = sc.nextLong(); ans[i1] = arr[i1] + ans[i1 - 1]; } long max = Integer.MIN_VALUE; int left = -1; int right = -1; long min = 0; for (int i1 = 1; i1 <= n; i1++) { if (ans[i1] - min > max) { max = ans[i1] - min; right = i1; left = findLeftIndex(ans, min, i1); } min = Math.min(min, ans[i1]); } System.out.println("Case " + cnt + ":"); System.out.println(max + " " + left + " " + right); cnt++; } } private static int findLeftIndex(long[] ans, long min, int endIndex) { for (int i = 0; i < endIndex; i++) { if (ans[i] == min) { return i + 1; } } return -1; } }
1004
用java特有双列集合
默认开哈希 速度快
最后再遍历一次即可 时间复杂度O(n)
import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while (sc.hasNext()){ long n= sc.nextLong(); if(n==0)return; //双列集合存储 Map<String,Long>map=new HashMap<>(); for (long i = 0; i < n; i++) { //输入键 String str= sc.next(); //如果集合有键 把键对应的数值拿出来 加1 再放回去 if(map.containsKey(str)){ long num=map.get(str); num++; map.put(str,num); } //如果集合里没有键 把（键，1）放到集合里面去 else map.put(str,1L); } //把键放到一个单列集合里 Set<String> set=map.keySet(); String s=""; long ans=0; //遍历单列集合 找到值最大的键 记录 for (String str : set) { if(map.get(str)>ans){ s=str; ans=map.get(str); } } System.out.println(s); } } }
1005
有取余必出现周期
对7取余就只能出现0到7
第三个数由第一个和第二个决定
两两组合 7*7 周期为49
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()) { long a = sc.nextLong(); long b = sc.nextLong(); long n = sc.nextLong(); if (a == 0 && b == 0 && n == 0) return; //最大周期为49 n %= 49; long ans1=1; long ans2=1; long ans3=1; if(n==1) System.out.println(1); else if(n==2) System.out.println(1); else { for (long i = 0; i < n - 2; i++) { ans3=(a*ans2+b*ans1)%7; ans1=ans2; ans2=ans3; } System.out.println(ans3); } } } }
1006
数学题 恶心人
import java.util.Scanner; public class Main { // 定义常量 static final int maxn = 12 * 60 * 60; static double hm, hs, ms; static double T_hm, T_hs, T_ms; // 初始化函数 static void init() { double h = 1.0 / 120; double m = 1.0 / 10; double s = 6; hm = m - h; hs = s - h; ms = s - m; T_hm = 360 / hm; T_hs = 360 / hs; T_ms = 360 / ms; } // 最大值函数 static double max(double a, double b, double c) { return Math.max(Math.max(a, b), c); } // 最小值函数 static double min(double a, double b, double c) { return Math.min(Math.min(a, b), c); } // 主函数 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); init(); while (scanner.hasNext()) { double n = scanner.nextDouble(); if (n == -1) break; double[] a = new double[6]; a[0] = n / hm; a[1] = n / hs; a[2] = n / ms; a[3] = (360 - n) / hm; a[4] = (360 - n) / hs; a[5] = (360 - n) / ms; double ans = 0; for (double i = 0; i <= maxn; i += T_hm) { for (double j = 0; j <= maxn; j += T_hs) { if (j + a[1] > i + a[3]) break; if (i + a[0] > j + a[4]) continue; for (double k = 0; k <= maxn; k += T_ms) { if (k + a[2] > i + a[3] || k + a[2] > j + a[4]) break; if (i + a[0] > k + a[5] || j + a[1] > k + a[5]) continue; double p = max(i + a[0], j + a[1], k + a[2]); double q = min(i + a[3], j + a[4], k + a[5]); if (q > p) { ans += q - p; } } } } double percentage = 100.0 * ans / maxn; System.out.printf("%.3f\n", percentage); } scanner.close(); } }
1007
不会
而且没看懂题解
分治算法是什么玩意
1008
枚举吧
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n= sc.nextInt(); if(n==0)return; int ans=0; int sum=0; for (int i = 0; i < n; i++) { int temp= sc.nextInt(); if(temp>ans){ sum+=(temp-ans)*6; } else if(temp<ans){ sum+=(ans-temp)*4; } ans=temp; sum+=5; } System.out.println(sum); } } }
1009
贪心
先解性价比最高的做法
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while (sc.hasNext()){ int n= sc.nextInt(); int m= sc.nextInt(); if(n==-1&&m==-1)return; int arr1[]=new int[m]; int arr2[]=new int[m]; double arr3[]=new double[m]; for (int i = 0; i < m; i++) { arr1[i]= sc.nextInt(); arr2[i]= sc.nextInt(); arr3[i]=arr1[i]*1.0/arr2[i]; } double max=0;//性价比 int ans=0;//记录最大值 double sum=0; while (n>0){ for (int i = 0; i < m; i++) { if(arr3[i]>max){ max=arr3[i]; ans=i; } } if(max==0)break; if(n>arr2[ans]){ sum+=arr1[ans]; arr3[ans]=0; n-=arr2[ans]; } else { sum+=arr3[ans]*n*1.0; n=0; } max=0; } System.out.println(String.format("%.3f",sum)); } } }
