P1010 [NOIP 1998 普及组] 幂次方 · 习题解析

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

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

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

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

题目描述

任何一个正整数都可以用 2 的幂次方表示。例如 137 = 2⁷ + 2³ + 2⁰。

同时约定次方用括号来表示，即 a^b 可表示为 a(b)。

由此可知，137 可表示为 2(7)+2(3)+2(0)。

进一步：

7 = 2² + 2 + 2⁰（2¹ 用 2 表示），并且 3 = 2 + 2⁰。

所以最后 137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)。

又如 1315 = 2¹⁰ + 2⁸ + 2⁵ + 2 + 1。

所以 1315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。

输入格式

一行一个正整数 n。

输出格式

符合约定的 n 的 0, 2 表示（在表示中不能有空格）。

说明 / 提示

对于 100% 的数据，1 ≤ n ≤ 2 × 10⁴。

NOIP1998 普及组第三题

输入输出样例

输入

输出

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

1算法只有五行，一半的分在格式上

p1010.cpp★ 这一版就能 AC

// P1010 [NOIP 1998 普及组] 幂次方 —— 能 AC 的那一版
//
// 递归一句话：**把 n 拆成 2 的幂之和，每个指数再拿同样的办法拆下去。**
//
//   rep(n) = 各个 1 位的 "2(rep(e))"，从**高位到低位**用 '+' 连起来
//
// 三条**格式**规则，全部写在题面里，一条都不能漏：
//   ① `2¹` 写成 `2`，**不是** `2(1)`；
//   ② `2⁰` 写成 `2(0)`，里面那个 0 是**字面的 0**；
//   ③ 从**高位到低位**输出。
//
// ⚠ 这道题的算法只有五行，一半的分在上面这三条上 ——
//   而「把输出解析回去求值」这种最强的自动验证手段，对它们**一无所知**（见 p1010Eval.cpp）。

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

static string rep(int n) {
    if (n == 0) return "0";
    string s;
    bool first = true;
    for (int e = 14; e >= 0; e--) {              // ★ 高位在前；n <= 2×10⁴ < 2¹⁵
        if (!((n >> e) & 1)) continue;
        if (!first) s += '+';
        first = false;
        if (e == 1) s += "2";                    // ★ 规则 ①
        else { s += "2("; s += rep(e); s += ")"; }
    }
    return s;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    printf("%s\n", rep(n).c_str());
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

递归一句话：把 n 拆成 2 的幂之和，每个指数再拿同样的办法拆下去。 n ≤ 2 × 10⁴ < 2¹⁵，递归最深 4 层，跑起来是瞬间的事。

★ 真正难的是三条格式规则，而它们全都写在题面里

规则	题面原话	漏了会怎样
① `2¹` 写成 `2`，不是 `2(1)`	「（`2¹` 用 `2` 表示）」—— 写在括号里	第 ③ 步
② `2⁰` 写成 `2(0)`	「`137` 可表示为 `2(7)+2(3)+2(0)`」	第 ③ 步
③ 从高位到低位	题面给的两串答案都是这个顺序	第 ③ 步

⇒ 这一页要回答的问题只有一个： 这三条，你能用什么办法自动验？

2★★★ 这道题没有第二个算法 —— 于是「对拍」验不了正确性

★★★ 对拍的参照物只能是你自己 ⇒ 它退化成了「回归测试」

前面十一章的解析页，对拍都长这样：一个慢而显然正确的暴力，对一个快的。

这道题没有那个「慢而显然正确的暴力」—— 拆法只有一种，你能写出来的第二份代码，和第一份是同一个算法。

⇒ 拿正解当参照物跑 300 轮，能证明的只有一件事： 「我刚才那次改动没有引入差异」。它证明不了正解本身是对的。

⇒ 真正能验正确性的只有三样，而且缺一不可：

手段	验的是	覆盖面
① 题面给的两串答案，逐字节	语义＋格式	★ 只有 2 个 `n`
② 反着验：把输出解析回去求值	★ 只有语义	★★ 全部 20000 个 `n`
③ 把格式规则抄成断言	★ 只有格式	★★ 全部 20000 个 `n`

★ 顺带一件小事：题面白送了第二组答案

「输入输出样例」那一栏只给了 1315。但题目描述里还完整推导了 137 —— 2(2(2)+2+2(0))+2(2+2(0))+2(0)。

⇒ 题面正文里的例子就是额外的测试用例，抄下来当第二组样例，白给的。（本页的 p1010Eval.cpp 把这两串都钉成了断言。）

3三个格式错法 —— 每一个都「算得完全正确」

p1010One.cpp⚠ 2¹ 也写成 2(…)

// P1010 ⚠ 错法一：`2¹` 也老老实实写成 `2(1)`
//
// 这是最自然的写法 —— 递归写下去，谁会记得给指数 1 开个特例？
// 而题面把这一条**单独用括号标了出来**：「( 2¹ 用 2 表示 )」。
//
// ★ 关键在于：**它算出来的值完全正确**。`2(1)` 和 `2` 代表的都是 2。
//   ⇒ 把输出解析回去求值的那种验证（p1010Eval.cpp），对它**一个字都说不出来**。

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

static string rep(int n) {
    if (n == 0) return "0";
    string s;
    bool first = true;
    for (int e = 14; e >= 0; e--) {
        if (!((n >> e) & 1)) continue;
        if (!first) s += '+';
        first = false;
        s += "2("; s += rep(e); s += ")";        // ⚠ 就是这里：e == 1 没开特例
    }
    return s;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    printf("%s\n", rep(n).c_str());
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1010Order.cpp⚠ 从低位到高位

// P1010 ⚠ 错法二：从**低位到高位**输出
//
// `while (n) { if (n & 1) …; n >>= 1; e++; }` 是最顺手的位循环写法，
// 而它天然是**从低位往高位**走的。题面给的答案是**从高位到低位**。
//
// ★ 同样地：**它的值也完全正确** —— 加法可以交换。
//   ⇒ 求值器对它也一个字都说不出来。

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

static string rep(int n) {
    if (n == 0) return "0";
    string s;
    bool first = true;
    for (int e = 0; e <= 14; e++) {              // ⚠ 就是这里：低位在前
        if (!((n >> e) & 1)) continue;
        if (!first) s += '+';
        first = false;
        if (e == 1) s += "2";
        else { s += "2("; s += rep(e); s += ")"; }
    }
    return s;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    printf("%s\n", rep(n).c_str());
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1010Zero.cpp⚠ rep(0) 返回空串 ⇒ 印出 2()

// P1010 ⚠ 错法三：递归到 0 的时候返回**空串**
//
// `rep(0)` 该返回什么？「0 没有任何 1 位」⇒ 循环一次都不进 ⇒ 返回空串，
// 于是 `2⁰` 印出来是 `2()`。而题面要的是 `2(0)`。
//
// ★ 它的值**还是对的**：`2()` 里面是空的，按「空 = 0」读，2⁰ = 1，一点没错。
//   ⇒ 求值器对它同样一个字都说不出来（除非你把求值器写严 ——
//     而「写严」的意思就是：你又在验格式了）。

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

static string rep(int n) {
    if (n == 0) return "";                       // ⚠ 就是这里，正解返回 "0"
    string s;
    bool first = true;
    for (int e = 14; e >= 0; e--) {
        if (!((n >> e) & 1)) continue;
        if (!first) s += '+';
        first = false;
        if (e == 1) s += "2";
        else { s += "2("; s += rep(e); s += ")"; }
    }
    return s;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    printf("%s\n", rep(n).c_str());
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

n = 1315 时它们各自印出：

版本	输出
★ 正解	`2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)`
⚠ `One`	`2(2(2(2(0))+2(0))+2(2(0)))+…`
⚠ `Order`	`2(0)+2+2(2(0)+2(2))+…`
⚠ `Zero`	`2(2(2+2())+2)+2(2(2+2()))+2(2(2)+2())+2+2()`

★★★ 三个都错得很显眼 —— 而它们代表的「数」全都等于 1315

2(1) 和 2 都是 2；
换个顺序，加法不变；
2() 按「空 = 0」读，2⁰ = 1，也没错。

⇒ 值全对，只有写法不对。 记住这一点，下一步那张表才有意思。

4★★★ 反着验：把 20000 个 n 一个不落地跑完

p1010Eval.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

// ★★★ 一道**没有第二个算法**的题，怎么验？—— 反着验，而且把整个数据范围跑完
//
// 用法：./p1010Eval          人话版
//       ./p1010Eval csv      给 check:viz 用
//
// 这道题的数据范围是 `1 <= n <= 2×10⁴` —— **两万个输入，一个不落地全跑得完。**
// ⇒ 别说「对拍 300 轮」了，直接**穷举**。
//
// 可是穷举也要有参照物，而这道题**没有第二个算法**（就这一种拆法）。
// ⇒ 唯一的路是**反着验**：把输出那一串 `2(2(2)+2+2(0))+…` 解析回去求值，看等不等于 n。
//
// ★★★ 而这一页真正的结论是下面这句：
//   **求值器在两万个 n 上 100% 通过，而三个格式错法它一个都抓不到** ——
//   因为 `2(1)`、`2()`、以及把顺序颠倒过来，**值全都是对的**。
//   ⇒ 这道题一半的分在格式上，而最强的自动验证手段对格式一无所知。
//
// ⇒ 出路不是「格式验不了」，是**把题面里的格式规则一条条抄成断言**：
//   R1 任何 `2(E)` 里的 E 都不许等于 1（题面：2¹ 写成 2）
//   R2 不许出现空括号 `2()`（题面：2⁰ 写成 2(0)）
//   R3 每一层的项必须**严格递减**（题面：从高位到低位）
//   下面那张表就是「哪条规则抓到哪个错法」。

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

/* ---------- 四个版本的生成函数（和四份 .cpp 一字不差） ---------- */
static string rep0(int n) {                       // 正解
    if (n == 0) return "0";
    string s; bool first = true;
    for (int e = 14; e >= 0; e--) { if (!((n >> e) & 1)) continue;
        if (!first) { s += '+'; }
        first = false;
        if (e == 1) s += "2"; else { s += "2("; s += rep0(e); s += ")"; } }
    return s;
}
static string rep1(int n) {                       // ⚠ 2¹ 也写成 2(…)
    if (n == 0) return "0";
    string s; bool first = true;
    for (int e = 14; e >= 0; e--) { if (!((n >> e) & 1)) continue;
        if (!first) { s += '+'; }
        first = false;
        s += "2("; s += rep1(e); s += ")"; }
    return s;
}
static string rep2(int n) {                       // ⚠ 低位在前
    if (n == 0) return "0";
    string s; bool first = true;
    for (int e = 0; e <= 14; e++) { if (!((n >> e) & 1)) continue;
        if (!first) { s += '+'; }
        first = false;
        if (e == 1) s += "2"; else { s += "2("; s += rep2(e); s += ")"; } }
    return s;
}
static string rep3(int n) {                       // ⚠ rep(0) 返回空串
    if (n == 0) return "";
    string s; bool first = true;
    for (int e = 14; e >= 0; e--) { if (!((n >> e) & 1)) continue;
        if (!first) { s += '+'; }
        first = false;
        if (e == 1) s += "2"; else { s += "2("; s += rep3(e); s += ")"; } }
    return s;
}

/* ---------- 求值器 ＋ 三条格式规则（一趟递归下降同时干完） ---------- */
struct Flags { bool r1 = false, r2 = false, r3 = false; bool bad = false; };

static long long parseE(const string& s, size_t& i, Flags& f);

static long long parseT(const string& s, size_t& i, Flags& f) {
    if (i >= s.size()) { f.bad = true; return 0; }
    if (s[i] == '0') { i++; return 0; }
    if (s[i] != '2') { f.bad = true; i++; return 0; }
    i++;                                          // 吃掉 '2'
    if (i < s.size() && s[i] == '(') {
        i++;
        if (i < s.size() && s[i] == ')') {        // ★ 空括号：R2
            i++; f.r2 = true; return 1;           // 按「空 = 0」读，2⁰ = 1 —— 值是对的
        }
        long long e = parseE(s, i, f);
        if (i < s.size() && s[i] == ')') i++; else f.bad = true;
        if (e == 1) f.r1 = true;                  // ★ 2(E) 而 E = 1：R1
        long long v = 1; for (long long t = 0; t < e && t < 62; t++) v *= 2;
        return v;
    }
    return 2;                                     // 裸的 2
}
static long long parseE(const string& s, size_t& i, Flags& f) {
    vector<long long> terms;
    while (true) {
        terms.push_back(parseT(s, i, f));
        if (i < s.size() && s[i] == '+') { i++; continue; }
        break;
    }
    for (size_t k = 1; k < terms.size(); k++)
        if (!(terms[k] < terms[k - 1])) f.r3 = true;   // ★ 项必须严格递减：R3
    long long sum = 0; for (long long t : terms) sum += t;
    return sum;
}
static long long evalOf(const string& s, Flags& f) {
    size_t i = 0; long long v = parseE(s, i, f);
    if (i != s.size()) f.bad = true;
    return v;
}

typedef string (*Rep)(int);
static Rep REPS[4] = { rep0, rep1, rep2, rep3 };
static const char* NAMES[4] = { "p1010（正解）", "p1010One", "p1010Order", "p1010Zero" };

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

    int evalBad[4] = {0}, r1Bad[4] = {0}, r2Bad[4] = {0}, r3Bad[4] = {0}, byteBad[4] = {0};
    for (int v = 0; v < 4; v++) {
        for (int n = 1; n <= NMAX; n++) {
            string out = REPS[v](n);
            Flags f;
            long long got = evalOf(out, f);
            if (got != n || f.bad) evalBad[v]++;
            if (f.r1) r1Bad[v]++;
            if (f.r2) r2Bad[v]++;
            if (f.r3) r3Bad[v]++;
            if (out != rep0(n)) byteBad[v]++;
        }
    }

    /* 题面自己给了两串答案：样例的 1315，以及题目描述里推导的 137 */
    const string WANT1315 = "2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)";
    const string WANT137  = "2(2(2)+2+2(0))+2(2+2(0))+2(0)";
    int okSample[4], ok137[4];
    for (int v = 0; v < 4; v++) {
        okSample[v] = (REPS[v](1315) == WANT1315) ? 1 : 0;
        ok137[v]    = (REPS[v](137)  == WANT137)  ? 1 : 0;
    }

    if (csv) {
        printf("nmax,%d\n", NMAX);
        for (int v = 0; v < 4; v++)
            printf("v%d,%d,%d,%d,%d,%d,%d,%d\n", v, evalBad[v], r1Bad[v], r2Bad[v], r3Bad[v],
                   byteBad[v], okSample[v], ok137[v]);
        return 0;
    }

    printf("n 从 1 到 %d，**一个不落**地全跑一遍（不是抽样 300 轮）：\n\n", NMAX);
    printf("  %-14s %10s %8s %8s %8s %10s %8s %8s\n",
           "版本", "求值≠n", "R1", "R2", "R3", "逐字节≠正解", "样例1315", "题面137");
    printf("  %-14s %10s %8s %8s %8s %10s %8s %8s\n",
           "--------------", "----------", "--------", "--------", "--------", "----------", "--------", "--------");
    for (int v = 0; v < 4; v++)
        printf("  %-14s %10d %8d %8d %8d %10d %8s %8s\n", NAMES[v],
               evalBad[v], r1Bad[v], r2Bad[v], r3Bad[v], byteBad[v],
               okSample[v] ? "✓" : "✗", ok137[v] ? "✓" : "✗");

    printf("\n  ★★★ 看「求值≠n」那一列：**四行全是 0**。\n");
    printf("     三个格式错法的**值全都是对的** —— 反着验对它们一个字都说不出来。\n");
    printf("  ★ 而 R1 / R2 / R3 各抓一个，一个不多一个不少：\n");
    printf("     R1「2(E) 里 E 不许等于 1」→ One；R2「不许空括号」→ Zero；R3「每层严格递减」→ Order。\n");
    printf("\n  ⇒ 格式不是「验不了」，是**规则要自己从题面里抄成断言**。\n");
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

数据范围只有 1 ≤ n ≤ 2 × 10⁴ —— 两万个输入，全跑完只要 0.12 秒。

版本	求值 ≠ n	R1	R2	R3	逐字节 ≠ 正解	样例 1315	题面 137
★ `p1010`	0	0	0	0	0	✓	✓
⚠ `One`	★ 0	19999	0	0	19999	✗	✗
⚠ `Order`	★ 0	0	0	19996	19996	✗	✗
⚠ `Zero`	★ 0	0	19985	0	19985	✗	✗

★★★ 看第一列：四行全是 0

求值器在两万个 n 上 100% 通过，而三个格式错法它一个都抓不到。

这不是求值器写得不好 —— 是它按定义就只能看见语义。把它写严（比如「不许出现空括号」），那就等于你又在验格式了，只是换了个地方写。

⇒ ★★★ 这道题一半的分在格式上，而你能造的最强的自动验证手段，对格式一无所知。

★★★ 出路不是「格式验不了」，是「规则要自己从题面抄成断言」

把题面那三句话，一句一句翻译成一个能跑的判据：

规则	题面原话	判据	抓到谁
R1	「`2¹` 用 `2` 表示」	任何 `2(E)` 里，`E` 的值不许等于 `1`	★ `One` 19999
R2	「`2⁰` 写成 `2(0)`」	不许出现空括号 `2()`	★ `Zero` 19985
R3	高位在前	每一层的项必须严格递减	★ `Order` 19996

★ 三条各抓一个，一个不多一个不少（正解那一行三个 0）。

⚠ 三个数都不是 20000，差的那几个也讲得通： One 漏掉 n = 1（rep(1) 本来就是 2(0)，没有 2(E) 且 E=1）； Order 漏掉 n = 1, 2, 4, 16（每一层都只有一个项，顺序无从颠倒）； Zero 漏掉那些表示里根本没有 2⁰ 的 n。 ⇒ 连「漏了几个」都能一条条对上，那才叫验过了。

5★ 顺带：数据范围小到能穷举的时候，别再对拍了

p1010Gen.cpp生成器：四档

// 数据生成器（P1010 对拍用）：`./p1010Gen <seed> [level]`
//
//   level 0（默认）n ∈ [1, 2×10⁴] 随机
//   level 1        n 是 **2 的幂**（1, 2, 4, …, 16384）—— 每一层只有一个项
//   level 2        n = 2ᵏ - 1（**全 1 位**）—— 每一层的项最多
//   level 3        n ≤ 8 —— 最小的那几个，`2`、`2(0)` 这些特例都在里面
//
// ⚠ 这道题的数据范围只有两万个，**根本不需要随机**：
//   `p1010Eval.cpp` 直接把 1..20000 一个不落地跑完了。
//   这个生成器留着只是为了页面上那个 StressTest 按钮能动 ——
//   ★ **范围小到能穷举的时候，「对拍 300 轮」是退步，不是进步。**

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;

    int n;
    if (level == 1)      n = 1 << ri(0, 14);
    else if (level == 2) n = (1 << ri(1, 14)) - 1;
    else if (level == 3) n = ri(1, 8);
    else                 n = ri(1, 20000);
    printf("%d\n", n);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

四档 × 300 轮，逐字节对拍（参照物是正解自己）：

生成器	⚠ `One`	⚠ `Order`	⚠ `Zero`
level 0 随机 `n ≤ 2×10⁴`	300 / 300	300 / 300	300 / 300
level 1 `n` 是 2 的幂	279	211	209
level 2 `n = 2ᵏ - 1`（全 1 位）	281	281	300
level 3 `n ≤ 8`	263	190	187

★ 这张表其实是多余的 —— 而「多余」正是它的用处

1200 轮抽样，抓到的东西比不上上一步那张全范围的表：上一步是 20000 个 n，一个不落，而且说得出漏掉的是哪几个。

⇒ ★ 范围小到能穷举时，「对拍 300 轮」是退步，不是进步。 先看一眼 n 的上限：2 × 10⁴ 个输入，全跑完 0.12 秒。

（顺带：level 1「n 是 2 的幂」那一档抓获率反而最低 —— 每一层只有一个项，Order 无从颠倒、Zero 也常常碰不到 2⁰。又一次第 7 章 P1638那条：为一个 bug 精心造的档位，正是另一个 bug 的盲区。）

6一张总表

版本	错在哪	值对吗	求值器抓到吗	哪条规则抓到	结果
⚠ `p1010One`	`2¹` 写成 `2(…)`	★ 对	✗ 0 / 20000	R1（19999）	✗ WA
⚠ `p1010Order`	低位在前	★ 对	✗ 0 / 20000	R3（19996）	✗ WA
⚠ `p1010Zero`	`rep(0)` 返回空串	★ 对	✗ 0 / 20000	R2（19985）	✗ WA
★ `p1010`	—	对	✓ 0 / 20000	三条全过	★ AC

这一页记住三句话

★★★ 一道没有第二个算法的题，「对拍」退化成回归测试 —— 它只能证明「这次改动没引入差异」，证明不了正解是对的。 ⇒ 换成反着验：把输出解析回去求值。
★★★ 而反着验只看得见语义。 两万个 n 上 100% 通过，三个格式错法一个都没抓到 —— 2(1)、2()、顺序颠倒，它们代表的数全是对的。 ⇒ 这道题一半的分在格式上，最强的自动手段对格式一无所知。
★★★ 格式不是验不了，是规则要自己从题面里抄成断言。 三句题面 → 三个判据（2(E) 里 E ≠ 1 / 不许空括号 / 每层严格递减）， 各抓一个，一个不多一个不少，连漏掉的那几个 n 都对得上。 ★ 而这一切的前提是：n ≤ 2 × 10⁴ 小到可以一个不落地全跑 —— 范围能穷举的时候，别再抽样对拍了。

洛谷 P1010 [NOIP 1998 普及组] 幂次方

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

输入

输出

1算法只有五行，一半的分在格式上

2★★★ 这道题没有第二个算法 —— 于是「对拍」验不了正确性

3三个格式错法 —— 每一个都「算得完全正确」

4★★★ 反着验：把 20000 个 n 一个不落地跑完

5★ 顺带：数据范围小到能穷举的时候，别再对拍了

6一张总表