FMCRAFT 我的世界服务器 2026 年 8 月 玩家数据汇总

https://www.tropical-fish.cn/usr/uploads/2026/09/3172396525.pdf

奖励已发放

20260831 主服务节点 维护通知

原始版本

开头

尊敬的用户：

请注意，目前有一个新的维护通知，涉及到您的正常使用，请阅读

描述

接上游 2026-08-28 21:37 通知，FMCRAFT 主服务节点 有一个新的维护通知：

服务器需要完成 网络接割，为了提高稳定性

影响

下面的网站无法正常使用：

(*.)fmcraft.top
(*.)slzx.work

下面的服务无法正常使用：

MC 服务器 登录组件：mc.tropical-fish.cn

欧洲卡车模拟2 服务器：85568392936646414

时间

绝对开始时间：2026-08-31 15:35
预计结束时间：2026-08-31 18:35

根据服务器提供商的通知，上面的结束时间是 预计 的，所以随时可能变化

如果在线，会进行对此通知的修改

补偿

针对于 mc.tropical-fish.cn，我们会在事后统计受到影响的玩家，并在本文完成更新（受到影响的玩家），具体的补偿标准根据 服务器意外事故、人工重启、停机维护、补偿标准，本次属于 停机维护，若上面的时间无变化，应为 21 积分

其他服务，无补偿

结尾

请耐心等待事件结束，我们将在本文更新处理进度

如有问题，请在社群反馈

FMCRAFT
2026-08-29 22:46

FMCRAFT 欧卡2 的一些配置

版本

1.60.1.7s

Mod

创意工坊 URL

https://steamcommunity.com/sharedfiles/filedetails/?id=1236032431

https://steamcommunity.com/sharedfiles/filedetails/?id=1122282180

顺序

1. Real Economy Reloaded
2. Real Traffic Density ETS2

不允许其他第三方模组

DLC

可选

服务器 Session ID

85568392936646414

字符串及文件读写

-1 检查浏览器渲染数学公式情况

因为笔者发布文章当天，本博客仍然存在 Latex 可能无法渲染的情况，下面是一个 Latex 示范：

$x$

• 如果正常显示为衡水体 x，则代表读者的浏览器已经成功渲染了 Latex
• 如果显示为 带有美元符号的 x 即 $x$（已除去换行符），则代表读者的浏览器没有成功渲染 Latex，读者可能需要刷新重试，如果刷新多次仍然无法渲染，请尝试换一个浏览器/网络环境

0 框架

你好，这里是 https://www.tropical-fish.cn/，本专题主要讲解 字符串及文件读写，感谢 深入浅出程序设计竞赛（基础篇） 提供的重要支持

这是 C++ 语法基础 的重要补充部分，包括了在 CCF 及其他系列比赛 获得 $\text{非}0$ 分数的方法，注意，这不是危言耸听

$$ \begin{aligned} &\textbf{字符串} \begin{cases} &\text{char}\\ &\text{string}\\ &\text{freopen} \end{cases} \end{aligned} $$

如上面的框架，笔者会介绍

• 字符串的存储
• 字符串的处理方法
• STL 字符串
• 文件输入输出

不废话了，现在开始！

1 char 字符数组

字符数组的 ASCII 本质与常用字符表

字符数组本质上和整数数组并没什么太大的区别，整数数字每一个下标存的是数字，字符数字存的是 字符（其实是 ASCII 码对应的数字），将这些字符存到数组里，便成为了一串字符，即 字符串，下面这张表是 ASCII 表，它们分别将 数字 对应了 字符，读者并不需要记忆全部的内容，仅需要记忆关键的键值，例如 0、A、a、 （空格），它们相对重要

图片

其中的第 $0 \sim 31 \& 127$ 号字符是控制字符，第 $32$ 号字符是空格

在 OI 的场景下，一般只有第 $32 \sim 126$ 号元素起到了相对关键的作用

【题目样本 1.1】P5733 自动修正

题目描述

https://www.luogu.com.cn/problem/P5733

大家都知道，一些办公软件有自动将小写字母转换为大写的功能

输入一个长度不超过 $100$ 且不包括空格的字符串。要求将该字符串中的所有小写字母转换成大写字母并输出

例如输入 Luogu4!, 输出 LUOGU4!

做法 1

分析

既然单个字符可以使用 char 类型存储，那么存储一串字符就可以使用数组，我们可以定义一个数组 $s[]$，其中每一个下标都是字符类型，即 char s[100];，这样的 字符数组 就叫 字符串

读入字符串的办法大同小异

1. 使用 scanf("%s",s);读入一个字符串，其中 %s 代表数据类型，即字符串，s 是定义的字符数组的名字
   至于为什么不需要取地址符 &，因为 s 是一个数组，这里的 s 在大多数表达式中会 自动转换为指向数组首元素的指针，即 &s[0]，类型是 char*，仅此而已
2. 使用 cin>>s;

请 特别注意 这一点，这两种读入方法只能读到空格、换行符、EOF（文章后面会有讲解），至于输入想要包含空格、换行符又想读入到同一个字符数组中，需要使用其他办法，文章后面同样会有讲解

参考代码

这段代码摘取至 深入浅出

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    char s[110];
    scanf("%s", s); // 读入这个字符串，还可以使用 cin>>s; 语句
    for (int i = 0; s[i] != '\0'; i++) // s[i] != '\0' 也有别的方法获取，具体会在文章后面提到
        if ('a' <= s[i] && s[i] <= 'z') /* 如果这个字符在'a'到'z'中间，说明是小写字母 */
            s[i] -= 'a' - 'A'; // 把这个字母转换成对应的大写字母，减去偏移量
    printf("%s\n", s); // 输出这个字符串，还可以使用 cout<<s<<endl; 语句
    return 0;
}

ASCII 码偏移量

这本身并不是一个特有名词，反倒是一个通俗的用语，它的意思由 Deepseek V4 Pro 提供：利用 ASCII 码表中字母的连续编码，通过加减一个固定值（偏移量）来实现大小写转换或字符映射

至于能否听懂，那就因人而异了，下面是一段解释：

如果你认真看了上面的 ASCII 表，你应该会发现 小写字母的顺序和大写字母的顺序分别是按照字母表的顺序排列的，a-A 是小写字母和对应大写字母的 ASCII，这被通俗地认为为 偏移量，这在其他的场景中也有体现，为了缩短篇幅，这里不再阐释，请 特别注意，小写字母的 ASCII 码相对于大写字母大

那么就很好说了，上面的代码利用 if ('a' <= s[i] && s[i] <= 'z') 判断是否是小写字母，如果是，减去偏移量，这样得到的字母就是大写字母了

字符串存储与 \0 结束标记

这段字符串在字符数组中的存储方式如下图

$s[]$ 中的每一个元素，都存储了一个不超过 $127$ 的整数，它们分别对应了 ASCII 编码中的字符

最开始的字符存在 $s[0]$，这个字符串虽然有且仅有 $7$ 个字符，但它却占用了 $8$ 个下标，即 $s[0] \sim s[7]$，字符串的末尾，存了一个特殊的字符 结束标记字符，它是 \0 ，也可能会有 \n 换行符，划掉的原因是因为笔者暂时没有找到任何明确的证据，这个结束标记被用于提示一个字符串的结束位置，它会在修改字符串的时候自动调整，一个例子，我们在用 cout<<s 的时候，结束标记就会告诉 cout 字符串已经没了，提一嘴，类似这样的 “特殊字符”，还有好几个，例如 \n（ASCII 表中可能被表示为 10，划掉的原因同上）

[collapse status="true" title="如何表示 \？"]

#include <bits/stdc++.h>
using namespace std;
int main(){
    cout<<"\\";
}

cout 内的第一个 \ 是转义符，转义后面的字符，因为第二个 \ 转义了 "，为了避免第二个 \ 被转义，所以只好用第一个 \ 转义第二个 \，这样第二个 \ 就不会转义 " 了

控制台输出：

PS D:\Users\Lenovo\Downloads\output> & .\'test.exe'
\

[/collapse]

做法 2

分析

当然，也不用一次直接读入整个字符串，可以每次只读入一个字符，判断是否需要处理，（处理后）输出这个字符即可

这里可以使用 getchar() 函数获取输入中的一个字符，如果你具有好奇心，你可以打开下面的折叠框

[collapse status="true" title="getchar() 的返回类型"]
getchar() 被定义于 cstdio 头文件，因此你需要在使用的时候导入这个头文件

答案：getchar() 返回 int 类型

至于为什么不返回 char，这是因为它要正确处理文件结尾标识符 EOF，后面你就能看见了，马上

因此，尽管你定义了一个 char 类型的变量，调用 getchar() 的时候他会自动根据 ASCII 表转换成 char 类型

这是一个例子：

#include <bits/stdc++.h>
using namespace std;
int main(){
    char s;
    cout<<"请键入一个字符：";
    s=getchar();
    cout<<"您键入的字符是："<<s;
}

PS D:\Users\Lenovo\Downloads\output> & .\'test.exe'
请键入一个字符：s
您键入的字符是：s

[/collapse]

相应的，putchar() 用于输出一个字符

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    char s;
    while (1) {
        s = getchar(); // 每次调用 getchar() 函数，读入一个字符
        if (s == EOF)
            break;
        if ('a' <= s && s <= 'z') // 如果这个字符是小写字母
            s += 'A' - 'a'; // 把它转换成大写字母，这样写和上面是一样的
        putchar(s); // 调用 putchar() 函数，输出一个字符
    }
    return 0;
}

输入结束和 EOF

运行程序，结果发现无论输入什么，程序都没有反应，这是因为程序不认为输入已经结束了，继续在等待输入

遇到这种情况，输入完字符串后，按一下 Ctrl+Z 组合键，再按一次回车，就可以完成读入了

程序中读入一个字符都会判断是否读完了整个文件，如果文件被读完了，那么 getchar() 函数会返回 EOF（一个特殊的常量)，即 End of File，这标志着读入已经结束了

在控制台中可以使用 Ctrl+Z 组合键（Windows 下）或者 Ctrl+D 组合键（Linux 下）来输入 EOF 标记提示程序输入已经完毕

至于一些教材使用的 gets() 函数将字符串读入字符数组，由于存在字符数组越界的风险， 已经不再建议使用，新的 C++11 标准更是删除了这个函数

而输出一个字符串还可以使用 puts() 方法，同时会自动输出换行，这倒是还能使用

如果您了解 HUSTOJ，您应该会遇到 #define gets(S) fgets(S,sizeof(S),stdin)，仅仅提一嘴

【题目样本 1.2】P1914 凯撒密码

题目描述

https://www.luogu.com.cn/problem/P1914

凯撒密码是由原文字符串（由不超过 $50$ 个小写字母组成）中每个字母向后移动 $n$ 位形成的

z 的下一个字母是 a，如此循环

给出 $n$ 和移动前的原文字符串，请求出密码

分析

你可以导入这个字符串，一个一个处理，然后输出

你需要注意，你不能直接给每一位加上 $n$ 然后输出，因为可能会溢出，举一个例子，一个字符串是 $\text{z}$，$n=5$，如果直接加上答案就是 $\text{DEL}$（$127$），如果不清楚这是什么，请翻阅前面的 ASCII 表，很明显答案是错的

所以，我们应该使用 s[i]-'a' 来计算和 $\text{a}$ 的偏移量，然后加上 $n$，得到目标字母的位置，一个例子，$\text{b}$ 这个字母移动 $4$ 位，就是第 $1$ 个字母（$\text{a}$ 是第 $0$ 个字母）向右移动 $4$ 位，是第五个字母，即 $\text{f}$

为了要求这个位置始终在 $0 \sim 25$ 之间，我们应当把上一段计算除的结果对 $26$ 取模，后面还需要再加上 $\text{a}$，以还原为字母，记 s[i]-'a' 为 $t$，则计算的答案为 $(t \bmod 26)+\text{a}$

警告：读者应当理解 $a$ 与 $\text{a}$ 的区别，第一个指的是字母，第二个指的是值

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n;
    char s[60];
    scanf("%d %s", &n, s);    // 读入字符串
    for (int i = 0; s[i] != '\0'; i++)
    putchar((s[i] - 'a' + n) % 26 + 'a');    // 计算偏移量并还原
    return 0;
}

【题目样本 1.3】P1125 [NOIP 2008 提高组] 笨小猴

题目描述

给出一个单词（由不超过 $100$ 个小写字母组成），假设 $maxn$ 是单词中出现次数最多的字母的出现次数，$minn$ 是单词中出现次数最少的字母的出现次数，如果 $maxn-minn$ 是一个质数，那么笨小猴就认为这是个 $\text{Lucky Word}$，输出 Lucky Word，然后在第二行输出 maxn-minn 的值；否则输出 No Answer，第二行输出 0

分析

考虑 计数排序思想，读入一个字母，用 $f[]$ 数组记录 $a \sim z$ 字母出现的数量，可以转换成 $0 \sim 25$ 的数字但是直接存更方便，$f[]$ 数组的大小为 $129$，这是 ASCII 表 非拓展字符的值域，随后使用 打擂台 思想寻找出现 次数最多的字母 和 非 $0$ 的最少，判断差是否为质数

bool isPrime(int n) { // 判断质数
    // 小于2的数不是质数
    if (n < 2) {
        return false;
    }
    
    // 从2到n-1逐个试除
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;  // 能被整除，是合数
        }
    }
    
    return true;  // 都不能整除，是质数
}

[collapse status="false" title="判断质数极限方法"]

inline uint64_t isqrt_u64(uint64_t n) { // 判断质数：小数字用试除（快），大数字用 Miller-Rabin（更快）
    if (n < 2) return n;
    uint64_t x = n;
    uint64_t y = (x + 1) >> 1;
    while (y < x) {
        x = y;
        y = (x + n / x) >> 1;
    }
    return x;
}

inline uint64_t mod_mul(uint64_t a, uint64_t b, uint64_t mod) {
    return (__uint128_t)a * b % mod;
}

inline uint64_t mod_pow(uint64_t a, uint64_t d, uint64_t mod) {
    uint64_t res = 1;
    while (d) {
        if (d & 1) res = mod_mul(res, a, mod);
        a = mod_mul(a, a, mod);
        d >>= 1;
    }
    return res;
}

bool isPrime(uint64_t n) {
    if (n < 2) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true;
    if ((n & 1) == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false;
    
    // 小数字用试除（更快）
    if (n < 1000000000ULL) {
        uint64_t limit = isqrt_u64(n);
        for (uint64_t i = 11; i <= limit; ) {
            if (n % i == 0) return false;
            if (n % (i + 2) == 0) return false;
            if (n % (i + 6) == 0) return false;
            if (n % (i + 8) == 0) return false;
            if (n % (i + 12) == 0) return false;
            if (n % (i + 18) == 0) return false;
            if (n % (i + 20) == 0) return false;
            if (n % (i + 26) == 0) return false;
            i += 30;
        }
        return true;
    }
    
    // 大数字用 Miller-Rabin
    uint64_t d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    
    static const uint64_t bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (uint64_t a : bases) {
        if (a >= n) continue;
        uint64_t x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = mod_mul(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

具体内容不解释，自行搜索

上述内容取自 Deepseek V4 Pro
[/collapse]

如果有需要，可以封装成 namespace

参考代码

同样取自 深入浅出

#include <stdio.h>
#include <iostream.h>
#include <string.h>
using namespace std;

int main() {
    char a[110];
    int ans[26] = {0};              // ans[0] 到 ans[25] 分别代表 'a' 到 'z' 出现的次数，注意要初始化
    int l, mmax, mmin, delta;       // 字符长度，出现次数最多的字母出现次数和出现次数最少的字母出现次数，以及差值

    scanf("%s", a);
    l = strlen(a);

    for (int i = 0; i < l; i++) {
        ans[a[i] - 'a']++;          // 统计增加某个字母的数量
    }

    mmax = 0;
    mmin = 10000;                   // 最大最小值初始化

    for (int i = 0; i < 26; i++) {  // 寻找每个字母的最大值和最小值
        if (ans[i] > mmax) {
            mmax = ans[i];          // 如果超过最大值
        }
        if (ans[i] != 0 && ans[i] < mmin) {
            mmin = ans[i];          // 如果小于最小值，但是不能为 0
        }
    }

    delta = mmax - mmin;

    if (delta == 0 || delta == 1) { // 质数特判
        printf("No Answer\n0\n");
        return 0;
    }

    for (int h = 2; h * h <= delta; h++) {  // 枚举质数
        if (delta % h == 0) {
            printf("No Answer\n0\n");       // 直接输出答案并退出程序
            return 0;
        }
    }

    printf("Lucky Word\n%d\n", mmax - mmin);
    return 0;
}

string 头文件

这是一个前所未有的新头文件，它包含了一些新的头文件

这里有一些新的用法，供读者参考：

• size_t strlen(const char *s); 求 char 数组的长度，将要求长度的数组放进 () 之中，在大部分情况下被 typedef 定义为 unsigned int，这也是为什么你在用 for(int i=0;i<strlen(s);i++) 会报 Warn 的原因，类型不同
• char *strcpy(char *dest, const char *src); 将 *str 复制到 *dest，即复制字符串，返回值一般无用

• int strcmp(const char *s1, const char *s2); 判断两个字符数组是否相同，下面是返回值及意义

  • $=0$ 是 $s1$ 和 $s2$ 完全相同
  • $\lt 0$ 是 $s1$ 小于 $s2$
  • $\gt 0$ 是 $s1$ 大于 $s2$

字符数组不能直接复制一个字符串，因为字符数组中的数组名也只是一个数组名，上面提供的函数可能会有作用

但是 char a[100]="TropicalFish"; 是合法的

【题目样本 1.4】P1957 口算练习题

题目描述

https://www.luogu.com.cn/problem/P1957

王老师收集了 $i(i \leq 50)$ 道学生经常做错的口算题，并且想整理编写成一份练习

王老师希望尽量减少输入的工作量，比如 $5+8$ 的算式最好只输入 5 和 8，输出的结果要尽量详细以方便后期排版使用

对于上述输入进行处理后，输出 5+8=13 以及该算式的总长度 6

输入数据第 $1$ 行是 $i$，接着的 $i$ 行是需要输入的算式，每行可能有 $3$ 个数据或两个数据

• 若该行是 $3$ 个数据，则第一个数据表示运算类型，a 表示加法运算，b 表示减法运算，c 表示乘法运算，接着的两个数据表示参加运算的运算数
• 若该行是两个数据，则表示本题的运算类型与上一题的运算类型相同，而这两个数据为运算数

分析

笔者写到这里的时候，就比较随意了，因为本题没有多大的实际意义，一般地，它只是作为一道相对复杂的应用题/模拟题

在本题中 switch-case 相对于 if-else 更加方便

sscanf 与 sprintf

他们的作用都是从字符串中读入/写出

请区别 scanf 与 printf

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
    int n, a, b, c;
    char last, s[20], ans[20];
    scanf("%d\n", &n);
    while (n--) {
        fgets(s, sizeof(s), stdin); // 读入一行
        if (s[0] == 'a' || s[0] == 'b' || s[0] == 'c')
            last = s[0], s[0] = ' '; // 获取计算符号，并替换为空格
        sscanf(s, "%d %d", &a, &b); // 从这个字符串里面读入两个数 a 和 b 
        switch (last) {
            case'a': c = a + b; sprintf(ans, "%d+%d=%d", a, b, c); break; // +
            case'b': c = a - b; sprintf(ans, "%d-%d=%d", a, b, c); break; // -
            case'c': c = a * b; sprintf(ans, "%d*%d=%d", a, b, c); break; // ×
        }
        printf("%s\n%d\n", ans, strlen(ans)); // 输出
    }
    return 0;
}

上面的代码同样改编于 深入浅出

2 string 字符串

从 C 风格字符串到 C++ STL 的 string 类型

$$ \left\{ \begin{array}{l} \textbf{C++ 标准库} \\ \left\{ \begin{array}{l} \textbf{STL（标准模板库）} \\ \left\{ \begin{array}{l} \text{容器} \left\{ \begin{array}{l} \text{vector} \\ \text{list} \\ \text{map} \\ \boxed{\text{string}} \quad \text{（核心问题）} \end{array} \right. \\ \text{迭代器} \\ \text{算法} \\ \text{适配器} \\ \text{分配器} \\ \text{函数对象} \end{array} \right. \\ \text{其他组件} \left\{ \begin{array}{l} \text{I/O 流} \\ \text{异常处理} \\ \text{内存管理} \end{array} \right. \end{array} \right. \end{array} \right. $$

上面的思维导图由 Deepseek V4 Pro 生成，它体现了 string 与 STL 的主要关系

很明显的，使用 C 语言的字符数字有很多不便（char 是属于 C 语言的），比如 不能：

• 弹性变化长度
• 直接赋值
• 直接复制
• 有数组越界的风险（gets）

好消息是，C++ 中提出了 STL 这一概念，即 标准模板库，将很多有用的功能进行了封装，直接就可以用，不需要重新开发这些功能，我们为 2017 年的 OI 选手默哀，已经封装的功能包括但不限于：

• 栈（stack）
• 队列（queue）
• 排序（sort）

总的来说，封装了容器、算法、其他功能，现在，我们会使用 string 解决字符串问题

【题目样本 2.1】P5015 [NOIP 2018 普及组] 标题统计

题目描述

https://www.luogu.com.cn/problem/P5015

凯凯刚写了一篇美妙的作文，请统计这篇作文的标题中有多少个字符

注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符，且字符串中的字符和空格数总和不超过 $5$

统计标题字符数时，空格和换行符不计算在内

分析

因为使用 cin 读入字符串时会忽略空格，并且读到 空格 或者 换行符 就停止了，所以可以将读入写进 while() 中，每次读入一个字符串，把长度加入答案即可

至于读入整行，会在 【题目样本 2.3】 中给出方法

参考代码

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    int ans = 0;
    while (cin >> s)
        ans += s.length();
    cout << ans << endl;
    return 0;
}

深入浅出

string：字符串的加强版数据类型

这里没使用 char，而是使用了一种新的数据类型 string，一个 string 类型的变量可以用来存储一个字符串，还可以把这个字符串当成一个整体的处理，string 的功能包括但不限于：

• 赋值
• 拼接
• 裁剪

char 毕竟是个数组，能做到这些就很烦了

输人时使用 cin 语句，不断读入字符串

当发现读入文件读完后（遇到 EOF，可以按 Ctrl+Z 组合键），cin>>s 本身就会返回 $0$，中断 while 语句，结束读入

这里的 $s$ 变量可以被认为是一个“加强版“的字符数组，可以使用 s.length()（s.size()） 来直接查询字符串 $s$ 的长度，也可以和字符数组一样使用 $s[0]$ 来查询这个字符串最开头的字符是什么

更厉害的是，string 类型的字符串可以直接拿来赋值、拼接操作，比如 s=s+s 就是将两个字符串 $s$ 拼接在一起，其结果赋值回 $s$ 的意思，请注意，这里提到的代码操作的时间复杂度是 $O(n)$，建议写 s+=s（s.append(s) 会在 【题目样本 2.2】 提到）

上述描述操作的便利性可不是字符数组可以比较的

【题目样本 2.2】P5734 文字处理软件

题目描述

https://www.luogu.com.cn/problem/P5734

现在需要开发一款文字处理软件

最开始时输入一个字符串（不超过 $100$ 个字符）作为初始文档

可以认为文档开头是第 $0$ 个字符，需要支持以下操作

1. 1 str: 后接插入，在文档后面插入字符串 $\text{str}$，并输出文档的字符串
2. 2 a b: 截取文档部分，只保留文档中从第 $a$ 个字符起 $b$ 个字符，并输出文档的字符串
3. 3 a str: 插入片段，在文档中第 $a$ 个字符前面插入字符串 $\text{str}$，并输出文档的字符串
4. 4 str: 查找子串，查找字符串 $\text{str}$ 在文档中最先出现的位置并输出；如果找不到输出 -1

为了简化问题，规定初始的文档和每次操作中的 $\text{str}$ 都不含有空格或换行

最多会有 $q (q \leq 100)$ 次操作

例如输入数据是：

4
ILove
1 Luogu
2 5 5
3 3 guGugu
4 gu

那么输出数据是：

ILoveLuogu
Luogu
LuoguGuuguugu
3

保证每次操作输入的字符串长度不超过 $100$ 且输入合法（($2$) 和 ($3$) 操作不会越界）

分析

string 需要头文件 string，方法包括但不限于：

1. string s: 定义一个名字为 $s$ 的字符串变量
2. s += str 或 s.append(str): 在字符串 $s$ 后面拼接字符串 $\text{str}$
3. s < str: 比较字符串 $s$ 的字典序是否在字符串 $\text{str}$ 的字典序之前
4. s.size() 或 s.length(): 得到字符串 $s$ 的长度
5. s.substr(pos, len): 截取字符串 $s$，从第 $pos$ 个位置开始 $len$ 个字符，并返回这个字符串
6. s.insert(pos, str): 在字符串 $s$ 的第 $pos$ 个字符之前，插入字符串 $\text{str}$，并返回这个字符串
7. s.find(str, [pos]): 在字符串 $s$ 中从第 $pos$ 个字符开始寻找 $\text{str}$，并返回位置，如果找不到返回 $-1$，$pos$ 可以省略，默认值是 $0$

灵活地运用上面的这些办法，可以使笔者更好地玩此题目

额外需要注意：s.find() 在 无法找到 时，会返回 string::npos，因此，你可以利用 s.find("bqiu")!=string::npos 判断 $s$ 中是否包含 $\text{bqiu}$，如果包含，返回 $1$，反之 $0$

string 的赋值

string a, b;
a="bqiu";
b=a;

上面的代码完全可以通过编译

但是 char 不行

【题目样本 2.3】P1308 [NOIP 2011 普及组] 统计单词数

题目描述

https://www.luogu.com.cn/problem/P1308

给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置

注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同，如果给定单词仅是文章中某一单词的一部分则不算匹配

分析

s.find() 是一个好东西

请注意，若 $s$ 为 $\text{to be or not to be is a question}$，在搜索 $\text{tion}$ 时，是否会检索到包含单词 question？

因此，你可以搜索 tion ，全字匹配

如果你这样做，你可能会意识到这个问题，如果 tion 在文章的结尾怎么办？

我们可以将 $s$ 的前后加上空格，即 s=' '+s+' '，这样就可以方便地解决这个问题

你太牛逼了

至于统计次数，你可以记下 find() 每次的返回值（位置），然后将位置作为参数继续查找，直到找到了 string::npos 就可以完成，这就是找到了多少次

getline：整行读入

为了方便地读取整行字符串，不用被 cin 的傻逼特性干扰，我们可以使用 getline() 函数，它的作用是将完整的一行的输入数据读入（到字符串中），一般地，它的用法是 getline(cin,<string_name>)，<string_name> 指 string 字符串的名字

string：其他

下面的这一个代码，体现了 string 具有强大的扩展性

// string 转字符数组
char arr[10];
string s = "LUOGU";
int len = s.copy(arr, 9); // 最多允许复制 9 个字符，否则就越界了
arr[len] = '\0'; // 在末尾增加结束标记

// 或者
char arr[10];
string s = "LUOGU";
strcpy(arr, s.c_str()); // strncpy(arr, s.c_str(), 10);

// 字符数组转 string 就更简单了
char arr[10];
strcpy(arr, "LUOGU");
string s;
s = arr;

在这里表示对 DeepSeek 的尊敬！

3 freopen 文件操作

废话

直到现在为止，绝大部分的输入输出方式都是 标准输入输出，即 stdin 与 stdout

但在很多程序设计竞赛中，例如万恶的 CCF，它们要求使用文件输入输出，这种输入输出的方式，可以将硬盘上的文件读入到程序，将程序中的输出写入到硬盘，Linux 中的 < 和 > 重定向符号和这个是一个道理，如果你没有在竞赛中使用文件读写，你会获得一个最小的自然数的分数

题目样本

题目描述

https://www.tropical-fish.cn/usr/uploads/2026/08/1163827895.pdf

分析

这是 $\text{2024 CCF 非专业级软件能力认证 CSP-J/S 2024 第二轮认证}$ 的真题，请看试题卷 题目 A poker

这道题是一道非常简单的模拟题，参考代码如下

#include <bits/stdc++.h>
using namespace std;
int T,ans;
string s;
map <string,int> f;
int main(){
    cin>>T;
    while(T--){
        cin>>s;
        if(!f[s]) ans++,f[s]=1;
    }
    cout<<52-ans;
}

但是，如果读者直接将这个代码作为你的程序提交，你会获得 0 分的好成绩，请看试题卷第一页，它给出了 英文题目与子目录名、提交源程序文件名、可执行文件名、输入文件名、输出文件名，我们必须按照这个要求使用，虽然其他信息也相对重要，但是就文章标题而言，没那么重要

根据要求，我们应当将文件保存为 /<英文题目与子目录名>/<提交源程序文件名>，也就是 /poker/poker.cpp，然后，我们需要学会使用 freopen，下面是一个比较基础的用法

freopen("<read_file_name>","r",stdin);
freopen("<write_file_name>","w",stdout);

一般它会放在 main 函数的下面

也就是说，这题的代码需要改成：

#include <bits/stdc++.h>
using namespace std;
int T,ans;
string s;
map <string,int> f;
int main(){
    freopen("poker.in","r",stdin);
    freopen("poker.out","w",stdout);
    cin>>T;
    while(T--){
        cin>>s;
        if(!f[s]) ans++,f[s]=1;
    }
    cout<<52-ans;
}

本地运行后，发现程序一闪而过，啥也没有，反倒程序文件目录出现了一个 poker.out

既然它有读入文件，我们就应当给程序指定输入文件 poker.in，可以将题目的输入样例填写进去，运行，就发现 poker.out 有了答案

特别的，当程序读到 EOF 时，就会停止输入（相当于 ^Z）

如果是在一般的 Online Judge 提交上面的代码，会判为 WA，如果 OJ 没有要求指定输入输出文件名（一般没写就是没有），所以，我们应当删除 freopen 或者设为注释行

重要：文件名等信息必须与题目要求的一模一样！复制粘贴是一个好东西

Better

如果你为了在撰写代码时的快速，你可以只注释 输出文件 的 freopen，这样，在 输入文件 填写好测试数据之后，运行即可看到结果，相对于下面的方法快多了

• 都不注释，你需要每次看 输出文件，很烦
• 都注释，你需要每次粘贴样例，而且对于多组测试数据的试题更加繁琐

4 总结

$Thanks \space for \space reading.$

签到、活跃一览表

https://www.tropical-fish.cn/usr/uploads/2026/08/1084561839.pdf

总结

本月服务器发生的大事包括 china_man 事件，原因不公示，自己看着办

排序（Round 1）

-1 检查浏览器渲染数学公式情况

因为笔者发布文章当天，本博客仍然存在 Latex 可能无法渲染的情况，下面是一个 Latex 示范：

$x$

• 如果正常显示为衡水体 x，则代表读者的浏览器已经成功渲染了 Latex
• 如果显示为 带有美元符号的 x 即 $x$（已除去换行符），则代表读者的浏览器没有成功渲染 Latex，读者可能需要刷新重试，如果刷新多次仍然无法渲染，请尝试换一个浏览器/网络环境

0 框架

在本文中，我将重点介绍 排序，感谢 深入浅出程序设计竞赛（基础篇） 提供重要支持，本文有一部分的内容是基于本书修改

排序 是在 OI 算法中重要的一部分，虽然大部分场景下都可以用 sort 解决（限于 bits/stdc++.h），但是掌握具体的内容还是必不可少的，相对于初赛而言

$$ \begin{aligned} &\textbf{排序（Round 1）} \begin{cases} &\text{计数排序}\\ &\text{选择排序、冒泡排序、插入排序}\\ &\text{快速排序}\\ &\text{排序算法的应用}\\ &\text{汇总}\\ \end{cases} \end{aligned} $$

1 计数排序

【题目样本 1.1】P1271【模板】排序

题目描述

https://www.luogu.com.cn/problem/P1271

学校正在选举学生会成员，有 $n(n \leq 999)$ 名候选人，每名候选人编号分别从 $1$ 到 $n$, 现在收集到了 $m(m \leq 200000)$ 张选票，每张选票都写了一个候选人编号

现在想把这些堆积如山的选票按照投票数字从小到大排序。输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字，求出排序后的选票编号。例如，当有 $5$ 个候选人，$10$ 张选票分别是 $2、5、2、2、5、2、2、2、1、2$ 时，需要输出 1222222255

分析

这题本质有很多方法，但是由于是 计数排序，因此：

在投票区放上 $n$ 个投票箱，投票人支持谁就把票投入对应的投票箱中，投票后只须统计每个投票箱有几张选票，直接按照候选人编号取出来就可以完成排序操作

也不需要排序了

参考代码

#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,x,f[100005];
int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>x,f[x]++;
    for(i=1;i<=n;i++) for(j=1;j<=f[i];j++) cout<<i<<" ";
}

这里倡导数组从 $1$ 开始存

只需要开一个大小不小于 $n$ 的数组作为票箱，依次读入选票，然后将选票号数加到对应的票箱中，最后按照每个票箱的数量输出候选人编号即可

在这个过程中，甚至不需要存储下每一张选票

在完成输入并计算时，$f[]$ 状态如下

计数排序

这种排序方法被称为 计数排序

读入选票并统计的时间复杂度是 $O(m)$，输出选票的时间复杂度是 $O(m+n)$（第一层循环做 $n$ 次，$f[i]$ 至多为 $m$），空间复杂度是 $O(n)$（因为 $f[]$）

所以计数排序只能用于排序编号范围不是很大的数字，如果需要排序的数字要到 $10^9$，别说运行时间了，内存都无法存得下这么大的范围的数组

此外，如果希望将一些浮点数或者字符串进行排序，就没办法去建造合适的 投票箱，所以就不能使用这种算法了（把下标存成 $\text{浮点数} \times 10^\text{浮点数位数}$ 也是一个不错的选择）

也有改进方法，即 桶排序&基数排序，思路类似，但是复杂

无论是上段和计数，这些排序都是基于分类，并非比较

2 选择排序、冒泡排序、插入排序

【题目样本 2.1】数列排序

题目描述

输入 $n(n \leq 1000)$ 个数字 $a_i(a_i \leq 10^9)$, 将其从小到大排序后输出

分析

设有 $5$ 张纸牌，他们是 $4,1,9,5,1$，打牌时如何排序？

解法 1：选择排序

分析

求最大值：max()

求最小值：min()

求一序列最值：for(int i=1;i<n;i++) ma=max(ma,a[i]);，a[] 为序列，$n$ 为数量，$ma$ 存放最大值

核心思想：打擂台

如何联想到本题？

[collapse status="false" title="答案"]
从第一张牌到最后一张牌中找到最小的一张，放在最前面的位置；然后从第二张牌到最后一张牌中继续找到最小的一张，放到第二位……如此反复，就可以得到从小到大的序列
[/collapse]

这里有一张不错的图，来自 深入浅出，因此贴在这

若遇到大小相等的牌，continue

参考代码片段

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[i]) {
            int p = a[i];
            a[i] = a[j];
            a[j] = p;
        }
}

解法 2：冒泡排序

分析

如果尝试把最大的一项放在后面，虽然可以倒过来使用选择排序，但是可以试试别的办法

这里有一张图，来自 豆包，它打了一个类似于文章的比方，讲述了 选择排序 与 冒泡排序 的区别，前情提要是 现有扑克牌：9、5，要排成5、9

首先比较第 $1$ 张牌和第 $2$ 张牌，如果后面的牌比前面的牌小，那么就交换位置；然后比较第 $2$ 张牌和第 $3$ 张牌，同样保证第 $3$ 张牌要大于第 $2$ 张牌……依此类推， 直到比较最后一张牌和倒数第二张牌，这样就能保证最后面的一张牌是最大的一张了

继续进行新的一轮，利用上面一样的交换，但是需要注意的是，由于最后一张牌已经是手牌中最大的一张了，所以只需要比较到倒数第二张就行了

这一轮后结束后倒数第二张牌就是第二大的牌（当然，也有可能是并列最大)。经过 $n-1$ 轮排序后，就得到了有序的手牌

下图同样来自 深入浅出，用于理解

参考代码片段

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++)
        if (a[j] > a[j + 1]) {
            int p = a[j];
            a[j] = a[j + 1];
            a[j + 1] = p;
        }
}

[scode type="green"]
int p=a[j];a[j]=a[j+1];a[j+1]=p; 推荐用 swap(a[j],a[j+1]); 来取代，用于交换
[/scode]

解法 3：插入排序

分析

一种很形象的比喻

你在玩纸牌游戏的时候，从牌堆里面抽牌，抽到一张牌，放到你的手牌里，你是怎么保证手牌内的牌是有序的呢？

如果你能通过 Cloudflare 的人机验证，你应该会看看抓到牌的大小，再看看手牌，定位到合适的位置，插入

上面描述的过程，即 插入排序

1. 把手牌分为有序的和无序的两部分
2. 最开始有序的就只有一张牌，也就是第一张
3. 要把接下来的 无序区 中的一张牌（称为 待插牌 ）插入到 有序区 中，就是从有序区的末尾开始往前比较，如果待插牌比正在比较的牌小，那么就把有序区的正在比较的牌往后面放一格，然后继续往前面进行比较，直到待插牌遇到不大于自己的牌或者成为第一个为止
4. 这时，待插牌就可以填入留出来的缺口中。反复将无序区中的待插牌插入到有序区中，直到所有的牌都在有序区

同样的，这里有一张非常生动的图，供读者查阅

下面这是来自 深入浅出 的 插入排序 实现代码，进行了注释的补充

for(int i = 1; i < n; i++) {
    int now = a[i], j;          // 记录待插入元素，稍候会放进去
    for(j = i - 1; j >= 0; j--) // 一个很经典的模板：元素后移
        if(a[j] > now)
            a[j + 1] = a[j];    // 大于now的元素后移
        else
            break;
    a[j + 1] = now;             // 插入到正确位置
}

选择排序

为了加强读者的记忆，这里重新梳理一遍

解法 1 这种算法被称为 选择排序

从代码中可以看出有两重循环，读者可以自己计算一下已知 $n$ 的情况下一共需要比较的次数

选择排序的算法时间复杂度是 $O(n^2)$；由于只需要一个数组存下这些数字即可，空间复杂度是 $O(n)$

[collapse status="false" title="答案"]

$$ \frac{n(n-1)}{2} $$

[/collapse]

冒泡排序

解法 2 这种算法被称为 冒泡排序，在一轮中，最大的那张牌会一点一点地从左移动到右边，像冒泡泡一样

读者也可以计算一下排序的过程中需要进行几次比较

冒泡排序算法的时间复杂度也是 $O(n^2)$，空间复杂度也是 $O(n)$

冒泡排序相比于选择排序并没有实质性的改进

有一种冒泡排序的改良版叫作希尔排序，不是相邻位置的两个数字比较，而是比较距离更远的两个数字，虽然能略微优化一些复杂度，但依然不实用

猴子排序同样也是一种奇怪的办法

插入排序

这种算法叫作 插入排序

如果序列本来已经从小到大排序，那么每次无序区的待插牌都不会插进有序区中，而是紧贴在有序区后使有序区一直扩大，那么只需要 $n-1$ 次比较就可以完成算法流程

然而，如果序列是从大往小排序，那么每次插入都会将有序区中的所有牌往后面挪动一次，这样速度就非常慢了

讲时间复杂度一般会考虑最悲观的情况，所以插入排序的算法复杂度还是 $O(n^2)$，和选择排序、冒泡排序的复杂度一致，它们空间复杂度也是一样的

不过，如果能保证序列 基本有序 , 那么使用插入排序的效率可能会不错

不推荐在 Contest 中使用这些方法，耗时过久

笔者认为，学习这些是为了掌握原理，在第一轮比赛中获得较好的成绩，在历年的 OI 比赛中，有相当一部分的套题涉及了这个内容

3 快速排序

【题目样本 3.1】P1177 快速排序

题目描述

https://www.luogu.com.cn/problem/P1177

输入 $n(n \lt 10^5)$ 个数字 $a_i(a_i \lt 10^9)$，将其从小到大排序后输出

分析

这个数据量就很大了，插入排序、选择排序、冒泡排序都无法完成。这次将介绍在 OI 中最普遍使用的排序算法 快速排序，简称快排，顾名思义

快速排序说起来其实也挺简单的，但是需要读者能够理解递归

[collapse status="false" title="递归"]
递归就是函数调用自己。

你的快速排序就是递归：

void Qsort(int x, int y) {
    if (x >= y) return;          // 终止条件
    // ... 分区操作 ...
    Qsort(x, i);                 // 自己调用自己，排左边
    Qsort(i+2, y);               // 自己调用自己，排右边
}

执行过程：先把数组分成左右两部分，然后分别对两部分再调用同样的函数继续分，直到每部分只剩一个元素。

每次调用会占用栈内存，递归太深会栈溢出。你的代码最坏情况（已有序数据）递归深度达 $200000$，风险很大。

上述内容来自 Deepseek V4 Pro，请注意辨别
[/collapse]

算法的大致过程是对于一个无序序列，找到一个 哨兵数 ，将序列中所有比哨兵数小的数字都在哨兵数的左边，所有比哨兵数大的数字都在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止

怎么选择哨兵呢？随便选，可以是第一个，可以是中间那个，也可以在序列中随机选择

选择好哨兵，然后从序列左端开始寻找第一个比哨兵大的数字，从右边选择第一个比哨兵小的数字，然后交换这两个数；接着继续从左边找到比哨兵大的数字，右边比哨兵小的数字并交换……直到将序列分为两组，左边序列都不大于哨兵，右边序列都不小于哨兵，就可以分别对左边和右边进行排序了

下面同样还有一张生动的图，建议配合代码食用

参考代码

有多种办法可以实现，这是一种实现办法，也基于书本内容进行了适当的补充更多的办法请前往 排序的应用 这一章节

void qsort(int a[], int l, int r) { // a[] 传递数组
    int i = l, j = r, flag = a[(l + r) / 2], tmp;  // flag是基准值（哨兵）
    do {
        while (a[i] < flag) i++;   // 左指针右移，跳过比基准小的
        while (a[j] > flag) j--;   // 右指针左移，跳过比基准大的
        if (i <= j) {              // 找到一对需要交换的数
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;              // 继续移动指针
        }
    } while (i <= j);              // 两指针未交错就继续
    if (l < j) qsort(a, l, j);     // 递归排左半部分
    if (i < r) qsort(a, i, r);     // 递归排右半部分
}

快速排序

虽然在极端情况下（比如数列已经有序，且每次选择哨兵都会分出长度为 $1$ 的小段），快速排序的时间复杂度是 $O(n^2)$，但是如果随机选择哨兵，则很难出现这种情况

实际上，随机化快速排序的算法复杂度是 $O(n \log n)$，空间复杂度是 $O(n)$，而且不需要额外的辅助空间，所以是一种最为实用的排序算法

快速排序利用了 分治 思想，后面可能会出一篇 排序 这一专题的补充篇，介绍了更多的非基础排序

额外的，二分查找法 也利用了 分治思想，这个方法也可能会在未来单独出一篇专题进行讲解

【题目样本 3.2】 P1923 求第 $k$ 小的数

题目描述

https://www.luogu.com.cn/problem/P1923

输入 $n(n \lt 10^6 \text{ 且 } n \text{ 为奇数})$ 个数字 $a_i(a_i \lt 10^9)$，输出这些数字的第 $k$ 小的数，最小的数是第 $0$ 小

分析

如上 URL 中的 题目描述，如果你是真的要训练 快排，请 不要 使用 nth_element STL，当然我估计你也不知道

虽然可以直接排序，然后取数组中的第 $k$ 个作为答案进行输出，但是直接排序一遍的复杂度是 $O(n \log n)$，不适合这道头目，我们可以借鉴 快排 的 分治思想 把时间复杂度降至 $O(n)$

[collapse status="false" title="可以降低时间复杂度的原因"]

核心原因在于每次只需要递归处理一边，而不是两边

更多的：

1. 快速排序的分治过程
   每次选一个基准（pivot），将数组分成三部分：

   • 左边：所有元素 ≤ pivot
   • 中间：pivot 本身
   • 右边：所有元素 > pivot

   然后递归地对左右两边分别排序，所以总复杂度是 (O(n \log n))。

2. 求第 k 小数的优化
   在快速选择（Quick Select）中，不需要对两边都排序，只需要判断第 k 小的数在哪一边：

   • 如果 (k) 小于左边元素个数，就只在左边递归查找
   • 如果 (k) 等于左边元素个数 + 1，那么 pivot 就是答案
   • 否则，只在右边递归查找，并且调整 k 的值

3. 复杂度分析

   • 每次递归处理的数组大小大约是上一次的一半（平均情况）

   • 总比较次数：

     $$ n + \frac{n}{2} + \frac{n}{4} + \cdots = 2n $$

   • 因此平均时间复杂度是 (O(n))

上述内容来源 Deepseek V4 Pro 修改而得
[/collapse]

和快速排序的方法一样，任意取一个哨兵，将序列分为两部分，左边部分的所有数字都不大于右边的数字

• 如果 $k$ 在左边的范围，则递归求解左边的部分
• 如果在右边，则递归求解右边的部分
• 但是也有可能两边都不属于（比如说 $j=4$ 而 $i=6$ , 但刚好 $k=5$)，那么直接就可以给出答案

参考代码

这个代码是 深入浅出 提供的，由 Deepseek V4 Pro 和 笔者 改写而得

int ans = 0, k; // 记录答案，以及求第 k 小
void findkth(int a[], int l, int r) { // 引入数组的地址
    if(l == r) {
        ans = a[l]; // 区间长度为 1 时，记录答案
        return;
    }

    int i = l, j = r, flag = a[(l + r) / 2], tmp;
    do {
        while (a[i] < flag) i++; // 从左找比哨兵大的数
        while (a[j] > flag) j--; // 从右找比哨兵小的数
        if (i <= j) { // 交换
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;
        }
    } while (i <= j);

    if (k <= j) findkth(a, l, j); // 第 k 小的数字在左区间
    else if (i <= k) findkth(a, i, r); // 第 k 小的数字在右区间
    else findkth(a, j + 1, i - 1); // 第 k 小的数字既不在左区间，也不在右区间
}

尽管 此参考代码片段（快速选择） 相对于 快排（模板代码）类似，但是每次处理的区间长度期望下都会被减半，复杂度是线性的

快速排序 - 快速选择

这个概念是在书中没有的，是由 Deepseek V4 Pro 提出

它基于 快速排序 的分治思想，但并不是完整的排序算法，而是一种 选择算法 ——专门用来查找数组中第 $k$ 小（或第 $k$ 大）的元素

下面是一张表格，阐释了区别

所以，这种方法叫做 快速选择，也可以理解为"快速排序的简化版"或"基于快排分治的选择算法"

[collapse status="false" title="函数图像（可能有误）"]

这个部分由 Deepseek V4 Pro 与 豆包 提供，它们分别为这个部分 提供函数生成代码 和 提供函数图，在这里表示对他们最诚挚的感谢

但是目前看起来它们携手合作画出来的图有误，作为初二学生的笔者，无法验证这张图的真伪，所以这个问题抛给读者，抱歉

[/collapse]

4 排序的应用

这里提供了一些 排序 的拓展用法，在第二轮比赛时可能有用

【题目样本 4.1】P1059 [NOIP 2006 普及组] 明明的随机数

题目描述

https://www.luogu.com.cn/problem/P1059

给出 $N(N \lt 10^2)$ 个 $1 \sim 10^3$ 的数字，输出去重后剩余数字的个数以及去重排序后的序列

解法 1：计数排序

在拿到新的选票时发现投票箱中已经有这个选票了，就扔掉这张选票，保持每个票箱中最多只有一张票

最后将有票的票箱编号输出即可

这里要求先输出不同数字的个数，可以先枚举一遍票箱记录，输出剩余数字的个数，然后再枚举一遍票箱，输出序列

也可以创建一个新的数组，在枚举票箱的时候将有票的编号复制进新的数组中

解法 2：STL

当然也可以直接对这些数据进行排序，然后从小到大每个数字只输出一个

考虑数据规模，可以使用上面提到的所有排序方式

不过，这次介绍排序的 STL， 这样就不需要去亲自实现排序算法了

关于 STL，后面可能会出一个专门的专题，STL = Standard Template Library（标准模板库）

有了这个就不用自己手搓了

排序 STL 1：sort

分析

std::sort 被定义于 algorithm 头文件中，因此，你在使用前需要先导入这个头文件，为了方便笔者，笔者会尽可能地在后文省略较多的不影响理解的内容

sort 的基本用法如下

// 形式1：默认升序排序
sort(起始迭代器, 结束迭代器);

// 形式2：自定义比较规则
sort(起始迭代器, 结束迭代器, 比较函数/仿函数/Lambda); // 比较函数即 cmp 用的较多

一个例子，sort(a,a+n,cmp)，对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行排序，cmp 是指自定义排序函数，如果是将数组 $a[]$ 从小到大排序，那么这一项可以省略

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int const MAXN = 1010;
int a[MAXN], ans[MAXN], n, cnt = 0, tmp = -1;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
    if (a[i] != tmp) ans[cnt++] = a[i]; /* 当前的和上一个不同才复制到新数组 */
    tmp = a[i];
    }
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) cout << ans[i] << ' ';
    return 0;
}

sort

这里，sort 的时间复杂度是 $O(n \log n)$

如果要对数组 $a[1]$ 到 $a[n]$ 排序，就要用 sort(a+1, a+n+1)

那么，如果要求从大到小排序，只需要定义一个名字是 cmp 的自定义比较函数即可，这个函数的输入是两个元素，如果第一个在第二个之前，则返回 true, 否则返回 false。代码如下：

bool cmp(int q,int h){ // q 前 h 后
    return q>h;
}

排序 STL 2：unique

分析

std::unqiue 同样被定义于 algorithm 头文件中

unique(a,a+n)：对 $a[]$ 数组从 $a[0]$ 到 $a[n-1]$ 进行去重，要求 $a[]$ 数组已经有序，返回去重后最后一个元素对应的指针

如果使用 unique, 就可以不用 ans 新数组了，可以直接获得去重后的数组和最终元素个数

参考代码

sort(a,a+n);
cnt=unique(a,a+n)-a; // 剩下的数总数
cout<<cnt<<"\n";
for(int i=0;i<cnt;i++) cout<<a[i]<<" ";

【题目样本 4.2】P1093 [NOIP 2007 普及组] 奖学金

题目描述

https://www.luogu.com.cn/problem/P1093

有 $n$（$n \le 300$）名学生的语文、数学、英语成绩，这些学生的学号依次是从 $1$ 到 $n$。需要对这些学生进行排序。如果总分相同，则语文分数高者名次靠前；如果语文成绩还相同，学号小者靠前。输出排名前 $5$ 的学生学号和总分

解法 1：STL

分析

定义一个 struct 结构体，命名为 student 存储学生各项信息，使用 sort 附带 cmp 比较函数进行排序，最后输出排序结果，下面是排序优先级

1. 总分，高者优先
2. 语文，高者优先
3. 学好，小者优先

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

int const MAXN = 310;
int n;

struct student {
    int id, chinese, total;
} a[MAXN];

int cmp(student a, student b) {
    if (a.total != b.total) return a.total > b.total;      // 总分先定胜负
    if (a.chinese != b.chinese) return a.chinese > b.chinese; // 然后比语文
    return a.id < b.id;                                    // 最后比学号
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int math, english;
        cin >> a[i].chinese >> math >> english;
        a[i].total = a[i].chinese + math + english;
        a[i].id = i + 1;
    }

    sort(a, a + n, cmp);

    for (int i = 0; i < 5; i++) {
        cout << a[i].id << " " << a[i].total << endl;
    }

    return 0;
}

解法 2：选择排序

分析

时间复杂度 $O(kn)$，此题 $k=5$，即 $O(n)$

解法 3：插入排序

分析

维护排名前 $5$ 数组作为比较对象（手牌）

时间复杂度 $O(n)$，运行效率不高

【题目样本 4.3】P1781 宇宙总统

题目描述

https://www.luogu.com.cn/problem/P1781

共有 ( n )（( n \le 20 )）个非凡拔尖的人竞选总统，现在票数已经统计完毕，请算出谁能够当上总统。第一行输出候选人编号，第二行输出选票数量。票数可能很大，最大会有 100 位

解法 1：计数排序

分析

由于本题只需要求出最大的那一个数字，所以用“打擂台”法

但是数字很大，没办法直接存下来（long long 也存不下）

但是需要高精度，不考虑单开一个话题

解法 2：结构体

分析

存进字符串。不过不能直接对这些字符串进行大小比较，因为字符串比较是比较字典序（第一位小的在前面，如果相同则比较第二位，以此类推），例如 $10000$ 小于 $1200$ 小于 $200$

得手搓 cmp

参考代码

struct node {
    string x;    // 票数
    int num;     // 候选人编号
} s[MAXN];

bool cmp(node a, node b) {
    if (a.x.length() != b.x.length()) {
        return a.x.length() > b.x.length(); // a 比 b 位数多时 a 在前面
    }
    return a.x > b.x; // 位数相同，但 a 字典序排列比 b 大
}

5 汇总

练习

笔者为读者提供了一些洛谷上没有的题目，供练习

• 计数排序
• 选择排序
• 冒泡排序
• 插入排序
• 快速排序

C++ 常用排序算法一览表

额外的，这里有一张特别大的表格，供读者查阅

[collapse status="false" title="C++ 常用排序算法一览表（无特点）"]

[/collapse]

C++ STL 中的排序一览表

同时，这里还有一张关于 STL 的表

关于学会说话【第二弹】

题

今天我被我的父母屌了，但是原因耐人寻味：你说话太直、不会来事、别人不喜欢你，仅此而已

这应该是很普遍的现象了，在绝大部分 $80\text{后} \sim 90\text{后}$ 的思想里，会说话=让所有人舒服、让所有人满意、让所有人喜欢

但冷静下来我想说一句大实话，也是这篇第二弹的核心：这根本不是会说话，这是教人讨好、教人卑微、教人丢掉自我

你以为你好了，说难听点，即拍马屁，孟子说得好：“此之谓失其本心。”——《鱼我所欲也》【《《孟子・告子上》】

我觉得我不是很玩梗吧，我反而觉得我很喜欢讲大白话，说话的意义，不是令他人开心

会说法=高情商？

这是 $80\text{后} \sim 90\text{后}$ 的观点之一，我认为是错误的

他们认为，一个人会不会说话，标准极其简单，即有没有人不高兴、有没有人吐槽、有没有人不喜欢你，这样的判断类似于郑振铎《猫》

[collapse status="false" title="郑振铎《猫》"]
我家养了好几次猫，结局总是失踪或死亡。三妹是最喜欢猫的，她常在课后回家时，逗着猫玩。有一次，从隔壁要了一只新生的猫来。花白的毛，很活泼，如带着泥土的白雪球似的，常在廊前太阳光里滚来滚去。三妹常常取了一条红带，或一根绳子，在它面前来回地拖摇着，它便扑过来抢，又扑过去抢。我坐在藤椅上看着他们，可以微笑着消耗过一二小时的光阴，那时太阳光暖暖地照着，心上感着生命的新鲜与快乐。后来这只猫不知怎地忽然消瘦了，也不肯吃东西，光泽的毛也污涩了，终日躺在厅上的椅下，不肯出来。三妹想着种种方法逗它，它都不理会。我们都很替它忧郁。三妹特地买了一个很小很小的铜铃，用红绫带穿了，挂在它颈下，但只显得不相称，它只是毫无生意的，懒惰的，郁闷地躺着。有一天中午，我从编译所回来，三妹很难过地说道：“哥哥，小猫死了！”

我心里也感着一缕的酸辛，可怜这两月来相伴的小侣！当时只得安慰着三妹道：“不要紧，我再向别处要一只来给你。”

隔了几天，二妹从虹口舅舅家里回来。她道，舅舅那里有三四只小猫，很有趣，正要送给人家。三妹便怂恿着她去拿一只来。礼拜天，母亲回来了，却带了一只浑身黄色的小猫同来。立刻三妹一部分的注意，又被这只黄色小猫吸引去了。这只小猫较第一只更有趣，更活泼。它在园中乱跑，又会爬树，有时蝴蝶安详地飞过时，它也会扑过去捉。它似乎太活泼了，一点也不怕生人，有时由树上跃到墙上，又跑到街上，在那里晒太阳。我们都很为它提心吊胆，一天都要“小猫呢？小猫呢？”地查问好几次。每次总要寻找了一回，方才寻到。三妹常指它笑着骂道：“你这小猫呀，要被乞丐捉去后才不会乱跑呢！”我回家吃中饭，总看见它坐在铁门外边，一见我进门，便飞也似地跑进去了。饭后的娱乐，是看它在爬树。隐身在阳光隐约里的绿叶中，好像在等待着要捉捕什么似的。把它抱了下来。一放手，又极快地爬上去了。过了二三个月，它会捉鼠了。有一次，居然捉到一只很肥大的鼠，自此，夜间便不再听见讨厌的吱吱的声了。

某一日清晨，我起床来，披了衣下楼，没有看见小猫，在小园里找了一遍，也不见。心里便有些亡失的预警。

“三妹，小猫呢？”

她慌忙地跑下楼来，答道：“我刚才也寻了一遍，没有看见。”

家里的人都忙乱的在寻找，但终于不见。

李嫂道：“我一早起来开门，还见它在厅上。烧饭时，才不见了它。”

大家都不高兴，好像亡失了一个亲爱的同伴，连向来不大喜欢它的张婶也说：“可惜，可惜，这样好的一只小猫。”

我心里还有一线希望，以为它偶然跑到远处去，也许会认得归途的。

过了一二个星期，它始终没有回来。大家都以为它一定是被人家捉去，或是死了。三妹很不高兴的，咕噜着道：“他们看见了，为什么不出来阻止？他们明晓得它是我家的！”

我也怅然地，愤恨地，在诅骂着那个不知名的夺去我们所爱的东西的人。

自此，我家好久不养猫。

冬天的早晨，门口蜷伏着一只很可怜的小猫，毛色是花白，但并不好看，又很瘦。它伏着不去。我们如不取来留养，至少也要为冬寒与饥饿所杀。张婶把它拾了进来，每天给它饭吃。但大家都不大喜欢它，它不活泼，也不像别的小猫之喜欢顽游，好像是具着天生的忧郁性似的，连三妹那样爱猫的，对于它也不加注意。如此的，过了几个月，它在我家仍是一只若有若无的动物。它渐渐的肥胖了，但仍不活泼。大家在廊前晒太阳闲谈着时，它也常来蜷伏在母亲或三妹的足下。三妹有时也逗着它玩，但并没有对于前几只小猫那样感兴趣。有一天，它因夜里冷，钻到火炉底下去，毛被烧脱了好几块，更觉得难看了。

春天来了，它成了一只壮猫了，却仍不改它的忧郁性，也不去捉鼠，终日懒惰的伏着，吃得胖胖的。

这时，妻买了一对黄色的芙蓉鸟来，挂在廊前，叫得很好听。妻常常叮嘱着张婶换水，加鸟粮，洗刷笼子。那只花白猫对于这一对黄鸟，似乎也特别注意，常常跳在桌上，对鸟笼凝望着。

妻道：“张婶，留心猫，它会吃鸟呢。”

张婶便跑来把猫捉了去，隔一会，它又跳上桌子对鸟笼凝望着了。

一天，我下楼时，听见张婶在叫道：“鸟死了一只，一条腿被咬去了，笼板上都是血。是什么东西把它咬死的？”

我匆匆跑下去看，果然一只鸟是死了，羽毛松散着，好像它曾与它的敌人挣扎了许久。

我很愤怒，叫道：“一定是猫，一定是猫！”于是立刻便去找它。

妻听见了，也匆匆地跑下来，看了死鸟，很难过，便道：“不是这猫咬死的还有谁？它常常对鸟笼望着，我早就叫张婶要小心了。张婶！你为什么不小心？”

张婶默默无言，不能有什么话来辩护。

于是猫的罪状证实了。大家都去找这可厌的猫，想给它以一顿惩戒。找了半天，却没找到。我以为它真是“畏罪潜逃”了。

三妹在楼上叫道：“猫在这里了。”

它躺在露台板上晒太阳，态度很安详，嘴里好像还在吃着什么。我想，它一定是在吃着这可怜的鸟的腿了，一时怒气冲天，拿起楼门旁倚着的一根木棒，追过去打了一下。它很悲楚地叫了一声，便逃到屋瓦上了。

我心里还愤愤的，以为惩戒得还没有快意。

隔了几天，李嫂在楼下叫道：“猫，猫！又来吃鸟了！”同时我看见一只黑猫飞快地逃过露台，嘴里衔着一只黄鸟。我开始觉得我是错了！

我心里十分地难过，真的，我的良心受伤了，我没有判断明白，便妄下断语，冤枉了一只不能说话辩诉的动物。想到它的无抵抗的逃避，益使我感到我的暴怒，我的虐待，都是针，刺我良心的针！

我很想补救我的过失，但它是不能说话的，我将怎样地对它表白我的误解呢？

两个月后，我们的猫忽然死在邻家的屋脊上。我对于它的亡失，比以前的两只猫的亡失，更难过得多。

我永无改正我的过失的机会了！

自此，我家永不养猫。
[/collapse]

虽然感觉直接给读者丢下这么长的文章也挺奇怪的，想看就看，不看拉倒——卤煮刘

说白了，只要有人对我有意见、只要场面不够和谐、只要我没有顺着别人的话说，就是我不会说话、就是我情商低、就是我不懂事

但是这个逻辑本身就是感觉很荒谬，漏洞百出

下面用标签来生动的表面

[scode type="green"]A说老板漂亮，你说漂亮[/scode]

[scode type="red"]A说老板漂亮，你说不漂亮[/scode]

老板本来就不漂亮，你说漂亮，骗了他人，你骗了自己了吗，骗下去，类似于汉斯・克里斯蒂安・安徒生（丹麦）《皇帝的新装》

[collapse status="false" title="汉斯・克里斯蒂安・安徒生（丹麦）《皇帝的新装》"]
许多年前，有一个皇帝，为了穿得漂亮，不惜把所有的钱都花掉。他既不关心他的军队，也不喜欢去看戏，也不喜欢乘着马车去游公园——除非是为了去炫耀一下他的新衣服。他每一天每一点钟都要换一套衣服。人们提到他，总是说：“皇上在更衣室里。”

有一天，他的京城来了两个骗子，自称是织工，说能织出人间最美丽的布。这种布不仅色彩和图案都分外美观，而且缝出来的衣服还有一种奇怪的特性：任何不称职的或者愚蠢得不可救药的人，都看不见这衣服。

“那真是理想的衣服！”皇帝心里想，“我穿了这样的衣服，就可以看出在我的王国里哪些人不称职；我就可以辨别出哪些是聪明人，哪些是傻子。是的，我要叫他们马上为我织出这样的布来！”于是他付了许多钱给这两个骗子，好让他们马上开始工作。

他们摆出两架织布机，装作是在工作的样子，可是他们的织布机上连一点东西的影子也没有。他们急迫地请求发给他们一些最细的生丝和最好的金子。他们把这些东西都装进自己的腰包，只在那两架空织布机上忙忙碌碌，一直搞到深夜。

“我倒很想知道衣料究竟织得怎样了。”皇帝想。不过，想起凡是愚蠢或不称职的人就看不见这布，心里的确感到不大自然。他相信自己是无须害怕的，但仍然觉得先派一个人去看看工作的进展情形比较妥当。全城的人都听说这织品有一种多么神奇的力量，所以大家也都渴望借这个机会测验一下：他们的邻人究竟有多么笨，或者有多么傻。

“我要派我诚实的老大臣到织工那儿去。”皇帝想，“他最能看出这布料是什么样子，因为他很有理智，就称职这点说，谁也不及他。”

这位善良的老大臣来到那两个骗子的屋子里，看见他们正在空织布机上忙碌地工作。

“愿上帝可怜我吧！”老大臣想，他把眼睛睁得特别大，“我什么东西也没有看见！”但是他没敢把这句话说出口来。

那两个骗子请他走近一点，同时指着那两架空织布机问他花纹是不是很美丽，色彩是不是很漂亮。可怜的老大臣眼睛越睁越大，仍然看不见什么东西，因为的确没有东西。

“我的老天爷！”他想，“难道我是愚蠢的吗？我从来没有怀疑过自己。这一点决不能让任何人知道。难道我是不称职的？不成！我决不能让人知道我看不见布料。”

“哎，您一点意见也没有吗？”一个正在织布的骗子说。

“哎呀，美极了！真是美极了！”老大臣一边说，一边从他的眼镜里仔细地看，“多么美的花纹！多么美的色彩！是的，我将要呈报皇上，我对这布料非常满意。”

“嗯，我们听了非常高兴。”两个织工齐声说。于是他们就把色彩和稀有的花纹描述了一番，还加上些名词。老大臣注意地听着，以便回到皇上那儿可以照样背出来。事实上他也就这样做了。

这两个骗子又要了更多的金子，更多的生丝，说是为了织布的需要。他们把这些东西全装进了腰包。

过了不久，皇帝又派了另外一位诚实的官员去看工作进行的情况。这位官员的运气并不比头一位大臣好：他看了又看，但是那两架空织布机上什么也没有，他什么东西也看不出来。

“你看这段布美不美？”两个骗子问。他们指着，描述着一些美丽的花纹——事实上它们并不存在。

“我并不愚蠢呀！”这位官员想，“这大概是我不配有现在这样好的官职吧。这也真够滑稽，但是我决不能让人看出来。”他就把他完全没看见的布称赞了一番，同时保证说，他对这些美丽的色彩和巧妙的花纹感到很满意。“是的，那真是太美了！”他对皇帝说。

城里所有的人都在谈论着这美丽的布料。

皇帝很想亲自去看一次。他选了一群特别圈定的随员——其中包括已经去看过的那两位诚实的大臣。他就到那两个狡猾的骗子那里。这两个家伙正在以全副精神织布，但是一根丝的影子也看不见。

“您看这布华丽不华丽？”那两位诚实的官员说，“陛下请看：多么美的花纹！多么美的色彩！”他们指着那架空织布机，他们相信别人一定看得见布料。

“这是怎么一回事呢？”皇帝心里想，“我什么也没有看见！这可骇人听闻了。难道我是一个愚蠢的人吗？难道我不够资格当皇帝吗？这可是最可怕的事情。”

“哎呀，真是美极了！”皇帝说，“我十分满意！”

于是他点头表示满意。他装作很仔细地看着织机的样子，因为他不愿意说出他什么也没有看见。跟他来的全体随员也仔细地看了又看，可是他们也没有看出更多的东西。不过，他们也照着皇帝的话说：“啊，真是美极了！”他们建议皇帝用这种新奇的、美丽的布料做成衣服，穿上这衣服亲自去参加快要举行的游行大典。“真美丽！真精致！真是好极了！”每人都随声附和着。每人都有说不出的快乐。皇帝赐给骗子每人一个爵士的头衔和一枚可以挂在纽扣洞上的勋章；并且还封他们为“御聘织师”。

第二天早晨游行大典就要举行了。在头天晚上，这两个骗子整夜不睡，点起十六支蜡烛。你可以看到他们是在赶夜工，要完成皇帝的新衣。他们装作把布料从织机上取下来。他们用两把大剪刀在空中裁了一阵子，同时又用没有穿线的针缝了一通。最后，他们齐声说：“请看！新衣服缝好了！”

皇帝带着他的一群最高贵的骑士们亲自到来了。这两个骗子每人举起一只手，好像他们拿着一件什么东西似的。他们说：“请看吧，这是裤子，这是袍子！这是外衣！”“这衣服轻柔得像蜘蛛网一样，穿的人会觉得好像身上没有什么东西似的，这也正是这衣服的奇妙之处。”

“一点也不错。”所有的骑士都说。可是他们什么也看不见，因为什么东西也没有。

“现在请皇上脱下衣服，”两个骗子说，“好让我们在这个大镜子面前为您换上新衣。”

皇帝把他所有的衣服都脱下来。两个骗子装作一件一件地把他们刚才缝好的新衣服交给他。他们在他的腰周围弄了一阵子，好像是为他系上一件什么东西似的；这就是后裙。皇上在镜子面前转了转身子，扭了扭腰肢。

“上帝，这衣服多么合身啊！裁得多么好看啊！”大家都说，“多么美的花纹！多么美的色彩！这真是一套贵重的衣服！”

“对！我已经穿好了，”皇帝说，“这衣服合我的身吗？”于是他又在镜子面前把身子转动了一下，因为他要使大家觉得他在认真地观看他美丽的新装。

那些托后裙的内臣都把手在地上东摸西摸，好像他们正在拾取衣裙似的。他们开步走，手中托着空气——他们不敢让人瞧出他们实在什么东西也没有看见。

这样，皇帝就在那个富丽的华盖下游行起来了。站在街上和窗子里的人都说：“乖乖！皇上的新装真是漂亮！他上衣下面的后裙是多么美丽！这件衣服真合他的身材！”谁也不愿意让人知道自己什么也看不见，因为这样就会显出自己不称职，或是太愚蠢。皇帝所有的衣服从来没有获得过这样的称赞。

“可是他什么衣服也没有穿啊！”一个小孩子最后叫了出来。

“上帝哟，你听这个天真的声音！”爸爸说。于是大家把这孩子讲的话私下里低声地传播开来。

“他并没有穿什么衣服！有一个小孩子说他并没有穿什么衣服啊！”

“他实在没有穿什么衣服啊！”最后所有的老百姓都说。皇帝有点儿发抖，因为他似乎觉得老百姓们所讲的话是真的。不过他自己心里却这样想：“我必须把这游行大典举行完毕。”因此他摆出一副更骄傲的神气。他的内臣们跟在他后面走，手中托着一条并不存在的后裙。
[/collapse]

他们一辈子都没搞懂：让别人喜欢，是无底线迁就的结果，不是好好说话的标准

[collapse status="false" title="迁就（GenAI）"]

1. 退让、包容，顺着别人的意愿，委屈自己满足对方（最常用）
   指明明自己不舒服、不认同，却为了和睦，放下自身想法去迎合他人。
   例句：家长总让我事事迁就别人，可一味迁就只会丢掉自己的底线。
2. 勉强凑合、将就
   物品、条件达不到理想标准，勉强使用。
   例句：这间房子太小，只能暂时迁就着住。

近义词、反义词

• 近义词：将就、包容、迎合、忍让
• 反义词：抗拒、固执、较真、强硬
  [/collapse]

可笑吗？

如果你说话面面俱到、不敢反驳、不敢拒绝、永远顺着别人，确实没人会讨厌你，但你也永远活得憋屈、永远没有立场、永远被人拿捏

你为了高情商，人家说什么，你就说什么，无论对错，误入歧途

这样的会说话，本质就是牺牲自我，转为顺从，说难听点，这不是能力，而是软弱

“说话要让人喜欢” 是毒鸡汤

解释标题

[collapse status="false" title="毒鸡汤（GenAI）"]
毒鸡汤
定义
表面听起来有道理、温柔治愈，内核逻辑扭曲、误导人、损害自身立场与心态的句子、观点。看似劝人变好，实则压抑自我、一味妥协，只会带来内耗。

核心特征

1. 片面化，只讲忍让、讨好，不提底线与自我；
2. 颠倒因果，把委屈自己当成成熟、懂事；
3. 弱化矛盾，要求单方面妥协，忽视互相尊重。

近义词
心灵毒汤、畸形情商论、讨好型说教
[/collapse]

你不可能被所有人接受

家长总幻想一种完美状态：说话圆滑、不得罪人、人人夸赞

你觉得，现实中，有这种状态吗？

[scode type="red"]你讲原则，想占便宜的人不喜欢你[/scode]

[scode type="red"]你讲道理，蛮不讲理的人不喜欢你[/scode]

[scode type="red"]你有主见，随波逐流的人不喜欢你[/scode]

[scode type="red"]你敢拒绝，自私自利的人更不喜欢你[/scode]

何曾不是社会现状？

社会从来不是完美的，只是你没遇到罢了

长辈总是说自己看过星星，摘过月亮，为什么会下定这种结论？

鲁迅《朝花夕拾》 给出了完美的答案

但凡你有底线、有思想、不讨好，就一定会有人不喜欢你

如果你为了别人的喜欢去改变你自己说法的方式，好似正方形变圆，你的边界呢？你的态度呢？你的独立呢？你只会因别人的改变而改变，你就是一个植物

追求被喜欢与拥有底气不可同时而立

[collapse status="false" title="《韩非子・难一》自相矛盾"]
楚人有鬻盾与矛者，誉之曰：“吾盾之坚，物莫能陷也。” 又誉其矛曰：“吾矛之利，于物无不陷也。” 或曰：“以子之矛陷子之盾，何如？” 其人弗能应也。夫不可陷之盾与无不陷之矛，不可同世而立。
[/collapse]

你说话唯唯诺诺，只为征求别人的喜欢，这年头 AI 短剧还少吗，惹不起大人物，就改变自己，你明明没错，却为了他人而习惯性的道歉，长辈一句句的丢了你的面子，你的根源一直都是从小被灌输的封建思想：别得罪人，要让别人喜欢

于是：

• 遇到不公不敢说
• 遇到不合理要求不敢拒绝
• 被误解不敢辩解
• 有不同想法不敢表达

你就是被思想禁锢了，我们生活在现代，已经不是近代中国了，何时能改变这种封建思想呢？

你以为你在学好好说话，其实你在习惯性委屈自己换取别人的善意，这不是失去自我的一种表现吗？

你从小觉得，你是一个独立的个体，可是在职场的环境下，你还是一个个体吗？小时没有零花钱，成人时你为了讨好他人而失去自我的本性

你，为了这些，值得吗？

仅仅是为了钱？

你能活出自己吗？

和朋友交往也差不多，有时确实为了对方打钱而不要脸

不对，有点扯了

但现实最讽刺的是：越想让人喜欢，越容易被人轻视你的迁就会变成理所当然，你的退让会变成软弱可欺

分清主次

让人喜欢是你的目的吗？

长辈把顺序完全搞反了：他们以为刻意讨好、刻意圆滑、刻意照顾所有人情绪，就能收获好人缘。

真实顺序是：你说话得体、有分寸、有立场、有逻辑、待人真诚，别人自然会尊重你、认可你，甚至喜欢你

我们亲爱的道法教师提到了“交友要讲原则”，你，讲原则了吗？你被剥削了！哈哈哈哈哈哈！

一旦你把“让人喜欢”当成说话的目标，你的表达就会变形、你的态度就会卑微、你的底线就会爆炸

怕你妈

人家明明是错的，你就大胆指出来，你就对着人家的鼻子说回去，怕什么

做真正的自己

首先，我不得不承认我国文不好，但是我不承认我不会说话

诚实、真实、实在

诚实

我可以礼貌待人、尊重他人、好好沟通，但我不会为了让你开心，就违背自己的想法、认可错误的观点、接受不合理的要求，尽管你是特朗普

真实

说话的第一意义，是让自己被理解、让诉求被表达、让边界被看见，不是维护表面的和谐

有些场面看似尴尬、有些人听着不舒服，不是我不会说话，是真话本来就不好听，原则本来就不讨喜

善用反问，但有时不能用反问

实在

好好说话是我的教养，不是我取悦别人的工具

我待人温和、有理有据、分寸得当，这是我做人的体面。至于你喜不喜欢、满不满意、舒不舒服，那是你的情绪，不是我的责任，谁他妈管你怎么样

因人而异

你被 PUA 了？？？

莫得关系

很多时候，不是你不会说话，是你不肯讨好、不肯妥协、不肯虚伪，所以显得“不合群”

以前的年代，有点战争，他们为了和平，这样做

然而，现在是什么年代了

玫瑰不用长高，恋者自会弯腰

你可以好，但是你不能讨好；你可以说话，但是你不能说好话

NOIP 信息学：搜索及其优化 完整知识点文档

https://www.tropical-fish.cn/usr/uploads/2026/07/3625185257.pptx

一、前言：搜索算法定位

1. 算法解题优先级：优先数学推导、递推、贪心、DP；无高效数学解法时，使用搜索。
2. 搜索特点：通用性强、适用范围广；纯暴力搜索效率极低，必须配合各类优化才能通过大数据。
3. 基础搜索分类：穷举、深度优先搜索（DFS）、广度优先搜索（BFS）。

二、核心基础概念

2.1 状态

• 定义：搜索的最小单元，决定搜索效率、思维难度、代码复杂度。
• 设计要点：靠刷题积累经验，状态定义优劣直接决定代码能否过时限。

2.2 搜索树

所有搜索过程均可抽象为一棵搜索树：

• DFS：纵向优先遍历整棵树，适合求全部可行解、构造方案；缺点是深度过大易栈溢出。
• BFS：逐层横向遍历，天然适合求最短/最小代价最优解；自带分层，第一次到达目标即为最优。

三、基础搜索算法实现

3.1 深度优先搜索 DFS（回溯）

通用模板

void dfs(int dep, [其他状态参数])
{
    // 边界：到达目标状态
    if(当前为目标状态){
        记录答案/输出/计数;
        return;
    }
    // 枚举所有可拓展状态
    for(枚举所有下一步可能){
        保存现场（修改全局/局部状态）;
        if(该拓展合法) dfs(dep + 1, 新参数);
        恢复现场（回溯，还原状态）;
    }
}

特点

1. 使用系统栈/手动栈，递归实现；
2. 不自动保证最优，需手动记录最优值；
3. 深度过大时栈溢出（如POJ3278裸DFS会爆栈）。

3.2 广度优先搜索 BFS（队列）

通用模板

初始状态入队;
while(队列不为空){
    取出队首元素，队首出队;
    if(当前是目标状态){输出答案; return;}
    // 拓展所有子状态
    for(所有拓展方向){
        if(状态未访问 && 拓展合法){
            标记已访问（判重）;
            新状态入队;
        }
    }
}

特点

1. 借助队列实现分层遍历；
2. 第一次抵达终点一定是最小步数/最小代价，无需额外比较最优；
3. 必须判重，否则重复入队无限循环。

四、经典入门例题：POJ3278 抓住那头牛

题目简述

农夫在数轴N，牛在K，三种移动方式，每次耗时1分钟：

1. $X \to X-1$
2. $X \to X+1$
3. $X \to 2X$
   求到达牛位置的最少时间。样例输入5 17，输出4。

算法选择分析

1. 裸DFS：搜索树深度极大，系统栈溢出，且无法保证最优；
2. BFS最优：分层遍历，首次走到K即为最小步数，是本题标准解法。

五、NOIP真题案例详解

5.1 NOIP2017提高组Day2 T1 奶酪（连通性DFS）

题意

无限大奶酪，高度$h$，内部有等半径球形空洞；空洞相交/相切可互通；空洞接触下表面$z=0$可进入，接触上表面$z=h$可逃出。判断老鼠能否从底部走到顶部。

核心思路

1. 模型转化：无向图连通性，每个空洞是节点；

2. 连通条件：两球心距离 $\le 2r$；

   • 距离公式避免sqrt防止精度丢失：平方比较
     $$(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2 \le (2r)^2$$
   • 全部变量使用long long，防止大数溢出；
3. 起点集合：$z \le r$ 的空洞（接触下表面）；
4. 终止条件：搜到任意满足 $z \ge h-r$ 的空洞（接触上表面）；

核心代码框架

void dfs(int id){
    vis[id] = true;
    // 判断是否连通上表面
    if(hole[id].z + r >= h) flag = true;
    for(int i = 1; i <= n; i++){
        if(!vis[i] && 两球连通(id,i)) dfs(i);
    }
}

5.2 NOIP2014提高组Day2 T2 寻找道路（反向DFS+BFS最短路）

题意

有向图，边权均为1，求起点s到终点t的最短路径，约束：路径上每个点的所有出边指向的点，都能间接到达终点t。

分步解法

1. 建两张图：正向图（原图）、反向图（所有边反转）；
2. 反向图DFS：从终点t出发，标记所有能到达t的点vis1[]；
3. 筛选合法点：一个点u合法当且仅当u所有出边指向的v都满足vis1[v]=true；
4. 正向图BFS：仅走合法点，求s到t最短路；

数据注意

$n\le10^4,m\le2\times10^5$，稀疏图用vector邻接表；输入量大，禁用cin，改用scanf防超时。

5.3 NOIP2017普及组T3 棋盘（带状态记忆化DFS）

题意

$m\times m$棋盘，格子红/黄/无色；四向行走，异色花费1金币；可花2金币临时将无色格子染色，魔法不可连续释放。求左上角到右下角最小花费。

状态设计（三维记忆化）

f[x][y][can]：坐标$(x,y)$，can=0/1代表当前能否使用魔法，存储到达该状态最小金币；

状态转移

1. 下一格有颜色：根据颜色是否相同累加金币，魔法重置为可用；
2. 下一格无色：仅当魔法可用时，花费2金币，魔法置为不可用；

优化梯度

• 裸DFS：40分；
• 最优性剪枝：60分；
• 记忆化剪枝（记录每个状态最小代价）：100分。

5.4 NOIP2009提高组T4 靶形数独（DFS+搜索顺序优化）

题意

9×9数独，每个格子有分值，数字×格子分值总和最大化；无解输出-1。

优化梯度

1. 暴力DFS顺序填格：40分；
2. 预处理空白格、行/列/九宫格数字判重：75分；

3. 最优优化（100分）：搜索顺序优化
   每次优先选择可填数字最少的空白格填充，大幅剪枝无效分支；

   • 若某格无合法数字：可行性剪枝，直接回溯；
   • 若只剩1种数字：直接填充，减少循环。

六、DFS核心优化：剪枝

6.1 可行性剪枝

当前状态已经不满足题目约束，后续无论怎么走都无解，直接回溯。
例：数独格子无可用数字、数轴坐标超出0~100000范围。

6.2 最优性剪枝

全局记录当前已知最优解；若当前已消耗代价 ≥ 最优解，后续路径只会更差，直接返回。
例：抓牛DFS记录当前最小步数，当前步数超过最优则剪枝。

6.3 记忆化剪枝（全局最优剪枝）

记录每个状态到达时的最小代价；再次走到同一状态时，若当前花费 ≥ 记录值，直接剪枝；否则更新记录。
适用：棋盘、最短代价类搜索问题。

6.4 搜索顺序优化

人为调整拓展节点的先后顺序，优先搜索分支少、更容易出解的路径，提前触发剪枝。
代表例题：靶形数独（优先填可选数字最少的格子）。

七、高阶搜索优化算法

7.1 迭代加深搜索 IDDFS

1. 思路：限制DFS最大深度，从小到大逐层放宽深度限制；
2. 优势：兼具DFS空间小、BFS保证最优的特点；解决深搜栈溢出问题；
3. 适用：求最小步数、深度不确定的最优解问题。

7.2 双向BFS

1. 思路：起点BFS、终点BFS同时向外拓展，两边相遇即得到最优解；
2. 优势：搜索范围指数级缩小，大幅降低时间复杂度；
3. 适用：起点终点明确、状态空间巨大的最短路问题（抓牛、迷宫最短路径）。

7.3 BFS配套优化：哈希判重

状态复杂（字符串、多维数组）无法开数组标记访问时，用哈希表存储已走过状态，避免重复入队。

八、搜索算法选择总结

九、易错点汇总

1. 距离比较时禁用sqrt，平方后用long long避免精度、溢出问题；
2. 大数据输入使用scanf/printf，cin关闭同步或直接淘汰；
3. DFS回溯必须恢复现场，否则状态污染；
4. BFS必须判重，否则死循环；
5. 连通性问题分清有向图/无向图，按需建反向图；
6. 记忆化数组初始化无穷大，到达同一状态代价更小时才更新；
7. 递归DFS注意递归深度上限，深度极大改用迭代加深或BFS。

十、配套上机习题

1. 奶酪：基础连通DFS
2. 飞越原野：BFS+记忆判重
3. 寻找道路：反向DFS+正向BFS综合
4. 棋盘：DFS+记忆化最优剪枝
5. 靶形数独：DFS+搜索顺序优化
6. 小木棍：DFS多重可行性/最优性剪枝

玫瑰不必长高

    小区花园一角有几丛玫瑰静静盛放，与附近奋力向天生长、争高比大的杨树不同，也不同于墙边需要攀附他物方能向上的藤蔓，故而它自自然然地立于泥土之中，在晨光初照、清风徐来时，很自然、很从容地舒展花瓣。因此其姿态简单天真，所作之事亦最本分、最快乐。

    从近处细看，可知其枝干细润而有分明、挺利的尖刺，更妙的是尖刺越分明硬朗，枝头所托之花便红得越鲜亮，清甜的香味也因此自然流露、扩散得更远。阳光穿过层层叠叠的绿叶，碎金似的光斑直接洒在花瓣上，故而那红色温润莹润，简直似被阳光轻轻吻过，遂有一层柔和圆润的光晕。因此，这小小的带刺之物，实为角落中不动声色的绝好风姿。

    路过的人对尖刺的反应有十分清楚、自然的差别：有人见了尖刺便绕道而行，有人停步弯腰，避开刺尖，轻托花枝，欲仔细嗅一嗅其芬芳。而玫瑰本身对此全无反应：它从没有因为自己不如杨树高大而低头丧气，也从来没有因为有人惧怕尖刺而收起锋芒，只是坦然开放，神情从容，仿佛早已明悟：真正为它驻足的人，爱的绝不是它的高度，而是它静静绽放时所释放的香气。

    看到这株玫瑰，我不由自主地联想到一个问题：玫瑰有刺，但并没有因此失去美，同样，人有棱角、有个性，不也恰恰是珍贵、独特之处吗？而现实中人人都生活在“要更优秀”、“要更懂事”、“要更符合别人的期待”的种种声音之中，因此不少人在主动修剪自己，磨平棱角，改变模样，去换取一声喝彩、一份认可。但毋庸讳言，在连绵不断的改变、迎合之中，最本真的那个鲜活的、带着露水清气的自我已经悄然消逝。

    “自己”是否也同褪色的花瓣一样，正在逐渐黯淡、凋零，因而失去了原有的光彩和芬芳呢？

    玫瑰不必长高，爱花的人自然会为它弯腰，由此也自然地引出人生的很有意境的道理：人生最重要的不是去拼命踮脚摘取不属于自己的高度，而是守住内心那份属于自己的“香气”，即你的热爱、你的真诚、你本来的样子。因此，当你安然接纳自己，在自己的土地上踏实扎根、妥帖生长，终有某一天，有人会穿过茫茫人海，只为寻你而来，为你驻足，为你低眉，为你流连。真正的价值，从来不需要声嘶力竭去证明。你若盛开，清风与懂得，自会前来。

关于 FMCRAFT 更新 使钱换积分 制度的说明

起初

自古以来，FMCRAFT 就有 1 人民币 = 50 积分 的说法
但是我考虑到，这样贫富差距过大
所以我决定，更新制度
在此之后，所有关于【积分换钱】的制度除本制度无效

新制度

计算方式

概述：$1$ 人民币 = $50 \times (1-x)$ 积分

$x$ 为个人 skill 技能值
你可以通过 /sk 查看个人技能值，管理员也可以通过 sk profile skills 玩家名 查看玩家个人技能值
skill 分为以下几个技能：

• Agility - 敏捷
• Alchemy - 炼金
• Archery - 射箭
• Defense - 防御
• Enchanting - 附魔
• Excavation - 挖掘
• Farming - 农耕
• Fighting - 战斗
• Fishing - 钓鱼
• Foraging - 采集
• Mining - 采矿

我们定义一个值 $t$，为您上述各个等级中最高的一个等级
我们列出以下表，来表示您的 $t$ 所对应的 $x$

简单地说，$t$ 与 $x$ 成正比，比值为 $100$
特别的，如果计算出的积分为浮点数，需要向上取整

打一个生动的比方，您捐赠了 10 元，您的最高经验等级为 $16$，所以 $t=16$，您的 $x=0.16$，因此您可得 $420$ 积分

领取方式

您需要先前往 https://www.tropical-fish.cn/281.html 下方的 【捐赠】，用您的【微信】或者【支付宝】扫描其中的二维码，备注为您的游戏名
随后，您可前往 https://user.fmcraft.top/ 完成登录，完成邮箱绑定，发起工单，类型为【FMCRAFT-其他】，名称为 【钱换积分-{游戏名}-{捐赠日期}】，内容需要包含您支付的日期和您的游戏名，在我们处理后会发放您的奖励并标记工单为完成状态