问题描述

Georgia 和 Bob 需要访问所有珠宝房间（树的叶子节点）并返回起点，求出他们必须旅行的最小距离以及达到该距离的有效访问顺序数目。所有内部节点至少有两个子节点。

方法思路

1. 最小距离计算：
   最小距离等于所有叶子节点对之间的距离总和的两倍除以（叶子节点数 - 1）。这是由于每对叶子节点之间的路径在树中会被两次遍历（进入和退出），因此总距离为所有路径总和的两倍。

2. 有效顺序数目计算：
   有效顺序数目由各内部节点的子节点数目的阶乘乘积决定。每个内部节点的子节点数目决定了该节点的排列方式，所有内部节点的排列方式相乘即为总的有效顺序数。

解决代码

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

vector<int> small_primes;

void sieve() {
    int max_p = sqrt(INT_MAX);
    vector<bool> is_prime(max_p + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_p; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_p; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= max_p; ++i) {
        if (is_prime[i]) {
            small_primes.push_back(i);
        }
    }
}

int main() {
    sieve();
    int L, U;
    while (cin >> L >> U) {
        vector<bool> is_prime(U - L + 1, true);
        for (int i = 0; i < is_prime.size(); ++i) {
            int num = L + i;
            if (num < 2) {
                is_prime[i] = false;
            }
        }
        for (int p : small_primes) {
            long long start = max((long long)p * p, (L + p - 1LL) / p * (long long)p);
            if (start > U) continue;
            for (long long j = start; j <= (long long)U; j += p) {
                int idx = j - L;
                if (idx >= 0 && idx < is_prime.size()) {
                    is_prime[idx] = false;
                }
            }
        }
        vector<int> primes;
        for (int i = 0; i < is_prime.size(); ++i) {
            if (is_prime[i]) {
                primes.push_back(L + i);
            }
        }
        if (primes.size() < 2) {
            cout << "There are no adjacent primes." << endl;
        } else {
            int min_diff = INT_MAX, max_diff = 0;
            pair<int, int> min_pair, max_pair;
            for (int i = 1; i < primes.size(); ++i) {
                int diff = primes[i] - primes[i-1];
                if (diff < min_diff) {
                    min_diff = diff;
                    min_pair = {primes[i-1], primes[i]};
                }
                if (diff > max_diff) {
                    max_diff = diff;
                    max_pair = {primes[i-1], primes[i]};
                }
            }
            printf("%d,%d are closest, %d,%d are most distant.\n",
                   min_pair.first, min_pair.second, max_pair.first, max_pair.second);
        }
    }
    return 0;
}

代码解释

1. 预处理质数：使用埃拉托斯特尼筛法生成所有小于等于√INT_MAX的质数，用于后续筛选区间内的质数。
2. 区间筛法：对于每个输入区间[L, U]，标记所有合数，剩下的即为质数。
3. 质数收集：收集区间内的所有质数，并计算相邻质数对的最小和最大间距。
4. 输出结果：根据质数对间距输出最近和最远的质数对，若无足够质数则提示无相邻质数。