大模拟从入门到入坑：调试技巧与解题方式

序言

之前的日报中已经有了对表达式求值这一常见的模拟种类进行了具体的分析，但是没有对大模拟的具体调试方法与做题方式进行完整的总结，这篇文章将会具体阐述适用于所有大模拟的调试技巧与解题方式。（膜 @tiger2005 神虎）

近年来，CCF 及各大比赛的赛场上都会出现几道大模拟，代码难度也有高有低。例如 CSP-J2021 的网络连接；再久远一点的有 CSP-S2020 和有点喜欢出大模拟的 THUPC。

如何在大模拟题减少代码难度，同时得到高分？如何在考场紧迫的时间里完成调试？这些都是我们需要解决的问题。

本文将手把手带领您完成您的第一道蓝及以上的大模拟，您完全可以依赖本文章一步步走，也可以使用自己的方法。如有补充或问题，请您一一指出或喷笔者。

解题技巧

2.1 从输入开始

数据处理类型的大模拟会输入非常多非常恶心的数据，这里推荐使用 cin 进行输入而不是 scanf。因为大模拟对常数基本没有要求，使用兼容性极高的 cin 可以较好地避免 scanf 中的类型错误问题。

常见的输入问题包括以下几个方面：

• 输入以 . 或 : 间隔的时间。这种情况下一般需要手写函数将字符串中的数转为 \(\texttt{int}\) 存储的数。当然可以使用非常好用的 sscanf。sscanf 的具体使用方法可以参见这个剪贴板。
• 输入比较长的一个数。通常这样的整数用于表示序号，因此可以使用 \(\texttt{string}\) 进行存储。\(\texttt{string}\) 同样支持排序和比较，且因为字典序与自然数顺序相通的原因，\(\texttt{string}\) 代替数不但可以减少 \(\texttt{long long}\) 转到 \(\texttt{int}\) 造成的溢出问题，还能在排序和比较上达到与 \(\texttt{long long}\) 相同的功效（注：尽管会在时间复杂度上乘一个字符串的长度，但在字符串一般不会很长的大模拟影响不大，而且字符串长度太长了也应该不能使用数的方式存储了）。
• 输入的内容中包含 " 或者 ' 字符。请使用转义语法。具体操作是在这些字符前面加个\。
  在这里不推荐一次性将所有内容都读进来，开一堆临时变量。建议每次读入一个内容，对该内容进行应有的处理后再继续读入。这样可以避免开很多临时变量导致混淆，也可以使得代码更加直观。

读入数的时候需要计算数的长度再确定是否需要 \(\texttt{long long}\)，例如 P7911 [CSP-J 2021] 网络连接就有可能出现最后一个数长达 \(17\) 位的情况。

2.2 打一张表

大模拟中需要打表的地方一般有两种，一种是真的需要打一张表来对某样东西进行匹配，另一种是用一个标准格式来 check 一个东西。

第一种的具体实例可以参见 P7426 [THUPC2017] 体育成绩统计，在此题中我们需要对长跑秒数及其对应的分数进行打表。

第二种的具体实例同样可以参见 P7911 [CSP-J 2021] 网络连接。此题中可以采用将 IP 地址转换为 1.1.1.1:1 的标准格式来进行 check。

在大模拟使用第一种打表可以减少码长并避免了大量 if 以及可能发生的 if(a=b)。使用第二种打表方式则可以减少分类讨论麻烦或没有讨论全的风险（例如可能存在 ....，:..，...: 等等毒瘤的东西，如果遗漏就可能失分，一个一个判断又太过麻烦）。

2.3 数据处理

真正的数据处理开始了。这部分主要分为两个内容，一是合法性的 check 问题，二是数据的计算问题。

对于合法性的 check，也有两种形式，一种是“是否符合标准格式”，可以直接用 2.2 中的第二种方法较方便地完成；另一种是“是否满足这些条件”，可以通过写多个布尔函数分别判断每个条件组合起来完成（注：需要注意逻辑运算符的优先级）。

对于数据的计算，有以下几个要点：

• 涉及到浮点数的，推荐统一使用 \(\texttt{long double}\) 避免精度误差，并设 eps=1e-5（具体建议依题而定，但多数大模拟这个值非常合适）。
• 减少除法，化除为乘。可用的技巧包括但不限于使用不等式化简和乘法逆元。
• 能不用浮点数就不要用，不使用浮点数可以减少强转整数类型的风险。解决这种问题的方法包括但不限于化为小单位。
• 注意计算数据的最大值防止溢出。

题目中通常会给出计算数据的公式，如果没有需要自己进行简单推导。计算出的数据应当与数据的属于者相绑定以避免一些风险，具体的风险 2.4 中会提到。

最后的输出时需要注意数据的顺序。输出结束后一道大模拟就这样打完了！

2.4 时间复杂度

大多数的大模拟不用考虑时间复杂度，因此排序写 \(O(n^2)\)，字符串的模式串匹配不写 KMP 也能过，但是有的题会卡时间复杂度并强制要求记录信息。

例如 P7426 [THUPC2017] 体育成绩统计，在此题中为了寻找上一条合法记录，我们需要使用一个 \(\texttt{map}\) 来记录。如果使用 \(O(m^2)\) 强行对于每条记录向前搜就会 TLE。

笔者建议在无需优化时间复杂度的时候尽量不要优化。例如 sort 如果没有使用结构体，可能造成原数组被打乱，一些数据会错位（注：所以推荐存储数据使用结构体而不是一堆数组）；KMP 可能会有打错的风险等等。

在常数方面，笔者建议尽量减少 STL 的使用。能用数组就用数组，不仅减少了常数，还便于在调试时进行遍历（注：STL 的常数可能是巨大的）。不建议进行循环展开或手写队列、栈等简易 STL，可能会导致代码极其不直观或出现边界问题。

笔者对位运算表示中立态度。位运算的确可以降低常数，但值得注意的是位运算的优先级是非常严格的。笔者建议每个位运算都打上括号来避免这样的问题。（如果能记住优先级顺序更好）

码长与码时减少技巧

很多时候在考场上选择做大模拟都是因为其它题目毫无思路，由于较长时间想其它题目，很有可能时间已经不多。笔者建议大模拟应该有 \(2\) 到 \(3\) 小时。在较为紧迫的时间下，减少码长和码时是非常重要的。

3.1 减少自写函数

笔者建议尽量使用 C++ 内置函数，减少自己写的函数的数量可以减少调试难度及码长，考试的时候节约时间非常好用。

C++ 中比较好用的函数包括 lower_bound，__builtin_popcount 等等，可以大大减少码长和码时。

关于 STL，笔者建议在最初版的代码使用 STL，如果遇到卡常的困难再手写（明明可以不用 STL 的情况除外）简单的 STL。

3.2 减少重复

笔者推荐将重复的部分写作函数，重复的变量写作数组。例如若要记录 \(01\) 序列的一些信息，而 \(0\) 和 \(1\) 都需要统计时，可以写作一个数组 a[2]，就可以不用写两次统计部分代码而是直接在外面套一个循环。

重复的部分通常不能够直接复制，这样可能造成第二次或后面都忘记改变量名（注：更多的时候是有这个心眼但漏了一个没改）的问题。这样的问题很难以被发现，会造成调试的困难。

3.3 分类讨论技巧

如果出现了分类讨论，可以选择写较容易判断的条件，最后剩下的一个条件直接用 else 完成。具体可以参考我的 CF1627A Not Shading 题解，其中有使用到这种技巧，读者可以下去自己实践一下这个技巧并用这种技巧完成我题解中所提到的另一道题。

分类讨论时，可以选择尽量合并情况来减少码长；也可以不合并情况，以便于调试。

3.4 舍弃 AC

在急需得分但时间紧的情况下，不必强求大模拟的 AC。通常大模拟的部分分是较高的，在少考虑很多的情况下也能得到 \(70\sim 90\) 的分数。题目中通常会给出大量的特殊性质，这些性质非常简单也非常容易判断。

一个很良心的例子是 P7911 [CSP-J 2021] 网络连接，本题中不判断地址是否完全合法，仅仅只分离数并判断这些数是否在要求范围内即可得到 \(65\) 分，而这只需要约 \(20\) 分钟就可做到。

然而相比之下，T4 的正解难以在 \(20\) 分钟内码出，而复杂度为 \(n^2\) 的暴力，吸氧后只能获得 \(60\) 分。性价比大大不如 T3 大模拟。

调试技巧

主要是对拍的技巧。平常可以对着题解对拍，考场可以自己写数据生成器，生成能调的数据。

4.1 函数单独测试

大模拟需要用到的函数非常之多，且每个函数基本都是互相独立的。可以采用将每个函数单独拿出来对拍的方式进行调试，这样可以较快地确定函数的正确性，缩小调试范围。

笔者建议在对拍时间不多时采取大函数至小函数对拍的方法以减少对拍次数。时间较多的时候可以从小函数到大函数一点一点拍，在大函数内套有一堆小函数的时候非常好用。

4.2 数据保证随机

小数据不能够太小，否则容易出现一直拍拍不出来的情况。也要注意，数据尽量保证随机，如果不够随机可能会出现数据一直拍不到错误（例如笔者曾经将一个条件的小于等于号写成了小于，由于自己不想写数据生成器，构造了一组数据，而这组数据满足的是小于，笔者又并没有出等于的数据，导致笔者对拍了一整天但交上去一直是 \(0\) 分）。

有时随机的数据也会很难卡一些小错误（例如上面所说的，小于等于写成小于），需要自己构造一些数据，构造时需要保证数据的强度。

构造的数据尽量保证只针对一个可能的问题。如果一组数据同时针对了两个可能的问题，就会很难调试是错在了哪里。

4.3 常见的问题

有一些低级错误可以在写的时候直接避免，下面罗列了一些难发现而常见的错误：

• int eps=1e-6 以及潜在的类型强转问题。
• if(a=b)，a+b; 等等漏打的错误，这些错误由于 C++ 超强的兼容性不会被发现。
• 函数没有返回值。这一情况在 2021 年比赛开始吸氧且部分城市没有配置 NOI Linux 系统考试后显得格外讨厌，吸氧指令加上没有 Linux 会使得这一问题的影响范围非常大，且在考场不容易被发现。
• 大于等于号、小于等于号在程序里面漏打等于。这一情况需要用特殊构造的数据才能拍出错误，只能通过肉眼观察。

笔者在此强烈推荐 -Wall 指令，此指令可以避免多数由于 C++ 的兼容性引起的问题，尤其是会造成抱零的不写返回值和 Windows 32 位机上能编译通过但到评测机就 CE 的 max 和 min 两边类型不同问题。

实战练习

接下来以 UVA12412 A Typical Homework (a.k.a 师兄帮帮忙) 为例解释以上提到的技巧与方法。

在此之前，读者可以自行尝试一下这道题。请您确保读了题再继续读这篇文章。

首先很明显，我们要对每个学生开一个结构体便于之后操作。

5.1 Query 操作的计算排名

一种方法是写一个 sort 排来排去，时间复杂度是非常优秀的 \(O(n\log n)\)，然而这非常有可能造成 sort 之前没有对原数组 memcpy，就会造成数组被打乱原顺序的问题。

我们可以试试摒弃这样的好时间复杂度，转而使用 \(O(n^2)\) 去对于每个学生都搜一遍前面有多少学生。这样做虽然舍弃了优秀的时间复杂度，但却大大减小了代码难度，不需要先复制数组再一一对应回去。

5.2 Remove 操作

这个操作笔者采用了 \(\texttt{map}\) 还要改标记的方法来做，实际上可以使用 \(\texttt{vector}\) 更好的解决。使用 \(\texttt{vector}\) 及其自带的 pop_back 可以极其优美、极其简单地解决这个操作，大大减小了码长和码时。

5.3 Show Statistics 操作

这是本题中唯一需要浮点数的部分，笔者统一使用了 \(\texttt{long double}\) 来增高精度。

这里容易出现的问题只有精度误差。注意浮点数运算中，参与运算的应该全部都是浮点数，所以要用 *1.0 进行类型转换。

在这个部分，另一个容易出错的就是 eps 的调参。笔者推荐解决此题的 eps 取 \(10^{-5}\)（注：笔者原先将 eps 的类型设为了 \(\texttt{int}\)，由于 eps 放在最上面一直没有发现，请各位读者重视这种难以发现的问题）。

此外，这部分由于输出较多，笔者推荐使用 cout 避免类型问题。由于是 UVA，还需要注意输出格式，非 UVA 的题目不用考虑。

到这里，这道题里容易出现问题的地方就结束了。笔者建议读者自行用 \(2.5\) 小时左右的时间实现并调试，尽量将时间压入 \(2\) 小时。

推荐习题

练习分类讨论请看 CF1280B Beingawesomeism（注：本题援引自我的 CF1627A 题解）。

读者在限时完成所提到的三道大模拟后，还可以尝试在 \(1.5\) 小时内切出该题：

P3952 [NOIP2017 提高组] 时间复杂度

在上题的基础上，可以选择性地尝试该题：

P5698 [CTSC1998]算法复杂度

参考

参考资料

浅谈表达式的求值（Vol.3 使用AST进行代码解析和运行） - tiger2005

浅谈表达式的求值（Vol.2 进阶） - tiger2005

浅谈表达式的求值（Vol.1 后缀表达式） - tiger2005

CF1627A Not Shading 题解 - Zealous_YH

UVA12412 题解 - int64

题解 P7911 【[CSP-J 2021] 网络连接】 - xyf007

P7911 [CSP-J 2021] 网络连接 题解 - Zealous_YH

参考例题

UVA12412 A Typical Homework (a.k.a 师兄帮帮忙)

P7911 [CSP-J 2021] 网络连接

P7426 [THUPC2017] 体育成绩统计

CF1627A Not Shading