杭电 OJ 1000-1009 Java解法

Problem Set

1000

高精度

java">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题的阴影

java">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

还是开大数

记得输出没有空格

java">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)

java">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)

java">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

java">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;//最大周期为49n %= 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

数学题恶心人

java">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

枚举吧

java">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

贪心

先解性价比最高的做法

java">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));}}
}