题解：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++:

CPP

#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:

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

P12254美丽区间题解

文章操作

题解：P12254 美丽区间

思路

实现方法：

AC Code：

相关推荐

评论

P12254美丽区间题解