洛谷试炼场 DAY 02

2023-10-06 16:23:34

洛谷试炼场 DAY 02

前言

上一篇的评论说想知道具体刷题的操作过程，在这里简单的提一嘴吧。其实大致的刷题提交过程都和力扣大同小异，主要不同的地方集中在在线IDE上。具体如下：

  • 洛谷提交的代码中，主类名必须为Main，否则无法成功编译。另外，代码中不能包含有package语句，否则一样会编译错误。

  • 洛谷题目最后的代码需要打印出来，而不是像力扣那样是一个返回值

    System.out.print("your answer");

  • 洛谷提交的代码中如果有使用到一些方法，则需要import相应的包，保证编译成功。

    //这里用Scanner为例演示
import java.util.*;
.......
  Scanner in = new Scanner(System.in);

  • 洛谷中使用的是Java 8，这里有时候需要注意一下子（虽然但是，洛谷社区中的主流语言是C++和python，有时候找题解会找不到就很难受）

上面就是我主要总结的洛谷和力扣的一些不同的地方，当然还有其它一些不一样的板块，比如力扣中更多的是就业相关内容，而洛谷则更像是一个竞赛内容社区，所以题目也会更多的有数学相关性（有些题是真的看不懂）。这里就贴一下洛谷官方发的新手必看贴，可以在里面了解更多内容。 洛谷官方新手必读贴

另外，发现上次的题目其实贴的有点多，所以之后的题目会筛选一下，主要集中在我没办法AC的题目上（感觉这样还是会有很多题hhhh）

洛谷试炼场 DAY 02 开始

01.三角形面积

题目描述

一个三角形的三边长分别是a,b,c，那么它的面积为\(\sqrt{p(p-a)(p-b)(p-c)}\)，其中\(p=1/2(a+b+c)\)。输入这三个数字，计算三角形的面积，四舍五入精确到一位小数。输入数字保证能构成三角形，\(0\leq a,b,c \leq 1000\)，每个边长输入时不超过2位小数。

原题目链接：洛谷P5708 三角形面积

思路

从题目本身来看，这道题的本身的难度并不难，对于根号的代码实现可以借助Math类里面的sqrt方法，剩下的也就是输出答案了。

但是，对于我一开始没有AC的原因，在于没有注意到最后的题目条件：==每边长不超过2位小数==，也就是说，在开始选择数据类型的时候应该选择double类型，这是我没有意识到的，我尝试了int和long两种类型，一直无法AC通过，甚至开始怀疑后面代码的正确性。anyway，最后修改正确之后，AC成功。

代码

注意这里的输出有要求是四舍五入精确到一位小数，没有小数位的需要补0，所以这里使用了DecimalFormat方法实现。

import java.text.DecimalFormat;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double a = in.nextDouble();
        double b = in.nextDouble();
        double c = in.nextDouble();
        
        double p = (a+b+c)/2.0;
        DecimalFormat df = new DecimalFormat("0.0");
        double size = Math.sqrt(p*(p-a)*(p-b)*(p-c));
        System.out.println(df.format(size));
        in.close();
    }
}

02.对角线

题目描述

对于一个n个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。输入一个整数表示边数，输出一个整数代表答案。

原题目链接：洛谷P2181 对角线

思路

这道题是一道黄题（洛谷中的一种难度）。一开始看到时有点懵懵的，找不到解题的思路。看完题解之后发现思路了。

从题目可知，凸多边形中的任何三条对角线都不会交于一点。换句话说，两条对角线可以确定一个交点。两天对角线又可以确定四个多边形顶点（是顶点！！！）。所以我们只需要确定4个顶点就可以得到一个唯一确定的交点。进而我们只需要求这样的4个顶点的搭配有多少个就可以了（到这里就可以发现有点排列组合的感觉）所以呢，我们根据排列组合的知识就可以得到这样一条公式\(n*(n-1)*(n-2)*(n-3)/24\)。(因为改变四个点的顺序不会改变对角线，也就是说我们求的是组合而不是排列，所以最后需要除以24。比如公式化简前是这样的：\(n*(n-1)/2*(n-2)/3*(n-3)/4\))

思路一旦确定之后，剩下的代码就可以非常简单的实现了，当然还需要注意内存溢出的问题。

代码


import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger num = sc.nextBigInteger();
        BigInteger ans = num.multiply(num.subtract(BigInteger.valueOf(1))).multiply(num.subtract(BigInteger.valueOf(2)))            .multiply(num.subtract(BigInteger.valueOf(3))).divide(BigInteger.valueOf(24));
        System.out.println(ans);
        sc.close();
    }
}

03.买铅笔

题目描述

P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有 33种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过nn支铅笔才够给小朋 友们发礼物。

现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少nn支铅笔最少需要花费多少钱

原题目链接：洛谷P1909 买铅笔

思路

对于这道题，本身的计算部分并不太难，通过两个循环嵌套即可求解，问题是对于有些测试用例（是真的非人用例，一支笔9999，一共有9999个学生），在计算过程中会可能会出现内存溢出的问题。这也是我打完代码没办法AC的问题。理想状态下应该只用修改一下数据类型和代码细节就可以解决了。

在这里使用了三个数组来存放每包铅笔的数量，价格和需要买的包数。最后使用函数进行求最小值，应该是没什么问题的。20个测试用例AC了14个，最后得分70分。（不想改了，用例真的非人）

代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] num = new int[3];
        int[] price = new int[3];
        int[] count = {1,1,1};
        int student = sc.nextInt();
        for(int i = 0 ; i < 3 ; i++) {
            num[i] = sc.nextInt();
            price[i] = sc.nextInt();
        }
        for(int j = 0 ; j < 3 ; j++) {
            while(num[j] < student) {
                num[j] += num[j];
                count[j] += count[j];
            }
        }
        int money = Math.min(price[0] * count[0], price[1]*count[1]);
        money = Math.min(money, price[2] * count[2]);
        System.out.print(money);
        sc.close();
    }
}

后言

这段时间刚好春节期间，懒得雅痞很少做题。然后做的题里面没办法AC的也比较少，导致这次的题目较少质量也不高。Anyway，never mind。

==祝各位新年快乐！！！==

上一篇：2022/02/04


下一篇：02-Nacos集群搭建