P1080 [NOIP 2012 提高组] 国王游戏 · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1080，日期见页头。两边不一致时信原站。

题目描述

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是： 排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 n，表示大臣的人数。

第二行包含两个整数 a 和 b，分别表示国王左手和右手上的整数。

接下来 n 行，每行包含两个整数 a 和 b，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

数据规模与约定

对于 20% 的数据，有 1 ≤ n ≤ 10，0 < a, b < 8；
对于 40% 的数据，有 1 ≤ n ≤ 20，0 < a, b < 8；
对于 60% 的数据，有 1 ≤ n ≤ 100；
对于 60% 的数据，保证答案不超过 10⁹；
对于 100% 的数据，有 1 ≤ n ≤ 1000，0 < a, b < 10000。

NOIP 2012 提高组第一天第二题。

输入输出样例

输入

输出

三个大臣 (2,3)、(7,4)、(4,6)，国王是 (1,1)。样例说明里把 6 种排法全列了：最少的那种拿 2 个金币。 ⚠ 而这组样例放过了本页四个错法里的三个 —— 第 ⑥ 步会说这几乎是必然的。

★ 这一页的主线：数据范围那几行不是背景，是两件工具

这道题挂在第 20 章的题单里，练的是交换论证。那部分推导只有两行（第 ② 步）。

真正值得讲的是题面数据范围那一段 —— 它顺手给了你两样东西，而且互不覆盖：

题面写的	它其实是
「对于 20% 的数据，`n ≤ 10`，`0 < a, b < 8`」	★ 出题人给的对拍档（小到能 `n!` 全排列）
「对于 60% 的数据，保证答案不超过 `10⁹`」	★★★ 不写高精度的分数线 —— 而且这个界不是随口写的

⚠ 而第一样验不出第二样：在那个 20% 档上，「不写高精度」那一版 300 轮一次都没被抓（第 ⑤ 步）。⇒ 一半靠对拍，一半只能靠算。

1先把「谁在前面」这件事写清楚

排好队之后，第 k 位大臣拿到的金币是

    (国王的 a) × (排在他前面那些大臣的 a 的乘积)  ÷  他自己的 b       向下取整

⚠ 两个容易读漏的地方：

国王也算「前面的人」 —— 他的 a 要计进乘积（而他的 b 从头到尾用不上）；
要最小化的是最大值，不是总和。

2★ 关键一步：交换论证（只有两行）

盯住相邻的两个人

设某个排法里相邻两位是 i、j（i 在前），他们前面所有人的 a 之积是 P。交换这两个人，只有他们俩的金币会变，别人一分不差。

    i 在前：  max( P / b_i ,  P·a_i / b_j )
    j 在前：  max( P / b_j ,  P·a_j / b_i )

两个 max 里，P / b_i ≤ P·a_j / b_i 而且 P / b_j ≤ P·a_i / b_j（因为 a ≥ 1），所以两边各自的最大值分别是右边那一项：

    i 在前更优  ⟺  P·a_i / b_j  ≤  P·a_j / b_i
                ⟺  a_i · b_i    ≤  a_j · b_j

⇒ 按 a · b 从小到大排。 排序关键字最大 9999² ≈ 10⁸，int 装得下。

3★ 参照物是题面送的：那一档小到能全排列

交换论证只证明了「相邻交换不会更差」。要确认「按这个键排完就是最优」，最省事的办法是对拍 —— 而参照物题面已经给了：

对于 20% 的数据，有 1 ≤ n ≤ 10，0 < a, b < 8。

n ≤ 10 ⇒ n! 全排列跑得动；a, b < 8 ⇒ 前缀积最大 8¹⁰ ≈ 10⁹，long long 装得下，连高精度都不用写。

p1080Brute.cpp参照物：枚举所有排队顺序

// P1080 的参照物：**枚举所有排队顺序**（不排序、不用交换论证）
//
// ★ 这个参照物是**题面自己给的**：数据范围里写着
//   「对于 20% 的数据，有 `1 ≤ n ≤ 10`，`0 < a, b < 8`」——
//   那一档正好小到可以 `n!` 全排列枚举，而且前缀积最大 `8¹⁰ ≈ 10⁹`，`long long` 装得下。
//   ⇒ **「对于 X% 的数据」那几行，经常就是出题人顺手给你的对拍档位。**
//
// ⚠ 只能跑 `n ≤ 9` 左右（`9! = 362880`，每种还要扫一遍）。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    ll ka, kb;
    cin >> ka >> kb;
    (void)kb;
    vector<pair<ll, ll>> a(n);
    for (auto& p : a) cin >> p.first >> p.second;

    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end());

    ll best = LLONG_MAX;
    do {
        ll pre = ka, worst = 0;
        for (int i : idx) {
            worst = max(worst, pre / a[i].second);
            pre *= a[i].first;
        }
        best = min(best, worst);
    } while (next_permutation(idx.begin(), idx.end()));

    cout << best << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果


那一档 300 组：贪心 vs 全排列暴力	不一致 0 组

★ 「对于 X% 的数据」那几行，经常就是出题人顺手给你的对拍档位

这不是巧合：部分分档位存在的意义就是「让暴力也能拿分」，而能让暴力拿分的规模，正好也是能让暴力当参照物的规模。

⇒ 读题读到数据范围时，顺手问一句：最小的那一档，我的暴力跑得动吗？

4★★★ 「要不要写高精度」是一道算术题

题面顶格是 n = 1000、a < 10000。前缀积最坏是

    9999 ^ 1000

位数 = 1000 × log₁₀(9999) ≈ 3999.96 ⇒ 约 4000 位十进制。


算出来的位数	约 4000
实测顶格一组的答案位数	3 996
`unsigned long long` 能表示的位数	20

差了两百倍。 ⇒ 必须写高精度，而且只需要三件事： 乘一个小整数（a < 10⁴）、除以一个小整数（b < 10⁴）、比大小。不需要高精度乘高精度，也不需要高精度除高精度 —— 这一点让代码短了很多。

p1080.cpp★ 这一版就能 AC

// P1080 [NOIP 2012 提高组] 国王游戏 —— ★ 这一版就能 AC
//
// 题意：国王站最前，后面排 n 个大臣，每人左右手各一个数 (a, b)。
//       第 i 个大臣拿到的金币 = （排在他前面所有人的 a 的乘积）÷ 他自己的 b，向下取整。
//       重排队伍（国王不动），让**拿得最多的那个人**尽量少。
//
// ★ 关键一步：交换论证。只盯相邻两位 i、j，设他们前面所有人的 a 之积是 P：
//
//       i 在前：  max( P / b_i ,  P·a_i / b_j )
//       j 在前：  max( P / b_j ,  P·a_j / b_i )
//
//   两边同乘 b_i·b_j / P（都是正数，不影响大小关系）：
//
//       i 在前：  max( a_j·b_j , a_i·... )  ⇒ 化简后就是比 a_i·b_i 和 a_j·b_j
//
//   ⇒ **按 a·b 从小到大排**。（页面第 ② 步把这个推导写全了。）
//   ⚠ 排序关键字 a·b 最大 9999² ≈ 10⁸，int 装得下 —— 但写 `long long` 不吃亏。
//
// ★★★ 而这道题真正的工作量在**高精度**上，页面第 ④ 步算了这笔账：
//   前缀积最大是 9999¹⁰⁰⁰，也就是大约 **4000 位十进制** —— 任何内置类型都装不下。
//   ⇒ 需要三件事：高精度**乘一个 int**、高精度**除以一个 int**、高精度**比大小**。
//   ★ 题面已经把分数线写出来了：「对于 60% 的数据，保证答案不超过 10⁹」——
//     **这句话等于在说另外 40% 会超**，不写高精度精确地拿 60 分（页面第 ⑤ 步实测）。

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

/** 高精度非负整数：低位在前，每节 8 位十进制 */
struct Big {
    static const ll BASE = 100000000LL;
    vector<ll> d;                                  // d[0] 是最低的 8 位

    Big(ll x = 0) { while (x) { d.push_back(x % BASE); x /= BASE; } }

    void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }

    /** 乘一个小整数（题面里是 a < 10000，乘完不会溢出 long long） */
    Big& mulSmall(ll m) {
        ll carry = 0;
        for (size_t i = 0; i < d.size(); i++) {
            ll cur = d[i] * m + carry;             // 最大 1e8 × 1e4 = 1e12，long long 够
            d[i] = cur % BASE;
            carry = cur / BASE;
        }
        while (carry) { d.push_back(carry % BASE); carry /= BASE; }
        trim();
        return *this;
    }

    /** 除以一个小整数，向下取整 */
    Big divSmall(ll m) const {
        Big r;
        r.d.assign(d.size(), 0);
        ll rem = 0;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            ll cur = rem * BASE + d[i];
            r.d[i] = cur / m;
            rem = cur % m;
        }
        r.trim();
        return r;
    }

    bool operator<(const Big& o) const {
        if (d.size() != o.d.size()) return d.size() < o.d.size();
        for (int i = (int)d.size() - 1; i >= 0; i--)
            if (d[i] != o.d[i]) return d[i] < o.d[i];
        return false;
    }

    string str() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());
        char buf[16];
        for (int i = (int)d.size() - 2; i >= 0; i--) {
            snprintf(buf, sizeof(buf), "%08lld", d[i]);
            s += buf;
        }
        return s;
    }
};

int main() {
    int n;
    if (!(cin >> n)) return 0;
    ll ka, kb;
    cin >> ka >> kb;                               // 国王的两个数（kb 用不上：国王不领赏）
    (void)kb;

    vector<pair<ll, ll>> a(n);                     // (左手, 右手)
    for (auto& p : a) cin >> p.first >> p.second;

    sort(a.begin(), a.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) {
        return x.first * x.second < y.first * y.second;      // ★ 按 a·b 升序
    });

    Big pre(ka);                                   // ★ 国王也在队伍里，他的 a 要算进前缀积
    Big best(0);
    for (auto& [x, y] : a) {
        Big cur = pre.divSmall(y);                 // 这位大臣拿到的金币
        if (best < cur) best = cur;
        pre.mulSmall(x);
    }
    cout << best.str() << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★ 顶格一组（n = 1000，全是 9999）算一遍本机 1 毫秒 —— 高精度在这题上完全不是瓶颈。

5★★★ 而题面那句「答案不超过 10⁹」，正好是「不写高精度」的分数线

p1080Ull.cpp错法一：不写高精度（能拿 60 分）

// P1080 错法一：不写高精度，用 `unsigned long long` 存前缀积
//
// ★★★ 这一版**不是瞎写的，它是一个能拿 60 分的策略** —— 而且分数线是题面自己给的：
//   题面数据范围里写着「对于 **60%** 的数据，保证答案不超过 `10⁹`」。
//   ⇒ 这句话反过来读就是：**另外 40% 的数据答案会超过 10⁹**。
//   页面第 ⑤ 步把两档分别造出来量了一遍。
//
// ⚠ 而它错的方式很难看：前缀积 9999¹⁰⁰⁰ 有约 4000 位，`unsigned long long` 只有 20 位 ——
//   溢出之后是**回绕**，算出来的数看着完全正常，只是和答案毫无关系。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    ull ka, kb;
    cin >> ka >> kb;
    (void)kb;
    vector<pair<ull, ull>> a(n);
    for (auto& p : a) cin >> p.first >> p.second;
    sort(a.begin(), a.end(), [](const pair<ull, ull>& x, const pair<ull, ull>& y) {
        return x.first * x.second < y.first * y.second;
    });
    ull pre = ka, best = 0;
    for (auto& [x, y] : a) {
        best = max(best, pre / y);
        pre *= x;                                  // ← 这里会悄悄回绕
    }
    cout << best << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

题面数据范围里那一行很容易被当成背景：

对于 60% 的数据，保证答案不超过 10⁹。

★★★ 这个界不是随口写的 —— 它正好是 unsigned long long 够用的条件

答案 = max(pre_i / b_i)。如果答案 ≤ 10⁹，那么对每一个用得上的 pre_i：

    pre_i / b_i ≤ 10⁹        而 b_i < 10⁴
    ⇒  pre_i < 10⁹ × 10⁴ = 10¹³          而 2⁶⁴ ≈ 1.8 × 10¹⁹

⇒ 只要答案 ≤ 10⁹，前缀积就一定塞得进 unsigned long long，那一版就是对的。

实测（随机 400 组，n ≤ 40、a, b < 10000）：

	组数	其中 `ull` 版算错的
答案 ≤ 10⁹	32	★ 0
答案 > 10⁹	368	350

推导和实测对上了。⇒ 那句话的意思是：不写高精度，精确地拿 60 分。 （⚠ 另一侧的 368 组里有 18 组它也蒙对了 —— 溢出回绕之后碰巧没影响到最大值，所以那一侧是「几乎全错」，不是「必错」。）

⚠ 而这件事，题面给的那个对拍档一次都抓不到

第 ③ 步那个 20% 档（n ≤ 8、a, b ≤ 7）上，答案顶多几百 —— 按上面的推导，ull 在那一档必然是对的。实测确认：

在 20% 那一档上跑 300 轮，各被抓几次
按 `a` 排序	125
按 `a·b` 降序	259
丢掉国王的 `a`	253
不写高精度	★ 0

⇒ 对拍档和高精度这件事是错开的：那一档验的是「排序键对不对」，而「类型够不够」它结构上看不见（第 18 章 P1516 那种两难的又一个形态）。 ★ 好在这一次不需要两难 —— 这一半本来就该算，不该测。

6另外两个错法，以及样例又一次的表现

p1080Desc.cpp错法二：交换论证方向推反

p1080ByA.cpp错法三：只按左手的数 a 排

p1080NoKing.cpp错法四：忘了国王也在队伍里

错法	官方样例	挡住了吗	在 20% 档 300 轮里被抓
按 `a·b` 降序	9（答案 2）	★ 挡住	259
按 `a` 排序	2	放过	125
丢掉国王的 `a`	2	放过	253
不写高精度	2	放过	0

★ 样例这次挡住的仍然是「最显眼」的那个

方向推反 ⇒ 几乎每组都错 ⇒ 样例挡住；
按 a 排序 ⇒ 这组样例上它排出来的顺序和正解恰好一样（2 → 4 → 7）⇒ 放过；
丢掉国王 ⇒ 样例里国王的 a 正好是 1，乘不乘一个样 ⇒ 放过；
不写高精度 ⇒ 样例答案是 2，离 2⁶⁴ 差着十九个数量级 ⇒ 放过。

⇒ 这是本书连着第五道题撞上同一条规律（P1223 / P2240 / P1094 / P1090）： 官方样例只有一组，它天生是一个「一测就死」的过滤器，挡得住的都是「每一组都错」的，放过的都是「偶尔才错」的。

7度量程序和生成器

p1080Count.cpp度量程序

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

// P1080 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1080Count`      人看的版本
// `./p1080Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ 贪心 ≡ 全排列暴力（用**题面自己给的**那一档：n ≤ 8、a,b ≤ 7）；
//   ② ★ 四个错法在那一档上各被抓多少；
//   ③ ★★★ **「要不要写高精度」是一道算术题**：答案顶格有多少位；
//   ④ ★★★ 题面那句「对于 60% 的数据，保证答案不超过 10⁹」**不是随口写的** ——
//      它正好是 `unsigned long long` 够用的条件（推导 + 实测）；
//   ⑤ ★ 顺带量一量高精度那份自己的规模（顶格要乘多少次、最长多少位）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

/** 高精度非负整数：低位在前，每节 8 位十进制 */
struct Big {
    static const ll BASE = 100000000LL;
    vector<ll> d;                                  // d[0] 是最低的 8 位

    Big(ll x = 0) { while (x) { d.push_back(x % BASE); x /= BASE; } }

    void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }

    /** 乘一个小整数（题面里是 a < 10000，乘完不会溢出 long long） */
    Big& mulSmall(ll m) {
        ll carry = 0;
        for (size_t i = 0; i < d.size(); i++) {
            ll cur = d[i] * m + carry;             // 最大 1e8 × 1e4 = 1e12，long long 够
            d[i] = cur % BASE;
            carry = cur / BASE;
        }
        while (carry) { d.push_back(carry % BASE); carry /= BASE; }
        trim();
        return *this;
    }

    /** 除以一个小整数，向下取整 */
    Big divSmall(ll m) const {
        Big r;
        r.d.assign(d.size(), 0);
        ll rem = 0;
        for (int i = (int)d.size() - 1; i >= 0; i--) {
            ll cur = rem * BASE + d[i];
            r.d[i] = cur / m;
            rem = cur % m;
        }
        r.trim();
        return r;
    }

    bool operator<(const Big& o) const {
        if (d.size() != o.d.size()) return d.size() < o.d.size();
        for (int i = (int)d.size() - 1; i >= 0; i--)
            if (d[i] != o.d[i]) return d[i] < o.d[i];
        return false;
    }

    string str() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());
        char buf[16];
        for (int i = (int)d.size() - 2; i >= 0; i--) {
            snprintf(buf, sizeof(buf), "%08lld", d[i]);
            s += buf;
        }
        return s;
    }
};


struct In { ll ka, kb; vector<pair<ll, ll>> a; };

/** 正解：按 a·b 升序 + 高精度 */
static Big solve(In in) {
    sort(in.a.begin(), in.a.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) {
        return x.first * x.second < y.first * y.second;
    });
    Big pre(in.ka), best(0);
    for (auto& [x, y] : in.a) {
        Big cur = pre.divSmall(y);
        if (best < cur) best = cur;
        pre.mulSmall(x);
    }
    return best;
}
/** 错法一：unsigned long long */
static ull solveUll(In in) {
    sort(in.a.begin(), in.a.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) {
        return x.first * x.second < y.first * y.second;
    });
    ull pre = (ull)in.ka, best = 0;
    for (auto& [x, y] : in.a) { best = max(best, pre / (ull)y); pre *= (ull)x; }
    return best;
}
/** 错法二 / 三 / 四：换排序键 或 丢掉国王 */
static Big solveVar(In in, int kind) {
    if (kind == 0) sort(in.a.begin(), in.a.end(),
        [](const pair<ll, ll>& x, const pair<ll, ll>& y) { return x.first < y.first; });
    else sort(in.a.begin(), in.a.end(), [kind](const pair<ll, ll>& x, const pair<ll, ll>& y) {
        return kind == 1 ? x.first * x.second > y.first * y.second
                         : x.first * x.second < y.first * y.second;
    });
    Big pre(kind == 2 ? 1 : in.ka), best(0);
    for (auto& [x, y] : in.a) {
        Big cur = pre.divSmall(y);
        if (best < cur) best = cur;
        pre.mulSmall(x);
    }
    return best;
}
/** 参照物：枚举所有排队顺序（只在题面那一档用） */
static ll brute(const In& in) {
    int n = in.a.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    ll best = LLONG_MAX;
    do {
        ll pre = in.ka, worst = 0;
        for (int i : idx) { worst = max(worst, pre / in.a[i].second); pre *= in.a[i].first; }
        best = min(best, worst);
    } while (next_permutation(idx.begin(), idx.end()));
    return best;
}

static In gen(mt19937& rng, int nHi, int vHi) {
    In in;
    int n = (int)(rng() % (unsigned)nHi) + 1;
    in.ka = (ll)(rng() % (unsigned)vHi) + 1;
    in.kb = (ll)(rng() % (unsigned)vHi) + 1;
    in.a.resize(n);
    for (auto& p : in.a) { p.first = (ll)(rng() % (unsigned)vHi) + 1; p.second = (ll)(rng() % (unsigned)vHi) + 1; }
    return in;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① 贪心 ≡ 全排列暴力（题面「20% 的数据」那一档） */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            In in = gen(rng, 8, 7);
            if (solve(in).str() != to_string(brute(in))) bad++;
        }
        if (!CSV) printf("① 题面那一档（n ≤ 8、a,b ≤ 7）：贪心 vs 全排列暴力 %d 组，不一致 %d 组\n", groups, bad);
        row("ref", {groups, bad});
    }

    /* ② 四个错法在那一档的抓获率 */
    {
        mt19937 rng(777u);
        int byA = 0, desc = 0, noKing = 0, uLL = 0;
        for (int r = 0; r < 300; r++) {
            In in = gen(rng, 8, 7);
            string ok = solve(in).str();
            if (solveVar(in, 0).str() != ok) byA++;
            if (solveVar(in, 1).str() != ok) desc++;
            if (solveVar(in, 2).str() != ok) noKing++;
            if (to_string(solveUll(in)) != ok) uLL++;
        }
        if (!CSV) printf("② 同一档 300 轮：按 a 排错 %d 次、按 a·b 降序错 %d 次、丢掉国王错 %d 次、"
                         "unsigned long long 错 %d 次\n", byA, desc, noKing, uLL);
        row("catch", {byA, desc, noKing, uLL});
    }

    /* ③ ★★★ 答案顶格有多少位 —— 先算，再量 */
    {
        // 算：前缀积最大 9999^1000，位数 = 1000 × log10(9999) 向上取整
        double lg = 1000.0 * log10(9999.0);
        ll calcDigits = (ll)floor(lg) + 1;
        // 量：造一组顶格（国王 1 1，1000 个大臣全是 (9999, 1)）
        In in;
        in.ka = 1; in.kb = 1;
        in.a.assign(1000, {9999, 1});
        string s = solve(in).str();
        if (!CSV) printf("③ 顶格：算出来前缀积约 %lld 位；实测答案 %zu 位"
                         "（unsigned long long 只能表示 20 位）\n", calcDigits, s.size());
        row("digits", {calcDigits, (ll)s.size(), 20});
    }

    /* ④ ★★★ 题面那句「60% 的数据答案不超过 10⁹」正好是 ull 够用的条件 */
    {
        // 推导：答案 = max(pre_i / b_i) ≤ 10⁹ 且 b_i < 10⁴  ⇒  每个用到的 pre_i < 10¹³ < 2⁶⁴
        mt19937 rng(31415u);
        int small = 0, smallBad = 0, big = 0, bigBad = 0;
        Big limit(1000000000LL);
        for (int r = 0; r < 400; r++) {
            In in = gen(rng, 40, 9999);
            Big ans = solve(in);
            bool le = !(limit < ans);                       // 答案 ≤ 10^9 ?
            bool same = to_string(solveUll(in)) == ans.str();
            if (le) { small++; if (!same) smallBad++; }
            else { big++; if (!same) bigBad++; }
        }
        if (!CSV) printf("④ 随机 400 组：答案 ≤ 10⁹ 的有 %d 组，其中 ull 版错 %d 组；"
                         "答案 > 10⁹ 的有 %d 组，其中 ull 版错 %d 组\n", small, smallBad, big, bigBad);
        row("guard", {small, smallBad, big, bigBad});
    }

    /* ⑤ 高精度那份自己的规模 */
    {
        In in;
        in.ka = 9999; in.kb = 1;
        in.a.assign(1000, {9999, 9999});
        auto t0 = chrono::steady_clock::now();
        Big ans = solve(in);
        ll ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
        if (!CSV) printf("⑤ 顶格一组（n = 1000，全是 9999）：答案 %zu 位，算一遍 %lld 毫秒\n", ans.str().size(), ms);
        row("scale", {(ll)ans.str().size(), ms});
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1080Gen.cpp数据生成器

// P1080 对拍生成器：`./p1080Gen <seed> [n 上限] [a、b 的上限]`
//   默认 `n ≤ 8`、`a, b ≤ 7` —— ★ **就是题面里「对于 20% 的数据」那一档**。
//
// ★ 为什么默认档抄题面：那一档小到可以用 `n!` 全排列当参照物，
//   而且前缀积不会溢出 `long long` —— **出题人顺手给了你一个能对拍的档位**。
// ⚠ 而这一档**量不出高精度那件事**（答案顶多几百）：
//   要看「不写高精度会怎样」，得把上限拧到题面顶格（`n = 1000`、`a, b < 10000`），
//   那时候参照物就没了 —— 页面第 ⑤ 步是靠**算**而不是靠对拍解决的。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int nHi = argc > 2 ? atoi(argv[2]) : 8;
    int vHi = argc > 3 ? atoi(argv[3]) : 7;
    nHi = max(1, min(1000, nHi));
    vHi = max(1, min(9999, vHi));

    mt19937 rng(seed * 2654435761u + 108u);
    int n = (int)(rng() % (unsigned)nHi) + 1;
    printf("%d\n", n);
    printf("%u %u\n", (unsigned)(rng() % (unsigned)vHi) + 1, (unsigned)(rng() % (unsigned)vHi) + 1);
    for (int i = 0; i < n; i++)
        printf("%u %u\n", (unsigned)(rng() % (unsigned)vHi) + 1, (unsigned)(rng() % (unsigned)vHi) + 1);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

8一页纸


关键的一步	交换论证 ⇒ 按 `a · b` 从小到大排（推导只有两行）
哪一版能 AC	`p1080.cpp`（排序＋高精度乘小数 / 除小数 / 比大小，顶格 1 毫秒）
这一页的主线	★★★ 数据范围那几行是两件工具：20% 档是对拍档，「答案 ≤ 10⁹」是不写高精度的分数线 —— 而且两者互不覆盖
要不要写高精度	一道算术题：`9999¹⁰⁰⁰` 约 4000 位（实测答案 3996 位），`ull` 只有 20 位
那个 60% 是怎么来的	`pre_i ≤ 答案 × b_i < 10⁹ × 10⁴ = 10¹³ < 2⁶⁴` ⇒ 答案 ≤ 10⁹ 时 `ull` 必然够（实测：答案 ≤ 10⁹ 的 32 组里错 0 组；> 10⁹ 的 368 组里错 350 组）
⚠ 对拍的盲区	那个 20% 档结构上抓不到「类型够不够」（300 轮 0 次）—— 这一半只能算
参照物	`n!` 全排列（题面自己给的那一档，`long long` 就够）—— 300 组不一致 0 组
样例的表现	四个错法只挡住最显眼的那一个（方向推反）—— 连着第五道题同一条规律

洛谷 P1080 [NOIP 2012 提高组] 国王游戏

0题目原文（本地存了一份）

输入

输出

1先把「谁在前面」这件事写清楚

2★ 关键一步：交换论证（只有两行）

3★ 参照物是题面送的：那一档小到能全排列

4★★★ 「要不要写高精度」是一道算术题

5★★★ 而题面那句「答案不超过 10⁹」，正好是「不写高精度」的分数线

6另外两个错法，以及样例又一次的表现

7度量程序和生成器

8一页纸