如何优雅的做大模拟题

· · 个人记录

0. 写在前面

考完 2023 年的 CSP-S，我找对象哭了好久，一边大骂自己菜，一边悔恨没有直接开 T1 和 T3，而是把过多的时间耗在了并没有想出来的 T4 上。特别的，T3 由于没看输出格式，部分分都写挂了。

本来连 NOIP 都不想打就直接退役的，结果被教练给强行拉过来了。

这篇文章将会针对大模拟题，和大家一同探讨如何优雅地、尽可能快地做出一道大模拟题目。

大模拟题千千万，本文选用了其中一些大家耳熟能详的大模拟题举例。除了本次考试 S 组 T3，其余题目列表如下：

那么，让我们开始吧。

1. 什么是大模拟

顾名思义，很大的模拟。他们往往具有如下特点：

例如大家耳熟能详的「P2482 猪国杀」「P3693 琪露诺的冰雪小屋」，以及出现在 CSP-S 组的「P7570 儒略日」「P9754 结构体」，THUPC 的题目也有大模拟「P9141 乱西星上的空战」「 P5380 鸭棋 」「 P7610 群星连结」甚至是在 NOIP 中武装了数据结构的「P7963 棋局」 也可以看做一种大模拟。

注：当然，本文所讨论的大模拟，并不包括如同「棋局」这样更偏向考察数据结构却一不小心把码量搞太大了的题。

大模拟极其考验选手的代码实现能力和逻辑的严密性。

大模拟难吗？如难。你要说他难他确实挺难打代码，但从思维上又确实并不太困难。

以下对话摘自我与对象的聊天：

我：大模拟好难……

对象：大模拟这么多年都是这难度，哪里难了？有的时候找找自己的原因好吧，学 OI 这么多年了，CF Raiting 涨没涨，有没有认真打代码好不好。我写大模拟多少年，大模拟难不难的。我是最知道的一个人……

我：……我服了，爸爸！

2. 如何优雅的写出大模拟题

2.1 预备工作：审题

看到标题，你说，SD！你也太敷衍了！小周老师都会审题，你怎么把审题给单独拿出来了！是不是想水字数！

SD：是的（逃）。

大模拟的第一个困难点就是在审题。因为审题的时候，你一定需要草稿纸和笔记录下关键信息。

怎么找？我的物理老师说：做物理题第一步是找对象。对象找不到，物理学不好。我大受震撼，并从中获得启示：做大模拟的第一步，是找对象！对象找不到，大模拟做不好！

我们这里说的对象，指的是「OOP 面向对象程序设计」中的对象。以「P2482 猪国杀」为例，如果我们把每个猪作为对象，我们可以抽象出猪的这么一些属性：

对于每一个抽象出来的属性，我们需要探讨他是否能对所有猪适用。不难发现抽象出前面四个属性是简单地，而在第一次读题就抽象出第五个属性是很困难的。其实，在不断地对规则深入分析中，我们有时候可以抽象出新的属性。并且每个人抽象出的属性可能各不相同。抽象出属性的不同会决定你代码实现方式的不同。

在审题阶段，除了分析对象抽象出对象类型外，还有一项重要的工作：抽象出数据类型。例如 「P9141 乱西星上的空战」中就要求我们定义一个空间向量的类，来实现后面的操作。

注：你说了这么多都是从 OOP 的角度考虑的。我写大模拟必须要用 OOP 的模式吗？我不能用面向过程 POP 吗？

答：当然可以。但笔者认为，在本身就不考虑效率的大模拟题下，OOP 分析问题的模式会更加简洁更加清晰。 当然，目前的 OI 选手大多选择的，也都是 POP。

并且在某些情况下，POP 更利于写程序。比如儒略日。

简而言之，我认为游戏类 / 模拟过程类大模拟使用 OOP，实现功能类大模拟使用 POP。特别的，这里我认为「P9754 结构体」应该属于模拟过程类的大模拟题目。

你当然可以跟我有不一样的想法，我们的目标是拿到分就行了，谁还会去维护自己在 OJ 里交的屎山……

2.2 分析过程，画出流程图

对于一个大模拟题，过程一定是繁多且复杂的。为了防止思路混乱，在草稿纸上画出流程图是一个不错的选择。以「P9754 结构体」中的第一个操作为例子，我们可以画出这样一个流程图。

画出流程图只是为了让你更好的分析问题和检查问题，你可以有不同的画法。

2.3 对比流程图和题意，分析特别需要注意的点

以「P2482 猪国杀」，你可以分析出这么些需要注意的点（摘自题解区）：

尽可能分析出多的细节处理，能让你的大模拟尽可能正确。

2.4 写代码

这部分就没什么好说的了。流程图已经出来了，已经是一个纯粹的翻译过程了。

3. 大模拟题的代码习惯

3.1 不要压行

SD 同学是忠实的压行党。但在些大模拟的时候一定不会压行。

请时刻牢记，代码是写给写代码的人看的，更是写给调代码的人看的。很显然，不压行的写法更利于自己调错。例如，这是我赛后补题写的 T3 代码，其中连续赋值等号对齐、分行分割参数等让 OI 选手看着难受的写法是为了让自己更好的调错。

inline void request_1() {
    string type_name; ll var_cnt;
    __type tmp;
    cin >> type_name >> var_cnt;
    to_id[type_name] = ++ type_counter;
    string var_type, var_name;
    for(ll i = 0; i < var_cnt; ++ i) {
        cin >> var_type >> var_name;
        ll type_id = to_id[var_type],
            lpos   = next_pos(tmp.__size,
                              type_list[type_id].__require);
        tmp.son.push_back({
            var_name,
            type_id,
            lpos,
            lpos + type_list[type_id].__size - 1
        });
        tmp.__size = tmp.son[i].__rpos + 1;
        tmp.__require = max(
            tmp.__require,
            type_list[tmp.son[i].__type].__require
        );
    }
    tmp.__size = next_pos(tmp.__size, tmp.__require);
    cout << tmp.__size << ' ' << tmp.__require << '\n';
    type_list.push_back(tmp);
}

注：「让 OI 选手看着难受的写法」是一个梗，来源于我在某学校线下集训的时候，某同学对我的代码发表出的感慨：看着真难受！

3.2 使用优秀的标识符

优秀的标识符，应该能让你尽可能快的看出来每个变量的作用。使用字母表作为标识符可能会增大你的代码调试难度。

3.3 写注释

同 3.2，也是为了让你更清楚地理解你的代码，让你更方便地调错。

3.4 善用命名空间

同 3.3，也是为了让你更清楚地理解你的代码。一个命名空间只考虑某一类问题，能加速你的查错效率。

3.5 模块化编程

模块化编程不是指的类似 Scratch 一样通过拖积木来编程，而是把每一个功能写成函数或一个模块，这样有助于你快速定位出问题的模块。

3.6 善用 STL

吸氧之后 STL 其实跑得并不慢。使用 STL 的容器也许会让你在模拟链表类数据结构的时候事半功倍。

对于 STL 容器的遍历，如果你不关心下标的值，你可以使用 for(auto e : x) 的写法。依旧以我的代码为例：

// do something...
for(auto e : var_name) {
    if(e == '.') splited_name.push_back(tmp), tmp = "";
    else tmp += e;
}
splited_name.push_back(tmp);

这种写法可以看出循环完成的就是分割字符串的功能。分割字符串的时候我们不关心下标，于是可以这样写，更简洁。

注：

  1. 数组也可以这么遍历，但长度默认是从头到尾；
  2. 你不用这种写法也行。

如果你使用 for(int i = 0; i < x.size(); ++ i) 的写法，请一定注意强制类型转换！因为 .size() 是一个无符号类型，一旦使用 .size() - a 操作就很容易造成错误。正确的做法是先进行强制类型转换，或者拿一个变量存储他，例如：

inline void request_4() {
    splited_name2.clear();
    ll rk;
    cin >> rk;
    if(find3(rk)) {
        for(ll i = 0; i < (ll)splited_name2.size(); ++ i) {
        // another possible verson:
        // ll len = splited_name2.size();
        // for(ll i = 0; i < size(); ++ i)
        // even though there's no need to do so
        // please keep a good coding habit
        // that will help you a lot
            if(i) cout << '.';
            cout << splited_name2[i];
        }
        cout << '\n';
    }
    else cout << "ERR\n";
}

4. 如果在考试的时候遇到了大模拟

这很难评。如果出了猪国杀这种大模拟，出题人应该被禁赛三年（啊？）。

出现大模拟题的比赛，请你认真估计自己的代码能力，自己有没有把握、值不值拿满分。如果是儒略日这种的简单大模拟，请务必保证拿满分（因为别人也能拿满分）；如果是结构体这样的中等难度大模拟，或者是猪国杀这种困难的大模拟，应该至少拿走两个特殊性质分。

\large{\texttt{请时刻记住，OI 比赛的首要目的是拿走}\texttt{\color{red}{尽可能多的分}，\color{black}而不是\color{red}完整地完成题目\color{black}。}}

当然如果你是 AK 佬当我没说。

5. 我有练习大模拟他必要吗？

我认为没有。

大模拟题现在有严重的两级分化趋势：正规考场上考的难度，和各大 OJ 上大模拟的难度（比如 「P3693 琪露诺的冰雪小屋 」「P4911 河童重工的计算机」，相差甚远。甚至大模拟作为考题的概率本身就不是很大。因为你写得难受，出题人也写得难受除非他有特殊癖好。

并且，大模拟题可以作为实现代码能力的练习题，但绝不应该作为锻炼算法思维的练习题，因为他本身思维含量不高。

这就有点像吃饭。饭菜是必要的，就像你板刷的 CF，AT 和往年真题；餐后甜点是可以有但无必要的，例如大模拟题。

我对待大模拟题的态度就是：奖励自己。如果某段时间写代码感觉状态不对劲，就奖励自己一个大模拟。

这是刷大模拟题的优点：他可以理顺你的思维，对于处理复杂问题你可以更快地理顺逻辑。

但是大模拟题并不能让你更快的设计出优秀的算法。大模拟的本质和暴力题是一样的。

如果你一定要做大模拟题，请优先做出在历年考试中的大模拟，其次考虑 THUPC 的大模拟，最后才是各大 OJ 的大模拟。

6. 写在最后

祝大家 NOIP 2023 ++ rp！