杭电 OJ 1000-1009 Java解法-阿里云开发者社区

杭电 OJ 1000-1009 Java解法

2024-06-21 6

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 杭电 OJ 1000-1009 Java解法

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