奶牛自行车

GitHub跳转原题关系图返回列表

枚举前、后齿轮组合：3 倍约束用整数乘法定向剪枝，把传动比按 lcm 标度改成整数后精确比方差，并列按字典序。

OJ: roj

题目 ID: 2068

难度:普及+/提高-

标签:搜索枚举剪枝数学

创建: 2026-10-01 06:12

更新: 2026-10-07 13:50

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定 FF（1⩽F⩽51 \leqslant F \leqslant 5）个前齿轮和 RR（1⩽R⩽101 \leqslant R \leqslant 10）个后齿轮的型号个数：前齿轮齿数从 [F1,F2][F_1, F_2] 中选 FF 个互不相同的整数，后齿轮从 [R1,R2][R_1, R_2] 中选 RR 个互不相同的整数（25⩽F1<F2⩽8025 \leqslant F_1 < F_2 \leqslant 80，5⩽R1<R2⩽405 \leqslant R_1 < R_2 \leqslant 40）。

每组方案产生 n=F×Rn = F \times R 个传动比 x=f/rx = f / r（前齿数除以后齿数），要求：

  1. 3 倍约束：最大传动比至少是最小传动比的 3 倍；
  2. 方差最小：把 nn 个传动比排序为 x1⩽x2⩽⋯⩽xnx_1 \leqslant x_2 \leqslant \cdots \leqslant x_n，记相邻差 di=xi+1−xid_i = x_{i+1} - x_i（共 m=n−1m = n-1 个），使
    dˉ=1m∑i=1mdi,方差=1m∑i=1m(di−dˉ)2\bar d = \frac{1}{m}\sum_{i=1}^{m} d_i,\qquad \text{方差}=\frac{1}{m}\sum_{i=1}^{m}(d_i-\bar d)^2
    最小。

并列规则：方差相同时，前齿轮组合字典序最小的优先；仍相同，后齿轮组合字典序最小。输出两行：前、后齿轮齿数各按升序。

样例：F=2,R=5F=2, R=5，前区间 [39,62][39,62]、后区间 [12,28][12,28]。最优解为前齿轮 39 53、后齿轮 12 13 15 23 27；它排序后的 10 个传动比见「正解 · 思路」，相邻差方差约 0.007850.00785。

正解

思路

这是一道"先读题、后编码"的题。 剥掉奶牛和别墅的故事，任务就是把两组数、F×RF\times R 个比值、排序、相邻差的方差按定义算清楚。没有隐藏的数学结构，正确做法就是枚举所有方案并精确比较——真正的挑战是让枚举在数据范围内跑完。

第一步：确定枚举框架与字典序。 前齿轮组合至多 (565)≈3.8×106\binom{56}{5}\approx 3.8\times10^6 种，后齿轮组合至多 (3610)≈2.5×108\binom{36}{10}\approx 2.5\times10^8 种，显然不能盲目做两层笛卡尔积。但注意：

  • 合法方案必须通过 3 倍约束，枚举后齿轮组合时可以先过这道闸再算方差；
  • itertools.combinations 按升序枚举，天然产生字典序。只要只在"分数严格更小"时更新答案，第一次拿到某个分数值的方案就是字典序最小的，自动满足并列规则。

流程如下：

flowchart LR
    A[按字典序枚举前齿轮组合] --> B[对每个前齿轮组合<br/>枚举后齿轮组合]
    B --> C{3 倍约束<br/>f_max*r_max >= 3*f_min*r_min}
    C -- "否: 剪枝" --> B
    C -- 是 --> D[排序 n 个传动比]
    D --> E[整数方差分数<br/>m*sum(d^2) - 首尾差^2]
    E --> F{分数严格小于<br/>当前最优?}
    F -- 否 --> B
    F -- 是 --> G[更新答案并回到 B]
    G --> B

图中只有两处分支：3 倍约束剪枝（O(1)O(1) 整数比较，砍掉不合法组合）和分数比较（决定是否更新答案）。

第二步：3 倍约束 = 一次整数乘法。 传动比的最大值是 fmax⁡rmin⁡\dfrac{f_{\max}}{r_{\min}}，最小值是 fmin⁡rmax⁡\dfrac{f_{\min}}{r_{\max}}，所以

fmax⁡rmin⁡⩾3⋅fmin⁡rmax⁡  ⟺  fmax⁡⋅rmax⁡⩾3 fmin⁡⋅rmin⁡.\frac{f_{\max}}{r_{\min}} \geqslant 3 \cdot \frac{f_{\min}}{r_{\max}} \iff f_{\max}\cdot r_{\max} \geqslant 3\,f_{\min}\cdot r_{\min}.

不等号两边交叉相乘，一次 O(1)O(1) 整数比较，完全避开浮点。对每个前齿轮组合，fmin⁡,fmax⁡f_{\min}, f_{\max} 已固定：

  • R⩾3R \geqslant 3 时枚举后齿轮组合，先查上式、不过再算方差；
  • R=2R = 2 时（真实数据最重的 cowcycle7 正是 F=3,R=2F=3, R=2），设两个后齿轮为 x<yx < y，合法条件即 y⩾⌈3fmin⁡x/fmax⁡⌉y \geqslant \lceil 3 f_{\min} x / f_{\max}\rceil。对每个 xx 直接从该下界开始枚举 yy，一个非法对都不会访问，把 (362)=630\binom{36}{2}=630 个齿对压到约 200–340 个。

第三步：方差比较变成纯整数运算。 方差是相邻差的方差。记 m=n−1m = n-1 个差为 did_i，展开：

方差=1m∑idi2−dˉ2,dˉ=1m∑idi.\text{方差}=\frac{1}{m}\sum_i d_i^2 - \bar d^2,\qquad \bar d=\frac{1}{m}\sum_i d_i.

两边乘 m2m^2（对每个方案都是同一个常数）：

m2⋅方差  =  m∑idi2−(∑idi)2.m^2 \cdot \text{方差} \;=\; m\sum_i d_i^2 - \left(\sum_i d_i\right)^2.

两个观察让这个表达式可以直接用整数算：

  1. 望远镜求和：∑idi=xn−x1\sum_i d_i = x_n - x_1，只需首尾两个传动比；
  2. 公共标度：令 L=lcm⁡(5,6,…,40)L=\operatorname{lcm}(5,6,\dots,40)，W[b]=L/bW[b]=L/b，则每个传动比 a/ba/b 等于整数 a⋅W[b]a\cdot W[b] 除以 LL。于是每个 di=Δi/Ld_i=\Delta_i/L，代入上式后 L2L^2 也是常数，最终只需比较整数
S=m∑iΔi2−Δspan2,Δspan=xn−x1 对应的整数跨度.S = m\sum_i \Delta_i^2 - \Delta_{\text{span}}^2,\qquad \Delta_{\text{span}} = x_n - x_1 \text{ 对应的整数跨度}.

排序传动比其实是在排序若干个整数 a⋅W[b]a\cdot W[b]：排序、求差、求和全是整数运算——比 fractions.Fraction 快一个数量级，同时绝对精确，不会因浮点噪声把"并列取字典序最小"的规则破坏。

第四步：看懂"方差最小"长什么样。 对样例答案前 39 53、后 12 13 15 23 27，把 10 个传动比排序并列出相邻差：

排序后的传动比 近似值 相邻差
39/27 1.4444 —
39/23 1.6957 0.2512
53/27 1.9630 0.2673
53/23 2.3043 0.3414
39/15 2.6000 0.2957
39/13 3.0000 0.4000
39/12 3.2500 0.2500
53/15 3.5333 0.2833
53/13 4.0769 0.5436
53/12 4.4167 0.3397

观察两点：最大/最小传动比为 4.4167/1.4444≈3.058⩾34.4167 / 1.4444 \approx 3.058 \geqslant 3，最优解贴着 3 倍约束线；9 个相邻差围绕均值 0.3300.330 上下波动，方差约 0.007850.00785——所谓"最佳齿轮组合"，就是让挡位差尽可能均匀的一组齿轮。

代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 06:19
# update_at: 2026-10-01 06:42

import sys
from itertools import combinations
from math import lcm

# 传动比 a/b 记为整数 a * W[b]（W[b] = L//b，L 是 5..40 的公倍数），
# 这样比值、相邻差、方差全在整数域精确计算，不存在浮点误差。
L = lcm(*range(5, 41))
W = [0] * 5 + [L // b for b in range(5, 41)]  # W[b] = L//b，下标 5..40 有效


def rank_score(nums: list[int], m: int) -> int:
    """由 m+1 个传动比整数（m 个相邻差）算“比较用方差分数”：m*Σ(相邻差)² - (首尾差)²。

    真实方差 = (m·Σd² - (Σd)²) / (L²·m²)，L、m 对每个方案相同，
    所以只需比较这个整数：越小方差越小。
    """
    nums.sort()
    first, last = nums[0], nums[-1]
    span = last - first            # Σd = 最大比 - 最小比（望远镜求和）
    sq = sum((b - a) ** 2 for a, b in zip(nums, nums[1:]))  # Σ d²
    return m * sq - span * span


def best_combo(f1: int, f2: int, r1: int, r2: int, F: int, R: int) -> tuple[tuple[int, ...], tuple[int, ...]]:
    """在所有合法方案里找方差分数最小的 (前齿轮, 后齿轮)；分数相同取字典序最小者在前。"""
    m = F * R - 1              # 相邻差的个数

    best_score: int | None = None  # 当前最小方差分数
    best: tuple[tuple[int, ...], tuple[int, ...]] | None = None

    for front in combinations(range(f1, f2 + 1), F):  # 字典序枚举前齿轮组合
        f_min, f_max = front[0], front[-1]
        # scaled[b] = 这个前齿轮组合配后齿轮 b 时的 F 个传动比整数（内部升序）
        scaled = [[a * W[b] for a in front] for b in range(r1, r2 + 1)]

        if R == 2:
            # 只需后齿轮较小者 x 与较大者 y：
            # 3 倍约束 f_max/y  >= 3*f_min/x  ⇔  y*f_max >= 3*x*f_min，
            # 直接算出每个 x 的合法 y 下界，跳过全部不合法对。
            for x in range(r1, r2):
                lo = (3 * f_min * x + f_max - 1) // f_max  # y 的最小合法值（向上取整）
                if lo < x + 1:
                    lo = x + 1
                for y in range(lo, r2 + 1):
                    score = rank_score(scaled[x - r1] + scaled[y - r1], m)
                    # 只替换严格更小者：枚举顺序即字典序，天然满足并列时取最小组合
                    if best_score is None or score < best_score:
                        best_score, best = score, (front, (x, y))
        else:
            for rear in combinations(range(r1, r2 + 1), R):
                if f_max * rear[-1] < 3 * f_min * rear[0]:  # 最大比不足最小比 3 倍
                    continue
                nums = [v for b in rear for v in scaled[b - r1]]
                score = rank_score(nums, m)
                if best_score is None or score < best_score:
                    best_score, best = score, (front, rear)

    return best  # 题面保证至少一组合法解


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    F, R = next(data), next(data)
    f1, f2, r1, r2 = next(data), next(data), next(data), next(data)

    best = best_combo(f1, f2, r1, r2, F, R)
    print(' '.join(map(str, best[0])))
    print(' '.join(map(str, best[1])))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:58
 * update_at: 2026-10-06 10:58
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 传动比 a/b 用整数 a * W[b] 表示（W[b] = L / b，L 是 5..40 的公倍数），
// 这样传动比、相邻差、方差分数全部是精确整数运算，没有浮点误差。
const ll L_LCM = 5342931457063200LL; // lcm(5,6,...,40)
ll W[45]; // W[b] = L_LCM / b，下标 5..40 有效

ll F, R;                 // 前、后齿轮个数
ll f1, f2, r1, r2;       // 前、后齿轮齿数的可选区间
ll front_g[10];          // 当前枚举的前齿轮组合（升序）
ll rear_g[11];           // 当前枚举的后齿轮组合（升序）
ll f_min, f_max;         // 当前前齿轮组合的最小 / 最大齿数
ll nums[55];             // 当前方案的 F*R 个传动比整数，排序后求相邻差

ll ans_front[10];        // 答案：前齿轮组合
ll ans_rear[11];         // 答案：后齿轮组合
bool has_ans = false;    // 是否已找到合法方案
__int128 best_score;     // 当前最优的方差分数（可能超过 ll，用 __int128 精确保存）

// 用当前 front_g / rear_g 组合计算“比较用方差分数”：
//   m*Σ(相邻差)^2 - (首尾差)^2，其中 m = F*R - 1 是相邻差的个数。
// 真实方差 = 分数 / (L^2 * m^2)，L、m 对每个方案相同，所以分数越小方差越小。
// 大小估计：span <= 80*W[5] 约 8.6e16，m <= 49，
//   m*Σd^2 <= 49*49*7.4e33 约 1.8e37，在 __int128 范围内。
__int128 calc_score() {
    ll n = F * R;
    ll idx = 0;
    for (ll j = 0; j < R; j++) {
        for (ll i = 0; i < F; i++) {
            nums[idx] = front_g[i] * W[rear_g[j]];
            idx++;
        }
    }
    sort(nums, nums + n);
    ll m = n - 1; // 相邻差个数
    __int128 sq = 0;              // Σ(相邻差)^2
    for (ll k = 0; k + 1 < n; k++) {
        ll d = nums[k + 1] - nums[k];
        sq += (__int128)d * d;
    }
    __int128 span = nums[n - 1] - nums[0]; // Σd = 最大比 - 最小比（望远镜求和）
    return (__int128)m * sq - span * span;
}

// 分数严格更小才更新：前后齿轮都是升序枚举，天然保证并列时取字典序最小的组合。
void try_update() {
    __int128 score = calc_score();
    if (has_ans && score >= best_score) return;
    has_ans = true;
    best_score = score;
    for (ll i = 0; i < F; i++) ans_front[i] = front_g[i];
    for (ll j = 0; j < R; j++) ans_rear[j] = rear_g[j];
}

// 枚举后齿轮组合：这一层在后齿轮区间里选第 dep 个齿数（保持升序）。
// 剪枝 1：第一个（最小）齿数 b 若连配上最大后齿 r2 都不满足 3 倍约束，更大的 b 只会更差，直接断开。
// 剪枝 2：选最后一个齿数时，必须 >= ceil(3*f_min*rear_g[0]/f_max) 才可能合法，从下界起选，
//         对 R=2 相当于一个非法齿对都不会被访问。
void dfs_rear(ll dep, ll start) {
    if (dep == R) {
        // 完整后齿轮组合已生成：3 倍约束 最大比 >= 3*最小比
        // 即 f_max/rear_min >= 3*f_min/rear_max，交叉相乘成整数比较
        if (f_max * rear_g[R - 1] >= 3 * f_min * rear_g[0]) {
            try_update();
        }
        return;
    }
    for (ll b = start; b <= r2; b++) {
        if (dep == 0 && f_max * r2 < 3 * f_min * b) break; // 最小齿数再增大只会更不合法
        rear_g[dep] = b;
        if (dep == R - 1) {
            ll lo = (3 * f_min * rear_g[0] + f_max - 1) / f_max; // 最后一个齿数的合法下界（向上取整）
            if (b < lo) continue;
        }
        dfs_rear(dep + 1, b + 1);
    }
}

// 枚举前齿轮组合：这一层在前齿轮区间里选第 dep 个齿数（保持升序）。
// 升序枚举即字典序，并列规则由“分数严格更小才更新”自动满足。
void dfs_front(ll dep, ll start) {
    if (dep == F) {
        f_min = front_g[0];
        f_max = front_g[F - 1];
        dfs_rear(0, r1);
        return;
    }
    for (ll a = start; a <= f2; a++) {
        front_g[dep] = a;
        dfs_front(dep + 1, a + 1);
    }
}

int main() {
    // 预处理 W[b] = L / b，把分数 a/b 变成整数 a * W[b]
    for (ll b = 5; b <= 40; b++) {
        W[b] = L_LCM / b;
    }

    cin >> F >> R;
    cin >> f1 >> f2 >> r1 >> r2;

    dfs_front(0, f1);

    // 输出前、后齿轮齿数（升序）
    for (ll i = 0; i < F; i++) {
        cout << ans_front[i] << " \n"[i == F - 1];
    }
    for (ll j = 0; j < R; j++) {
        cout << ans_rear[j] << " \n"[j == R - 1];
    }
    return 0;
}

复杂度

设 N=F2−F1+1⩽56N = F_2 - F_1 + 1 \leqslant 56，M=R2−R1+1⩽36M = R_2 - R_1 + 1 \leqslant 36。枚举框架为

O((NF)⋅(MR)⋅nlog⁡n),n=F×R⩽50,O\left(\binom{N}{F}\cdot \binom{M}{R}\cdot n\log n\right),\qquad n = F\times R \leqslant 50,

与标准 C++ 枚举解法同阶；nlog⁡nn\log n 来自每组合法方案的排序。真正的收益在剪枝与常数：3 倍约束把不合法后齿轮组合整体跳过，R=2R=2 时又从下界直接弹掉全部非法齿对（cowcycle7 的 8436×6308436\times630 组合对实际只访问约 210 万合法对）。空间 O(n)O(n)。

真实数据验证：8 组测例全部通过，最重的 cowcycle7（F=3,R=2,[43,80]×[5,40]F=3,R=2,[43,80]\times[5,40]）本地约 1.7s。理论极端组合（F=5,R=10F=5,R=10 且两个区间都拉满）对任何枚举类解法都不可行，不在本题数据中，Python 侧允许 TLE。

总结

  • 先翻译、再编码：把"传动比、3 倍约束、相邻差方差、字典序并列"逐条变成数学条件后，本题是一个干净的枚举 + 剪枝 + 精确比较问题。
  • 整数化三件套：约束用整数乘法判、传动比用 lcm 标度变整数、方差只用整数分数 m∑Δ2−Δspan2m\sum\Delta^2 - \Delta_{\text{span}}^2 比较，全程零浮点。
  • 并列规则白嫖枚举顺序：组合升序枚举 + 只在严格更小时更新，字典序要求自动满足。
  • 剪枝按最重数据特化：R=2R=2 时直接从 3 倍约束解出 yy 的下界，一个非法对都不访问。