P1368 工艺 · 习题解析｜信息学奥赛算法练功房

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

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

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

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

⚠⚠ 顺带一条题单要订正的：第 49 章的题单里这道题写的是「洛谷 P1368【模板】最小表示法」，而洛谷现在这道题叫「工艺」 —— 题目背景那一行写着「新模板题：P13270【模板】最小表示法」。 ⇒ 题号没变、题名变了，本书的题单已按原站改成「P1368 工艺」。

题目背景

新模板题：P13270【模板】最小表示法。

题目描述

小敏和小燕是一对好朋友。他们正在玩一种神奇的游戏，叫 Minecraft。

他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。

他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。

两个工艺品美观的比较方法是，从头开始比较，如果第 i 个位置上方块不一样那么 谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 i+1 个方块。如果全都一样，那么这两个工艺品就一样漂亮。

输入格式

第一行一个整数 n，代表方块的数目。

第二行 n 个整数，每个整数按从左到右的顺序输出方块瑕疵度的值，保证其为小于 30 的非负整数。

输出格式

一行 n 个整数，代表最美观工艺品从左到右瑕疵度的值。

数据范围

对于 20% 的数据，n ≤ 1000；
对于 40% 的数据，n ≤ 10⁴；
对于 100% 的数据，n ≤ 3×10⁵。

时限 1 秒，内存 524288 KB（512 MB）。

输入输出样例

输入

10
10 9 8 7 6 5 4 3 2 1

输出

1 10 9 8 7 6 5 4 3 2

把 10 9 8 7 6 5 4 3 2 1 一直往右转，转到 1 排在最前面时字典序最小 ⇒ 输出 1 10 9 8 …。

1★★ 翻译成一句话：求字典序最小的那个循环移位

★ 「把最左边的方块搬到最右边」就是旋转

每做一次操作，序列就变成它的一个循环移位（rotation）。做 n 次回到原样 ⇒ 一共只有 n 个候选，问的是其中字典序最小的那个。

⇒ 这就是「最小表示法」这个名字的来处。

⚠ 而这道题从头到尾只有一句话需要读对

「如果第 i 个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮」

⇒ 要的是字典序最小的旋转。一个 < 写成 >，程序照样跑得飞快、格式一个字不差、输出照样是 n 个数 —— 它只是答了另一道题（见 p1368Rev.cpp，四档 300 / 300 / 300 / 248）。

p1368.cpp★ 正解：最小表示法，O(n)

// P1368 工艺（洛谷题库里的旧名字是「【模板】最小表示法」）—— 正解：最小表示法，O(n)。
//
// ★ 题目翻译过来只有一句：**把「最左边的方块搬到最右边」当作一次旋转，
//   求字典序最小的那个旋转**。
//
// ★★ 最小表示法的骨架（三个指针）：
//   拿两个候选起点 i、j 和一个「已经比对了多长」的 k：
//     · a[i+k] == a[j+k] ⇒ k++，接着比；
//     · a[i+k] >  a[j+k] ⇒ **i 这一段的前 k+1 个起点全都不可能是答案** ⇒ i += k + 1；
//     · 反之 j += k + 1。
//   ⚠ 那句「前 k+1 个起点全都不可能」是这个算法的全部内容，也是它唯一难的地方：
//     对任意 0 ≤ t ≤ k，从 i+t 开始的旋转，一定不比从 j+t 开始的那个小。
//   ⚠⚠ 而代码上最容易漏的是收尾那句 **`if (i == j) j++;`** —— 两个指针撞在一起
//     就再也分不开了（见 p1368Same.cpp）。
//
// ⇒ 这一章的路子（二分 + 哈希）见 p1368Hash.cpp：慢一个 log，但**不用证上面那句话**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        int x = a[(i + k) % n], y = a[(j + k) % n];
        if (x == y) { k++; continue; }
        if (x > y) i += k + 1; else j += k + 1;
        if (i == j) j++;                                   // ⚠ 两个指针撞上就把 j 推开
        k = 0;
    }
    int s = min(i, j);
    for (int t = 0; t < n; t++) {
        if (t) putchar(' ');
        printf("%d", a[(s + t) % n]);
    }
    putchar('\n');
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

2★★★ 这一章的路：二分＋哈希 —— 它买的不是速度，是「不用证那句话」

★★ 先看朴素那条路死在哪儿

第一版一定是「n 个起点，一个个和当前最好的比一遍」：

   for i = 1 .. n-1:
       把「从 i 开始的旋转」和「从 best 开始的旋转」逐位比

⇒ n 个起点 × 每次最坏 n 位 = O(n²) = 9×10¹⁰，顶格必挂。

★★ 而卡住它的从来不是「n 个起点」，是「比一次要 O(n)」。 ⇒ 于是这一章的招式直接对上了：

二分出两个旋转的最长公共前缀 L（每一步用哈希 O(1) 判「前 mid 位一不一样」）；
L == n ⇒ 两个旋转完全相同；否则比 a[i+L] 和 a[best+L] 这一个数。

⇒ 一次比较从 O(n) 降到 O(log n)，总共 O(n log n) = 3×10⁵ × 19 ≈ 5.7×10⁶。

⚠ 两个必须做对的细节： ① 把数组倍长（a + a）再做前缀哈希 —— 旋转 i 就是倍长数组上的一段，不用再取模； ② 二分的上界是 n，不是 n−1（两个旋转可以完全相同）。

p1368Hash.cpp★ 这一章的路：二分＋哈希，O(n log n)

// P1368 —— ★ 这一章的路：**二分 ＋ 哈希**，O(n log n)。
//
// ★★ 想法只有一句：朴素做法是「n 个起点两两比，每次比最坏 O(n)」⇒ O(n²)，过不去。
//   而卡住它的从来不是「n 个起点」，是「**比一次要 O(n)**」。
//   ⇒ 于是把「比较两个旋转」这一步换成：
//       ① 二分出这两个旋转的**最长公共前缀** L（每一步用哈希 O(1) 判「前 mid 位一不一样」）；
//       ② L == n ⇒ 两个旋转完全相同；否则比 a[i+L] 和 a[j+L] 这**一个数**。
//     一次比较从 O(n) 降到 O(log n) ⇒ 总共 O(n log n) = 3×10⁵ × 19 ≈ 5.7×10⁶。
//
// ⚠ 两个必须做对的细节：
//   ① **把数组倍长**（`a + a`）再做前缀哈希 —— 旋转 i 就是倍长数组上的 [i, i+n)，不用再取模；
//   ② **二分的上界是 n，不是 n−1** —— 两个旋转可能完全相同（序列有周期时一定会发生）。
//
// ★★ 而这一页真正的收获是那句题单注解：**哈希不是这道题的正解，它是「想不到 O(n) 那招时的保底」。**
//   最小表示法只有十行，可它压着一句要证的话；这条路多一个 log、多三十行，
//   但**每一步都是你已经会的东西**。
#include <bits/stdc++.h>
using namespace std;

const long long MOD1 = 1000000007, MOD2 = 998244353;
const long long B1 = 131, B2 = 13331;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int N = 2 * n;
    vector<long long> h1(N + 1, 0), h2(N + 1, 0), p1(N + 1, 1), p2(N + 1, 1);
    for (int i = 0; i < N; i++) {
        long long c = a[i % n] + 1;                        // ⚠ +1：不许有值映射成 0
        h1[i + 1] = (h1[i] * B1 + c) % MOD1;
        h2[i + 1] = (h2[i] * B2 + c) % MOD2;
        p1[i + 1] = p1[i] * B1 % MOD1;
        p2[i + 1] = p2[i] * B2 % MOD2;
    }
    /* 倍长数组上的 [l, l+len) 的哈希 */
    auto sub = [&](int l, int len) {
        long long x = ((h1[l + len] - h1[l] * p1[len]) % MOD1 + MOD1) % MOD1;
        long long y = ((h2[l + len] - h2[l] * p2[len]) % MOD2 + MOD2) % MOD2;
        return make_pair(x, y);
    };
    /* 旋转 i 和旋转 j 的最长公共前缀（≤ n）*/
    auto lcp = [&](int i, int j) {
        int lo = 0, hi = n;                                // ⚠ 上界是 n
        while (lo < hi) {
            int mid = (lo + hi + 1) >> 1;
            if (sub(i, mid) == sub(j, mid)) lo = mid; else hi = mid - 1;
        }
        return lo;
    };

    int best = 0;
    for (int i = 1; i < n; i++) {
        int L = lcp(best, i);
        if (L < n && a[(i + L) % n] < a[(best + L) % n]) best = i;
    }
    for (int t = 0; t < n; t++) {
        if (t) putchar(' ');
        printf("%d", a[(best + t) % n]);
    }
    putchar('\n');
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 题单注解说得很老实：哈希不是这道题的正解

「⚠ 提高组：哈希不是正解，但拿哈希 + 二分能写出一个好懂的版本，正好练『二分 + 哈希』这个套路。」

★★★ 而量完之后这句话可以说得更准： 最小表示法只有十行，可它压着一句要证的话；二分＋哈希多一个 log、多三十行，但每一步都是你已经会的东西。

那句要证的话是：a[i+k] > a[j+k] 时，从 i、i+1、…、i+k 出发的旋转全都不可能是答案 （所以能一次跳 k+1 格）。⇒ 想不出它的时候，二分＋哈希就是保底。

3★★★ 顶格 ≠ 最坏：朴素那条路在顶格随机上只要 2 毫秒

p1368Count.cpp★ 全枚举验两个「精确的 0」＋次数表＋顶格秒表

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

226

227

// P1368 —— 三条路的次数 / 秒表，外加**把两个「精确的 0」全枚举验一遍**。
//
// ★ 这一页要回答三个问题：
//   ① 朴素那条 O(n²) 到底什么时候才死 —— ⚠ **顶格随机它跑得飞快**，得换形状；
//   ② 二分 ＋ 哈希（多一个 log）和最小表示法（O(n)）在顶格上差多少；
//   ③ ★★ 两份「看着像 bug 其实不会错」的版本，凭什么敢说「精确的 0」：
//      · 二分上界写成 `n − 1`（p1368Lcp.cpp）—— 靠的是「**两个旋转的 LCP 不可能正好是 n−1**」；
//      · 值不 `+1`（p1368Zero.cpp）—— 靠的是「**这道题的比较永远等长**」。
//      ⇒ 两条都全枚举验，**而且各配一个自检**（把前提拿掉，当场就错）。
//
// 用法：./p1368Count [enum|cnt|time|table|csv]
#include <bits/stdc++.h>
using namespace std;

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) { if ((c & 0xC0) == 0x80) continue; disp += (c < 0x80) ? 1 : 2; }
    return s + string(max(0, width - disp), ' ');
}
static string padLeft(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) { if ((c & 0xC0) == 0x80) continue; disp += (c < 0x80) ? 1 : 2; }
    return string(max(0, width - disp), ' ') + s;
}

static long long ops = 0;                        // 「比了多少个数」——一把和机器无关的尺子

/* ---------- ① 朴素：n 个起点挨个和当前最好的比 ---------- */
static int byNaive(const vector<int>& a) {
    int n = (int)a.size(), best = 0;
    for (int i = 1; i < n; i++)
        for (int k = 0; k < n; k++) {
            ops++;
            int x = a[(i + k) % n], y = a[(best + k) % n];
            if (x != y) { if (x < y) best = i; break; }
        }
    return best;
}

/* ---------- ② 最小表示法 ---------- */
static int byMin(const vector<int>& a) {
    int n = (int)a.size(), i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        ops++;
        int x = a[(i + k) % n], y = a[(j + k) % n];
        if (x == y) { k++; continue; }
        if (x > y) i += k + 1; else j += k + 1;
        if (i == j) j++;
        k = 0;
    }
    return min(i, j);
}

/* ---------- ③ 二分 ＋ 哈希；bound 是二分的上界（正解是 n），plus1 决定值要不要 +1 ---------- */
static const long long MOD1 = 1000000007, MOD2 = 998244353, B1 = 131, B2 = 13331;
static int byHash(const vector<int>& a, int boundCut, bool plus1) {
    int n = (int)a.size(), N = 2 * n;
    vector<long long> h1(N + 1, 0), h2(N + 1, 0), p1(N + 1, 1), p2(N + 1, 1);
    for (int i = 0; i < N; i++) {
        long long c = a[i % n] + (plus1 ? 1 : 0);
        h1[i + 1] = (h1[i] * B1 + c) % MOD1;
        h2[i + 1] = (h2[i] * B2 + c) % MOD2;
        p1[i + 1] = p1[i] * B1 % MOD1;
        p2[i + 1] = p2[i] * B2 % MOD2;
    }
    auto sub = [&](int l, int len) {
        long long x = ((h1[l + len] - h1[l] * p1[len]) % MOD1 + MOD1) % MOD1;
        long long y = ((h2[l + len] - h2[l] * p2[len]) % MOD2 + MOD2) % MOD2;
        return make_pair(x, y);
    };
    int best = 0;
    for (int i = 1; i < n; i++) {
        int lo = 0, hi = max(0, n - boundCut);
        while (lo < hi) { ops++; int mid = (lo + hi + 1) >> 1; if (sub(best, mid) == sub(i, mid)) lo = mid; else hi = mid - 1; }
        if (lo < n && a[(i + lo) % n] < a[(best + lo) % n]) best = i;
    }
    return best;
}

static vector<int> rot(const vector<int>& a, int s) {
    int n = (int)a.size();
    vector<int> r(n);
    for (int i = 0; i < n; i++) r[i] = a[(s + i) % n];
    return r;
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    bool csv = (mode == "csv");

    /* ================= ① 全枚举：字母表 {0,1}，长度 1..14 ================= */
    int total = 0, badMin = 0, badHash = 0, badCut1 = 0, badCut3 = 0;
    for (int L = 1; L <= 14; L++)
        for (int mask = 0; mask < (1 << L); mask++) {
            vector<int> a(L);
            for (int i = 0; i < L; i++) a[i] = (mask >> i) & 1;
            total++;
            vector<int> ref = rot(a, byNaive(a));
            if (rot(a, byMin(a)) != ref) badMin++;
            if (rot(a, byHash(a, 0, true)) != ref) badHash++;
            if (rot(a, byHash(a, 1, true)) != ref) badCut1++;      // 上界 n−1：该是 0
            if (rot(a, byHash(a, 3, true)) != ref) badCut3++;      // ⚠ 自检：上界 n−3 该现形
        }
    /* 「两个旋转的 LCP 不可能正好是 n−1」—— 长度 ≤ 12 的全部串上逐对数一遍 */
    long long pairs = 0, lcpIsNm1 = 0;
    for (int L = 2; L <= 12; L++)
        for (int mask = 0; mask < (1 << L); mask++) {
            vector<int> a(L);
            for (int i = 0; i < L; i++) a[i] = (mask >> i) & 1;
            for (int i = 0; i < L; i++)
                for (int j = i + 1; j < L; j++) {
                    int k = 0;
                    while (k < L && a[(i + k) % L] == a[(j + k) % L]) k++;
                    pairs++;
                    if (k == L - 1) lcpIsNm1++;
                }
        }
    /* 值不 +1 的自检：这道题的比较永远等长 ⇒ 没事；**换成不等长就当场撞** */
    int zeroBad = 0;
    for (int L = 1; L <= 14; L++)
        for (int mask = 0; mask < (1 << L); mask++) {
            vector<int> a(L);
            for (int i = 0; i < L; i++) a[i] = (mask >> i) & 1;
            if (rot(a, byHash(a, 0, false)) != rot(a, byHash(a, 0, true))) zeroBad++;
        }
    /* ⚠ 自检：拿同一份「不 +1」的哈希去比**不等长**的两段 —— "0" 和 "00" 立刻同值 */
    long long z1 = 0, z2 = 0;
    { long long h = 0; z1 = (h * B1 + 0) % MOD1; z2 = ((h * B1 + 0) % MOD1 * B1 + 0) % MOD1; }

    if (mode == "enum" || mode == "table") {
        printf("★ 全枚举：字母表 {0,1}、长度 1~14 的全部 %d 个序列\n\n", total);
        printf("    最小表示法 ↔ 朴素        不一致 %d 个\n", badMin);
        printf("    二分＋哈希 ↔ 朴素        不一致 %d 个\n", badHash);
        printf("    ★ 二分上界写成 n−1       不一致 %d 个  ⇐ 看着像 bug，其实一次都不会错\n", badCut1);
        printf("    ⚠ 自检：上界压到 n−3     不一致 %d 个  ⇐ 前提拿掉，当场现形\n", badCut3);
        printf("    ★ 值不 +1（0 就是 0）    不一致 %d 个  ⇐ 因为这道题的比较**永远等长**\n", zeroBad);
        printf("    ⚠ 自检：同一份哈希比不等长的两段 —— h(\"0\") = %lld、h(\"00\") = %lld ⇒ %s\n",
               z1, z2, z1 == z2 ? "★ 当场撞上" : "没撞");
        printf("\n    ★★ 上界 n−1 凭什么是对的：**两个旋转的 LCP 不可能正好是 n−1**\n");
        printf("       长度 2~12 的全部序列、逐对数：%lld 对里 LCP = n−1 的有 %lld 对\n", pairs, lcpIsNm1);
        printf("       （理由一行：两个旋转是同一个多重集 ⇒ 前 n−1 位都相同，剩那一位也只能相同）\n\n");
    }

    /* ================= ② 次数表 ================= */
    const int NS[3] = { 1000, 4000, 16000 };
    const char* SHAPE[3] = { "随机（值域 0~29）", "★ 整排相同", "★ 周期串（长 7 的段重复）" };
    long long cnt[3][3][3];                          // [shape][n][path]
    for (int sh = 0; sh < 3; sh++)
        for (int k = 0; k < 3; k++) {
            int n = NS[k];
            vector<int> a(n);
            mt19937 rg(20260909u + sh * 31 + k);
            for (int i = 0; i < n; i++)
                a[i] = (sh == 0) ? (int)(rg() % 30) : (sh == 1) ? 0 : (int)(i % 7 == 3);
            ops = 0; byNaive(a); cnt[sh][k][0] = ops;
            ops = 0; byHash(a, 0, true); cnt[sh][k][1] = ops;
            ops = 0; byMin(a); cnt[sh][k][2] = ops;
        }

    if (mode == "cnt" || mode == "table") {
        printf("★ 比了多少个数（一把和机器无关的尺子）\n\n");
        for (int sh = 0; sh < 3; sh++) {
            printf("  %s\n", SHAPE[sh]);
            printf("    %-8s %s %s %s\n", "n",
                   padLeft("✗ 朴素 O(n²)", 16).c_str(), padLeft("★ 二分＋哈希", 16).c_str(),
                   padLeft("★ 最小表示法", 16).c_str());
            for (int k = 0; k < 3; k++)
                printf("    %-8d %16lld %16lld %16lld\n", NS[k],
                       cnt[sh][k][0], cnt[sh][k][1], cnt[sh][k][2]);
            printf("    n 每翻 4 倍，朴素这一列 ×%.1f、×%.1f\n\n",
                   (double)cnt[sh][1][0] / (double)cnt[sh][0][0],
                   (double)cnt[sh][2][0] / (double)cnt[sh][1][0]);
        }
    }

    /* ================= ③ 顶格秒表 ================= */
    const int BIG = 300000;
    double tm[3][3];
    for (int sh = 0; sh < 3; sh++) {
        vector<int> a(BIG);
        mt19937 rg(20260909u + sh);
        for (int i = 0; i < BIG; i++)
            a[i] = (sh == 0) ? (int)(rg() % 30) : (sh == 1) ? 0 : (int)(i % 7 == 3);
        for (int p = 0; p < 3; p++) {
            if (sh != 0 && p == 0) { tm[sh][p] = -1; continue; }     // ⚠ 那两格是 n²，真跑要分钟量级
            double v[3];
            for (int r = 0; r < 3; r++) {
                auto t0 = chrono::steady_clock::now();
                volatile int x = (p == 0) ? byNaive(a) : (p == 1) ? byHash(a, 0, true) : byMin(a);
                (void)x;
                v[r] = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();
            }
            sort(v, v + 3);
            tm[sh][p] = v[1];
        }
    }

    if (mode == "time" || mode == "table") {
        printf("★ 秒表：顶格 n = 3×10⁵（3 次取中位数）\n\n");
        printf("    %s %s %s %s\n", padDisp("形状", 30).c_str(), padLeft("✗ 朴素", 14).c_str(), padLeft("★ 二分＋哈希", 15).c_str(), padLeft("★ 最小表示法", 15).c_str());
        for (int sh = 0; sh < 3; sh++) {
            printf("    %s", padDisp(SHAPE[sh], 30).c_str());
            for (int p = 0; p < 3; p++) {
                if (tm[sh][p] < 0) printf("%s", padLeft("跑不完", p == 0 ? 14 : 15).c_str());
                else printf("%s", padLeft(to_string((long long)(tm[sh][p] * 10) / 10.0).substr(0, to_string((long long)(tm[sh][p] * 10) / 10.0).find('.') + 2) + " ms", p == 0 ? 14 : 15).c_str());
            }
            printf("\n");
        }
        printf("\n    ⚠⚠ 「跑不完」那两格是 O(n²) = 9×10¹⁰ —— 而**顶格随机它只要几十毫秒**\n");
        printf("    ⇒ 顺手造一组顶格随机跑一遍，这个坑一步都看不见\n");
    }

    if (csv) {
        printf("total,%d\nbadMin,%d\nbadHash,%d\nbadCut1,%d\nbadCut3,%d\nzeroBad,%d\n",
               total, badMin, badHash, badCut1, badCut3, zeroBad);
        printf("pairs,%lld\nlcpIsNm1,%lld\nzeq,%d\n", pairs, lcpIsNm1, (int)(z1 == z2));
        for (int sh = 0; sh < 3; sh++)
            for (int k = 0; k < 3; k++)
                printf("cnt%d_%d,%lld %lld %lld\n", sh, NS[k], cnt[sh][k][0], cnt[sh][k][1], cnt[sh][k][2]);
        for (int sh = 0; sh < 3; sh++)
            printf("grow%d,%.1f %.1f\n", sh, (double)cnt[sh][1][0] / (double)cnt[sh][0][0],
                   (double)cnt[sh][2][0] / (double)cnt[sh][1][0]);
        for (int sh = 0; sh < 3; sh++)
            printf("time%d,%.1f %.1f %.1f\n", sh, tm[sh][0], tm[sh][1], tm[sh][2]);
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

★★ 同样是 n = 3×10⁵，只换形状就是「2 毫秒」和「跑不完」

题面说瑕疵度是「小于 30 的非负整数」。于是：

形状	✗ 朴素（比了多少个数）	★ 二分＋哈希	★ 最小表示法
随机（值域 0~29），`n = 16000`	16 537	208 513	24 166
★ 整排相同，`n = 16000`	255 984 000	223 986	16 000
★ 周期串（长 7 的段重复），`n = 16000`	18 325 710	221 646	16 006

n 每翻 4 倍，朴素这一列在随机数据上 ×4.0（线性！），在整排相同上 ×16.0（O(n²) 的签名）。

顶格 n = 3×10⁵ 的秒表（3 次取中位数，A 机 · WSL2 · 2026-09-09 · 独占）：

形状	✗ 朴素	★ 二分＋哈希	★ 最小表示法
随机（值域 0~29）	★ 2.0 ms	26.9 ms	1.6 ms
★ 整排相同	跑不完（9×10¹⁰）	40.4 ms	0.8 ms
★ 周期串	跑不完	31.1 ms	1.6 ms

⇒ ★★★ 顺手造一组顶格随机跑一遍，这道题的坑一步都看不见 —— 随机串上两个旋转平均比 1.03 个数就分出高下，朴素那条路根本没被逼出来。 ⇒ 「顶格 ≠ 最坏」又一次，而这一次的「最坏形状」是最容易想到的那个：整排都一样。

⚠ 顺带一条：二分＋哈希比最小表示法慢 17~50 倍（多一个 log、每次比较还带乘法和取模），可它离时限还有 25 倍余量 ⇒ 它是能过的。

p1368Naive.cpp✗ 朴素：答案永远对，只是跑不完

4★★★ 两份「看着像 bug、其实一次都不会错」—— 而它们各配一个自检

★ 第一份：二分上界写成 n − 1

第一眼这一定要出事：两个旋转完全相同是常事（序列有周期就会发生，整排都是 0 时每一对都相同） —— 上界卡在 n−1，那种情况下 LCP 被算成 n−1，然后还要拿 a[i+n-1] 和 a[j+n-1] 再比一次。

★★ 可它一次都不会错，靠的是一句和哈希毫无关系的话：

两个旋转的最长公共前缀，绝不可能正好是 n − 1。

理由一行：两个旋转是同一个多重集（就是原序列的 n 个数）。前 n−1 位都相同 ⇒ 剩下那一位也只能相同 ⇒ LCP 是 n，不是 n−1。

⇒ 于是 LCP 只有两种取值：n 或 ≤ n−2：

≤ n−2 时上界 n−1 一点都没削到它，二分找到的就是真值；
= n 时被削成 n−1，而那时 a[i+n-1] == a[j+n-1]（两个旋转本来就一样）⇒ 不会换 best。

★ 全枚举验过：字母表 {0,1}、长度 1~~14 的全部 32766 个序列，和朴素比 0 个不同；长度 2~~12 的全部序列逐对数 LCP，458748 对里 LCP = n−1 的有 0 对。

⚠⚠ 而这个「精确的 0」配了自检：把上界继续往下压到 n−3， LCP 恰好是 n−2 的那些对就被削过头了 —— 当场 12 个不同。 ⇒ ★★ 同样是二分的边界，差一格是噪声，再差一格是命门。

p1368Lcp.cpp★ 上界写成 n−1 —— 全枚举 0 个不同

★★★ 第二份：值不 +1 —— 而这一条把本章那句规矩的主语找出来了

第 49 章正文白纸黑字写着：字符要映射成 1..26，不许有谁被映射成 0 （否则 h("a") 和 h("aa") 都会是 0）。而这道题的瑕疵度是「小于 30 的非负整数」，0 就在值域里，看着正撞枪口。

★★ 可它在这道题上一次都不会错，理由只有一句： 这道题里所有的比较都是等长的 —— 二分 LCP 比的永远是「两段同样长的」。而「映射成 0」毁掉的是不等长的比较。

★ 全枚举验过：同样那 32766 个序列，+1 和不 +1 两版 0 个不同。 ⚠ 而自检就在同一份程序里：拿同一份不 +1 的哈希去比不等长的两段 —— h("0") 和 h("00") 当场都是 0。

⇒ ★★★ 于是本章那条规矩的主语被这一页和 P3370 一起钉住了： 「不许映射成 0」是不是命门，取决于「你会不会拿两段不等长的东西去比」。 P3370 要比的正是长度不同的整串（0 / 00 / 000）⇒ 命门；这道题永远等长 ⇒ 噪声。

p1368Zero.cpp★ 值不 +1 —— 在这道题上是噪声

5⚠ 真会错的三个：两句收尾＋一个方向

★ 最小表示法的两句收尾，漏哪一句都错，而触发条件完全不同

   if (x > y) i += k + 1; else j += k + 1;
   if (i == j) j++;          // ① 两个指针撞上就把 j 推开
   k = 0;                    // ② 起点动了，比过的那一截就作废

漏掉	它变成了什么	触发条件
① `if (i == j) j++`	两个指针指同一个起点 ⇒ 两边永远相等 ⇒ `k` 一路加到 `n` 退出，`min(i,j)` 是个没被验证过的起点	跳的过程中真的撞上 —— 重复段越多越容易
② `k = 0`	下一轮从半空中接着比，跳过了本该比的那几位	只要发生过一次「不相等」

⇒ 两句长得一样（都是「循环体收尾少一句」），可 ② 的触发条件宽得多 —— 四档实测 ① 是 200 / 184 / 169 / 90，② 是 74 / 252 / 266 / 168。

p1368Same.cpp✗ 错法一：漏了 if (i == j) j++

// P1368 —— ✗ 错法二：最小表示法漏掉了那句 `if (i == j) j++;`。
//
// ★ 那一句看着像个补丁，其实是这个算法的一部分：`i += k+1` 之后 i 有可能**正好跳到 j 上**，
//   而两个指针指向同一个起点之后，`a[(i+k)%n]` 和 `a[(j+k)%n]` 永远相等
//   ⇒ k 一路加到 n，循环靠 `k < n` 退出，最后取 `min(i, j)` —— **它拿的是一个没被验证过的起点**。
//
// ⚠ 触发条件：跳的过程中 i 和 j 真的撞上。序列里**重复的段越多越容易撞**，
//   而这道题的值域只有 30 个数、n 到 3×10⁵ ⇒ 真实数据上撞是常态。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        int x = a[(i + k) % n], y = a[(j + k) % n];
        if (x == y) { k++; continue; }
        if (x > y) i += k + 1; else j += k + 1;
        /* ⚠ 少了这一句：if (i == j) j++; */
        k = 0;
    }
    int s = min(i, j);
    for (int t = 0; t < n; t++) { if (t) putchar(' '); printf("%d", a[(s + t) % n]); }
    putchar('\n');
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1368Reset.cpp✗ 错法二：忘了把 k 归零

p1368Rev.cpp✗ 错法三：方向读反，求成了最大表示法

6★ 对拍：四档 × 300 轮

p1368Gen.cpp★ 生成器：值域是这一页唯一的旋钮

// P1368 数据生成器（对拍用）。用法：./p1368Gen <seed> [档位]，不给档位就是**最终档 3**。
//
// ★ 每个错法靠什么现形：
//   ①漏了 i == j      ← 要「两个指针真的撞上」⇒ 序列里重复的段越多越容易，**小值域**是开关
//   ②忘了 k = 0       ← 只要发生过一次「不相等」就已经走歪
//   ③二分 off-by-one  ← 恒输出原序列 ⇒ 触发条件是「答案不是原序列」，随机就抓
//   ★ 而 p1368Lcp（上界 n−1）是**看着像 bug 其实不会错**的那一份，四档都该是精确的 0
//
// ⚠⚠ 题面的值域是「**小于 30 的非负整数**」—— 而这里默认把它压得更小（2~4 个值）：
//   [第 22 章 P1020](/sol/p1020/) 那条规矩，**生成器该照抄题面的「比值」而不是绝对规模**。
//   n 只有二三十的时候，值域 30 会让每个旋转第一位就分出高下，什么坑都碰不到。
//
// 档位：
//   0  ★ 顺手写法：n = 8~20，值域照抄题面（0~29）—— 几乎全是「第一位就分开」
//   1  ★ 值域压到 3 个值 —— 重复段变多
//   2  ★ 值域压到 2 个值 ＋ n 更长
//   3  ★★ 最终档：一半轮次造**周期串**（一段重复若干次）—— 两个旋转会完全相同
#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) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int level = argc > 2 ? atoi(argv[2]) : 3;
    rng.seed(seed * 2654435761u + 77u);

    vector<int> a;
    if (level == 0) {
        int n = ri(8, 20);
        for (int i = 0; i < n; i++) a.push_back(ri(0, 29));
    } else if (level == 1) {
        int n = ri(8, 24);
        for (int i = 0; i < n; i++) a.push_back(ri(0, 2));
    } else if (level == 2) {
        int n = ri(12, 30);
        for (int i = 0; i < n; i++) a.push_back(ri(0, 1));
    } else {
        if (ri(0, 1)) {                                    // ★ 周期串：一段重复若干次
            int u = ri(1, 5), rep = ri(2, 6);
            vector<int> unit;
            for (int i = 0; i < u; i++) unit.push_back(ri(0, 1));
            for (int r = 0; r < rep; r++) for (int i = 0; i < u; i++) a.push_back(unit[i]);
        } else {
            int n = ri(12, 30);
            for (int i = 0; i < n; i++) a.push_back(ri(0, 1));
        }
    }
    printf("%d\n", (int)a.size());
    for (size_t i = 0; i < a.size(); i++) printf("%d%c", a[i], i + 1 == a.size() ? '\n' : ' ');
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

（参照物是朴素枚举所有起点，它和最小表示法、和哈希都一行代码不共享；正解 vs 二分＋哈希：1200 轮 0 组不一致）

档位	✗ 漏 `i==j`	✗ 忘了 `k=0`	✗ 方向反了	★ 上界 `n−1`	★ 值不 `+1`
0 ★ 顺手写法：`n = 8~20`，值域照抄题面（0~29）	200	74	300	★ 0	★ 0
1 ★ 值域压到 3 个值	184	252	300	★ 0	★ 0
2 ★ 值域压到 2 个值＋ `n` 更长	169	266	300	★ 0	★ 0
3 ★★ 最终档：一半轮次造周期串	90	168	248	★ 0	★ 0

★★ 这张表读出来三条

★★ 生成器该照抄题面的「比值」，不是绝对规模（第 22 章 P1020 那条）—— 题面的值域是 30、n 到 3×10⁵ ⇒ 比值 10⁴；而对拍的 n 只有一二十，照抄值域 30 的话每个旋转第一位就分出高下，「忘了 k=0」只被抓 74 / 300。值域压到 3 个值就跳到 252。
★★★ 档 3（周期串）把三列一起往下压 —— 90 / 168 / 248，全是这一列里最低的。原因不是数据变弱了，是这道题输出的是「那个序列」，不是「那个下标」：序列有周期时很多旋转完全相同，挑错了起点也照样打出同一串数 ⇒ 一整类 bug 在这一档上是隐形的。 ⇒ ★★ 和第 26 章 P1040 / 第 31 章 B3644 那条正好反过来：那些题是「答案不唯一 ⇒ 逐字节比会误报」，这道题是「中间量不唯一、而输出唯一 ⇒ 逐字节比会漏报」。
★ 两份「看着像 bug」的四档全是精确的 0，而它们的自检不在这张表里，在上一节那个全枚举里（压到 n−3 ⇒ 12 个不同；比不等长的两段 ⇒ 当场撞）。

⚠ 官方那唯一一组样例：三个真错法只挡住一个

	✗ 漏 `i==j`	✗ 忘了 `k=0`	✗ 方向反了
样例 `10 9 8 7 6 5 4 3 2 1`	★ 死	放过	★ 死

★ 那组样例是严格递减、十个互不相同的数 —— 「忘了 k=0」需要「先比中一段、再失配」，而这组数据里每一对旋转第一位就分开了， k 从头到尾都是 0，归不归零一个样。 ⇒ 又一次「这组样例在结构上问不出这个问题」： 它连一次「相等」都没发生过。

7★ 哪一版就已经能过了

★★ 两版都能过，而这一页的收获是「哈希是保底」

版本	结果	说明
★ `p1368.cpp`（最小表示法）	AC	顶格 0.8~1.6 ms，十行
★ `p1368Hash.cpp`（二分＋哈希）	AC	顶格 27~40 ms，慢十几到几十倍，但余量仍有 25 倍
✗ 朴素 `O(n²)`	⚠ 看形状：随机 2 ms，整排相同跑不完	稳拿 40 分（`n ≤ 10⁴` 那两档）
✗ 漏 `if (i == j) j++`	WA	样例就死
✗ 忘了 `k = 0`	WA	⚠ 样例放过
✗ 方向读反	WA	样例就死

⇒ ★★★ 一句话带走：这一章的招式在这道题上不是最优解，它是「想不出那句话时的保底」。 而保底这件事本身很值钱 —— 考场上想不出最小表示法那句跳跃论证的时候，二分＋哈希是一条每一步都不用证的路，代价只是一个 log。

洛谷 P1368 工艺

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

输入

输出

1★★ 翻译成一句话：求字典序最小的那个循环移位

2★★★ 这一章的路：二分 ＋ 哈希 —— 它买的不是速度，是「不用证那句话」

3★★★ 顶格 ≠ 最坏：朴素那条路在顶格随机上只要 2 毫秒

4★★★ 两份「看着像 bug、其实一次都不会错」—— 而它们各配一个自检

5⚠ 真会错的三个：两句收尾 ＋ 一个方向

6★ 对拍：四档 × 300 轮

7★ 哪一版就已经能过了

2★★★ 这一章的路：二分＋哈希 —— 它买的不是速度，是「不用证那句话」

5⚠ 真会错的三个：两句收尾＋一个方向