P12254美丽区间题解

Algo_Kit · 2025-05-05 10:38:55 · 题解

题解：P12254 美丽区间

本蒟蒻第一次写题解，不喜勿喷。

思路

预处理每个数字所在的美丽区间。
输出答案。

实现方法：

1. 使用 while 循环计算每个美丽区间的左边界和右边界

我们可以定义一个 cnt 表示这是第几个美丽区间，每算完一个区间时，cnt 加上一个 1，计算下一个区间。
因为题目要求的是 L_i，R_i 之间的差尽可能的小，所以第 cnt 个美丽区间的左边界可以直接等于上一个美丽区间的右边界（条件 2：L_i \le R_i），第 cnt 个美丽区间的右边界可以等于上一个美丽区间的左边界 +k（条件 3：R_i − L_i \ge K）。
当 l_{cnt} 和 r_{cnt} 不满足条件 5（\gcd (L_i,R_i)=1）时，可以自增 r_{cnt}, 直到满足条件 5 为止。

2. 每次读入 n 时，循环遍历每个美丽区间，当 n 在此美丽区间中时，即可输出此美丽区间的编号。

但是这样会 TLE 的。

为什么会这样呢？\ 原来是在读入中，每读入一个 n 后都要一个 for 循环来查找，导致超时。\ 那该怎么办呢？\ 答：用一个 ans 数组存储第 i 个数字在哪个美丽区间中，每次找到美丽区间的左右边界（l 和 r 数组），就循环一次记录 ans。

AC Code：

C++:

#include <bits/stdc++.h>
using namespace std;

int l[5000010],r[5000010],ans[5000010];
int k,t,n,cnt = 0;

signed main(){
    scanf("%d%d",&k,&t);
    //初始化 
    l[0] = 0,r[0] = 0;
    while(r[cnt] < 1000000){
        cnt++;
        l[cnt] = r[cnt - 1] + 1;
        r[cnt] = k + l[cnt];
        while(__gcd(l[cnt],r[cnt]) > 1){   //这是个好东西 
            r[cnt]++;
        }
        for(int i = l[cnt];i <= r[cnt];i++){
            ans[i] = cnt;
        }
    }
    //直接输出 
    while(t--){
        scanf("%d",&n);
        printf("%d\n",ans[n]);
    } 
    return 0;
}

Java:

import java.util.Scanner;

public class Main {
    static int[] l = new int[5000010];
    static int[] r = new int[5000010];
    static int[] ans = new int[5000010];
    static int k, t, n, cnt = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        t = sc.nextInt();
        // 初始化
        l[0] = 0;
        r[0] = 0;
        while (r[cnt] < 1000000) {
            cnt++;
            l[cnt] = r[cnt - 1] + 1;
            r[cnt] = k + l[cnt];

            while (gcd(l[cnt], r[cnt]) > 1) {  // 这是个好东西
                r[cnt]++;
            }

            for (int i = l[cnt]; i <= r[cnt]; i++) {
                ans[i] = cnt;
            }
        }
        // 直接输出
        while (t-- > 0) {
            n = sc.nextInt();
            System.out.println(ans[n]);
        }
    }
    // 计算最大公约数
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}