当前位置：首页 > article >正文

蓝桥杯试题：特殊的三角形

article 2025/3/4 19:48:04

一、问题描述

假设一个三角形三条边为 a、b、c，定义该三角形的值 v=a×b×c。

现在有 tt个询问，每个询问给定一个区间 [l,r]，问有多少个三条边都不相等的三角形的值 v 在该区间范围内。

输入格式

第一行包含一个正整数 t，表示有 t 个询问。

接下来 tt 行，每行有两个空格隔开的正整数 l、r，表示询问区间 [l,r]。

输出格式

输出共 tt 行，第 ii 行对应第 ii 个查询的三角形个数。

样例输入

样例输出

二、代码展示

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[] sum = new long[(int)1e6+1];
        for (int a = 1; a < 100; a++) {
            for (int b = a+1; b < 1000; b++) {
                for (int c = b+1; c < a + b; c++) {
                    if(isTriangle(a,b,c) && a*b*c<sum.length){
                        sum[a*b*c]++;
                    }
                }
            }
        }
        for (int i = 1; i < sum.length; i++) {
            sum[i] += sum[i-1];
        }
        int t = sc.nextInt();
        while (t-->0){
            int l = sc.nextInt()-1;
            int r = sc.nextInt();
            System.out.println(sum[r]-sum[l]);
        }
    }
    public static boolean isTriangle(int a, int b, int c){
        if((a+b>c) && (a+c>b) && (b+c>a)){
            return true;
        }
        return false;
    }
}

代码解释

预处理阶段：

创建一个大小为1e6+1的数组sum，用于记录每个可能的三角形值v（即a×b×c）的出现次数。

使用三重循环遍历所有可能的边a、b、c，其中：

a的范围是1到99。

b的范围是a+1到999。

c的范围是b+1到a+b-1（确保c < a + b）。

检查这三个边是否能构成三角形，并确保a×b×c不超过1e6。若满足条件，则在sum数组中对应位置计数加1。

前缀和处理：

将sum数组转换为前缀和数组，使得sum[i]表示所有值小于等于i的三角形数目。

处理查询：

对于每个查询区间[l, r]，通过sum[r] - sum[l-1]快速得到区间内的三角形数目。

潜在问题

范围限制：

数组sum的大小为1e6+1，意味着代码只能正确处理v ≤ 1e6的情况。若输入的查询范围超过1e6（如r > 1e6），结果会错误地返回sum[1e6]的值，导致漏统计实际存在的更大的v值。

循环条件：

外层循环a的范围是1到99，这是基于当a ≥ 100时，即使最小的b和c也会使得a×b×c超过1e6。这一假设在大多数情况下成立，但若题目允许更大的v值，此限制会导致遗漏。

结论

代码在预处理阶段正确覆盖了所有可能的v ≤ 1e6的情况，并通过前缀和优化查询效率。然而，当查询的右边界r超过1e6时，结果将不准确。若题目保证所有查询的r ≤ 1e6，代码是正确的；否则需调整数组大小及循环范围以覆盖更大的值。