第 49 章　模拟

本章配套 12 道例题，见 §例题。

模拟题没有算法：题目怎么说，代码就怎么做。 但它是笔试里丢分最多的一类——不是因为想不出，而是因为读漏了一句话。

模拟题的唯一考点是「读题的精确度」和「状态建模的干净程度」。 它考的是工程能力，不是算法能力。

---

1　模拟题的读题方法

把题面逐句拆成「状态」和「规则」两张清单，写在纸上，一句都不许跳。

以 BISHI19 乒乓球为例：

题面句子	归类	落到代码
「W 表示得分，L 表示对手得分」	状态	a, b 两个计数器
「某选手分数 \(\ge 11\) 且分差 \(\ge 2\) 时一局结束」	规则	if (a>=11 or b>=11) and abs(a-b)>=2
「新局开始时比分记为 0:0」	规则	a = b = 0
「若读取结束时当前局未结束，也需输出」	边界	循环外补一次输出
「分别按 11 分制与 21 分制统计」	结构	同一份逻辑跑两遍，参数化
「空行分隔两部分」	输出格式	中间插一个 ""

六句话，六处代码。漏掉第 4 句就是 WA，漏掉第 6 句也是 WA。

三条读题纪律：

纪律	说明
注意「且」与「或」	「\(\ge 11\) 且分差 \(\ge 2\)」写成「或」直接错
注意「严格」	「严格大于」不含等号，「不小于」含等号
注意输出的边界情形	「未结束的局也要输出」「可能输出 0:0」

---

2　状态建模：用最简单的容器

模拟题写不下去，通常是状态选错了容器。

状态	推荐容器	反例
二维网格	list of list，或一维 list + i*m+j	用 dict 存坐标（慢且啰嗦）
有序序列，两端操作	deque	list.pop(0) 是 \(O(n)\)
光标左右两侧	对顶栈（两个 list，一个倒序）	在中间 insert，\(O(n)\)
有限状态机	dict 映射「(状态, 输入) → 新状态」	层层嵌套 if
循环轮转（回合制）	turn ^= 1 或 turn = (turn+1) % k	复制粘贴两份逻辑
方向移动	方向数组 DX = (0,0,1,-1)	四份重复代码

网格模拟的标准骨架

DX = (-1, 1, 0, 0)
DY = (0, 0, -1, 1)          # 上下左右，顺序随意但两个数组必须一一对应

for k in range(4):
    nx, ny = x + DX[k], y + DY[k]        # 同一个 k 取出同一个方向
    # 链式比较等价于 0 <= nx and nx < n，且 nx 只求值一次
    # 必须先判越界再访问：Python 的负下标会从尾部回绕，不报错但静默取错格子
    if 0 <= nx < n and 0 <= ny < m:      # 链式比较，越界判断的标准写法
        ...

八连通就写 8 个方向，或者：

for dx in (-1, 0, 1):
    for dy in (-1, 0, 1):
        if dx or dy:                     # 排除 (0,0)，即原地不动这一种组合
            ...

回合制的标准骨架

turn = 0                                 # 0 / 1 表示两名玩家
while not finished:
    move(players[turn])
    turn ^= 1                            # 异或 1 只翻转最低位，于是在 0 和 1 之间来回切

---

3　三个高频子模型

一、日期

# 首位补 0，让下标直接等于月份：MONTH[1] 是 1 月，MONTH[12] 是 12 月
MONTH = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
# 平年各月天数的前缀和：PRE[m] = 1..m-1 月的总天数（同样首位补 0 对齐月份下标）
PRE = (0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334)


def is_leap(y):
    # 四年一闰、百年不闰、四百年再闰；括号里的 and 必须整体先算，顺序不能改
    return (y % 4 == 0 and y % 100 != 0) or y % 400 == 0


def days_in_month(y, m):
    return 29 if (m == 2 and is_leap(y)) else MONTH[m]


def day_of_year(y, m, d):
    # 只有 3 月及以后才补闰日：2 月 15 日在平年闰年同为第 46 天
    return PRE[m] + d + (1 if is_leap(y) and m > 2 else 0)

闰年规则一字不能错：(能被 4 整除 且 不能被 100 整除) 或 能被 400 整除。 而且只有 3 月及以后才 +1——2 月 15 日在闰年和平年是同一个「第 46 天」。

Python 也有 datetime，但竞赛里慎用： 它的年份范围是 \([1, 9999]\)，而题目常给到 \(Y \le 3000\)（够用）或更大（不够用）； 另外 datetime 不接受非法日期，而某些题恰好要求判断日期是否合法。 自己写 12 行更可控。

二、字符串逐字符处理

s = sys.stdin.buffer.read().split()[0]   # bytes
for c in s:
    d = c - 48                            # bytes 逐字节得到的是 int，减去 '0' 的码值即数值

bytes 迭代出的是 int 不是 str，c == "0" 恒为假。 要么写 c == 48，要么一开始就 .decode()。 这是 sys.stdin.buffer 用法里最高频的坑，见 输入输出处理。

三、输出格式

模拟题的输出格式往往很啰嗦，几条通用建议：

"%d:%d" % (a, b)                # 定制分隔符，比 str 拼接更不易漏掉符号
"%.2f" % x                      # 固定小数位（四舍五入到 2 位）
"%05d" % x                      # 补前导零到 5 位宽
"YES" if ok else "NO"           # 注意大小写！Yes / YES / yes 是三种不同答案
sys.stdout.write("\n".join(out) + "\n")   # 一次写出，10^5 行时逐行 print 会 TLE

---

4　模拟题易错点清单

写完之后，照着这张表过一遍。

#	易错点	典型表现
1	多组数据没给组数	必须读到 EOF（BISHI16）
2	循环结束后的收尾输出	「未结束的一局也要输出」（BISHI19）
3	「严格大于」vs「不小于」	平局算不算赢（BISHI9、BISHI17）
4	下标 0-based / 1-based	「第 \(t\) 名」对应 a[t-1]
5	状态清零的时机	新一局开始时比分归零
6	输出的大小写与标点	Yes / YES / yes 是三种不同答案
7	空行分隔	两部分输出之间要不要空行
8	bytes 与 str 混用	c == "0" 恒假
9	原地修改边遍历	遍历列表时删除元素
10	浮点参与判定	能用整数就别用浮点（m*3//2 vs int(m*1.5)）
11	数据规模	\(10^5\) 行输出必须 join
12	题面的「可以为 0 / 为空」	「一个都不选」也是合法方案

第 2 条和第 5 条几乎是模拟题的固定考点。 只要题目里出现「分段 / 分局 / 分组」，就一定要问： 最后一段没走完怎么办？新一段开始时要重置什么？

---

5　例题

题号	题名	难度	题解
BISHI10	小红的字符串修改	简单	题解
BISHI11	变幻莫测	简单	题解
BISHI13	九倍平方数	简单	题解
BISHI15	小红的夹吃棋	简单	题解
BISHI16	计算一年中的第几天	入门	题解
BISHI17	纸牌游戏	简单	题解
BISHI19	乒乓球	简单	题解
BISHI20	回文日期	简单	题解
BISHI67	穿搭大挑战	简单	题解
BM98	螺旋矩阵	简单	题解
BM99	顺时针旋转矩阵	中等	题解
LC54	螺旋矩阵	中等	题解

BISHI16　计算一年中的第几天（入门）

输入年月日（\(1 \le Y \le 3000\)），输出是本年第几天。多组数据，未给组数。 题面见 原题。

import sys

# 每月天数的前缀和（平年）：PRE[m] = 1..m-1 月的总天数
PRE = [0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334]

data = sys.stdin.buffer.read().split()    # 未给组数，一把读到 EOF 最省事
out = []
# 每组消耗 3 个 token；上界写 len(data)-2 保证最后一组是完整三元组，末尾空白不会越界
for i in range(0, len(data) - 2, 3):
    y, m, d = int(data[i]), int(data[i + 1]), int(data[i + 2])
    leap = (y % 4 == 0 and y % 100 != 0) or y % 400 == 0
    # PRE[m] 是前 m-1 个月的总天数，加上 d 即本年第几天；只有 3 月起才补闰日
    out.append(PRE[m] + d + (1 if leap and m > 2 else 0))
sys.stdout.write("\n".join(map(str, out)) + "\n")

三个要点：

• 没有给组数（易错点 1）。题面只说「输入可能有多组测试数据」， 必须读到 EOF。sys.stdin.buffer.read().split() 一把梭最省事， 而且不怕行尾空白和空行。
• range(0, len(data) - 2, 3)：每组消耗 3 个 token， - 2 保证最后一组是完整的三元组，末尾多余的空白不会导致 IndexError。
• 预处理前缀和表代替逐月累加，每组 \(O(1)\)。

题解见 solutions/nowcoder/BISHI16/sol.py。

BISHI17　纸牌游戏（简单）

Alex 和 Bob 各有 2 张牌，两回合，每回合各翻一张比大小（严格大者赢，相等无人得分）。 赢的回合更多者获胜。求 Alex 获胜的翻牌顺序数量。\(t \le 10^4\)。 题面见 原题。

Alex 的出牌顺序 2 种、Bob 的 2 种，共 4 种翻牌顺序，直接枚举：

import sys

data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(t):
    a1, a2, b1, b2 = map(int, data[1 + 4 * i:5 + 4 * i])   # 每组 4 个 token
    cnt = 0
    # Alex 2 种出牌顺序 × Bob 2 种 = 4 种翻牌顺序，逐一检查
    for a in ((a1, a2), (a2, a1)):
        for b in ((b1, b2), (b2, b1)):
            win = sum(x > y for x, y in zip(a, b))     # 严格大才算赢
            lose = sum(x < y for x, y in zip(a, b))    # 相等时两边都不计分
            if win > lose:                             # 平分不算 Alex 获胜
                cnt += 1
    out.append(cnt)                                    # 统计顺序数量，牌面重复也不去重
sys.stdout.write("\n".join(map(str, out)) + "\n")

三个要点：

• 单回合相等时双方都不得分（易错点 3）。写成「谁都赢」或「都算一分」都错。
• 平分不算 Alex 赢，必须 win > lose。
• 统计的是「顺序数量」不是概率，所以即便牌面重复，4 种顺序也各算一种—— 样例 10 10 2 2 的答案是 4 就是证据。别去重。

题解见 solutions/nowcoder/BISHI17/sol.py。

BISHI19　乒乓球（简单）

一串 W/L 记录（\(|s| \le 10^5\)），分别按 11 分制和 21 分制切局并输出每局比分。 规则：某方 \(\ge\) 目标分且分差 \(\ge 2\) 时本局结束；未结束的当前局也要输出； 两部分之间空一行。 题面见 原题。

把「目标分」参数化，同一份逻辑跑两遍——这是模拟题最常见的重构：

import sys


def split_games(record, target):
    """把记录按「先到 target 分且领先 2 分」切局。target 参数化，11 分制与 21 分制共用。"""
    res, a, b = [], 0, 0
    for ch in record:
        if ch == "W":
            a += 1
        else:
            b += 1
        # 是「且」不是「或」：13:11、15:13 都合法，写成「等于 target」直接错
        if (a >= target or b >= target) and abs(a - b) >= 2:
            res.append("%d:%d" % (a, b))
            a = b = 0                   # 新局开始，比分归零
    res.append("%d:%d" % (a, b))        # 未打完的当前局（可能是 0:0）也要输出
    return res


s = sys.stdin.buffer.read().decode().strip()
out = split_games(s, 11) + [""] + split_games(s, 21)   # 插一个空串，join 后即两部分间的空行
sys.stdout.write("\n".join(out) + "\n")

这题把 §4 的清单考了个遍：

• 「\(\ge\) 目标分 且 分差 \(\ge 2\)」：13:11、15:13 都是合法结果， 写成「等于 11」直接错（易错点 3）。
• 循环外的收尾输出（易错点 2）：即使上一球刚好打完一局、新局比分还是 0:0， 也要输出一行 0:0。这是 NOIP 原题的标准做法，也是本题最大的坑。
• 新局归零（易错点 5）。
• 两部分之间的空行（易错点 7）：用 + [""] + 插一个空串，join 后就是空行。

题解见 solutions/nowcoder/BISHI19/sol.py。

BISHI15　小红的夹吃棋（简单）

\(3\times3\) 棋盘，* 黑、o 白、. 空。横向或纵向三连的中间被对方两子夹住即被「夹吃」。 仅一方有子被夹则对方胜（kou / yukari），否则平局（draw）。 题面见 原题。

枚举全部可能被夹的位置——\(3\times3\) 里能被夹的只有「三连的中间」： 横向 3 个（每行第 2 列）+ 纵向 3 个（每列第 2 行）= 6 个位置：

import sys

data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(t):
    g = [row.decode() for row in data[1 + 3 * i:4 + 3 * i]]    # 每组 3 行棋盘
    black_eaten = white_eaten = False
    # 3x3 里能被夹住的只有「三连的中间格」：每行第 2 列 + 每列第 2 行，共 6 个
    # 统一整理成 (中, 左, 右) 三元组，横纵两种情形共用同一份判定
    pos = [(g[r][1], g[r][0], g[r][2]) for r in range(3)]      # 横向三连的中间格
    pos += [(g[1][c], g[0][c], g[2][c]) for c in range(3)]     # 纵向三连的中间格
    for mid, left, right in pos:
        # 链式比较：两侧同色且非空，中间有子且与两侧异色，才构成夹吃
        if mid != "." and left == right != "." and left != mid:
            if mid == "*":
                black_eaten = True
            else:
                white_eaten = True
    if black_eaten and not white_eaten:
        out.append("yukari")
    elif white_eaten and not black_eaten:
        out.append("kou")
    else:
        out.append("draw")
sys.stdout.write("\n".join(out) + "\n")

• 把「被夹」的判定抽象成三元组 (中, 左, 右)，横纵两种情形共用一份判定， 代码量减半。这是 §2「用最简单的容器」的体现。
• left == right != "." 是链式比较，等价于 left == right and right != "."。
• 输出别弄反：黑子（小红 *）被夹 → 小紫赢 → yukari。 「若仅一方存在被夹吃的棋子，则对方获胜」——这个「对方」是本题唯一的陷阱。
• 双方都被夹 / 都没被夹都是平局（易错点 12）。

题解见 solutions/nowcoder/BISHI15/sol.py。

BISHI11　变幻莫测（简单）

两种操作：交换 \((X,Y)\to(Y,X)\)；变换 \((X,Y)\to(X+Y, X-Y)\)。 求使 \(X = Y\) 的最少操作次数，无法实现输出 \(-1\)。\(|X|,|Y| \le 100\)。 题面见 原题。

这题看着要 BFS 搜索状态，实际上答案只有 5 种。 把两种操作写成矩阵 \(S = \begin{pmatrix}0&1\\1&0\end{pmatrix}\)、 \(T = \begin{pmatrix}1&1\\1&-1\end{pmatrix}\)，关键性质是

\[S^2 = I, \qquad T^2 = 2I\]

所以任何操作序列化简后都是 \(S\)、\(T\) 交替的约化词乘一个常数， 而 \(X = Y\) 这个条件对整体缩放不敏感。于是只需枚举交替词：

步数	词	判定条件
0	\(I\)	\(X = Y\)
1	\(T\)	\(Y = 0\)
2	\(T S\)	\(X = 0\)
3	\(T S T\)	\(X + Y = 0\)
\(\ge 4\)	—	条件开始重复，不会产生新解

x, y = map(int, input().split())

# 必须按步数 0 -> 1 -> 2 -> 3 的顺序判，先命中的就是最少步数；顺序打乱会给出偏大的答案
if x == y:
    print(0)          # 已经相等，一步都不用
elif y == 0:          # 一次变换：(X,Y) -> (X+Y, X-Y)，Y=0 时两边都是 X
    print(1)
elif x == 0:          # 先交换成 (Y,0)，再变换
    print(2)
elif x == -y:         # 变换、交换、变换；此时 X+Y = 0，第三步两边相等
    print(3)
else:
    print(-1)         # 连续两次变换只等于整体乘 2，不产生新解，>= 4 步不必再试

• 必须按 0→1→2→3 的顺序判断，否则 \((0,0)\)、\((5,0)\) 这类会给出偏大的答案。
• 连续两次变换等于同时乘 2，不产生新的可行解——所以「多操作几次就有救」是错觉。

模拟题里有一类「伪模拟」：题面描述了一个过程，但状态空间其实极小或有代数结构， 正解是分析而不是模拟。看到「最少操作次数」且操作可逆时， 先想想操作生成的群有多大。

题解见 solutions/nowcoder/BISHI11/sol.py。

其余五题的归属

题单里的模拟题有几道更适合放在专题章节里讲，这里只给索引：

题	主要考点	主讲章节
BISHI10 小红的字符串修改	字符环上的距离 + 枚举起点	字符串处理
BISHI12 元素方碑	不变量（奇偶位和），排序会毁掉它	排序 §7
BISHI13 九倍平方数	数字和模 9 的性质	基础数学与递推
BISHI14 特殊的科学计数法	浮点与字符串解析	浮点与科学计数法
BISHI18 多项式输出	纯输出格式模拟，规则多达 5 条	多项式
BISHI20 回文日期	日期合法性 + 回文枚举	回文

BISHI18 是「输出格式模拟」的典型：系数为 0 省略、系数为 \(\pm1\) 省略绝对值 （常数项除外）、次数为 1 只写 x、首项不带 +…… 五条规则要逐条落到代码，且要用样例逐字符核对。 这类题没有技巧，只有耐心。

BISHI20 是「日期 + 枚举」的典型：不要逐日枚举 8 位数（\(10^8\) 太多）， 而是枚举前 4 位年份，翻转得到后 4 位月日，再判合法性——只有 \(10^4\) 次。 这个「枚举一半再对称构造」的思路，与 构造 的套路②相通。

---

面试题单里的两道矩阵模拟题

螺旋矩阵（同一道题在另一处题库里编号 LC 54. 螺旋矩阵）按顺时针从外向内输出矩阵元素。 写法有两种，各有各的坑：

1. 四个边界收缩：维护 top / bottom / left / right 四条线， 走完一行或一列就把对应的边收进来。 每走完一条边都要立刻判一次「四条边界是否已经交错」， 否则非方阵在最后一圈会把中间那一行或一列输出两遍。
2. 转圈剥皮：每次取出第一行，再把剩下的部分逆时针转 90 度，重复到空。 在 Python 里这一版短得多——matrix = [list(r) for r in zip(*matrix)][::-1] 一行完成旋转， 代价是每轮都新建一个矩阵，额外空间 \(O(nm)\)。规模小的时候值得用它换正确性。

顺时针旋转矩阵把上面那行拆开来考：把 \(n \times n\) 矩阵原地顺时针转 90 度。 原地做法是先沿主对角线转置，再逐行反转，两步都只用交换，额外空间 \(O(1)\)。 转置的循环必须写成 for i in range(n): for j in range(i + 1, n)—— 从 i + 1 起步，否则每对元素会被交换两次，等于没转。 不要求原地时，[list(r) for r in zip(*a)][::-1] 更省事， zip(*a) 的转置全程在 C 层。

6　本章速查

读题	做法
把题面拆成「状态」+「规则」两张清单	逐句对应到代码
「且」/「或」	逐字确认
「严格大于」/「不小于」	等号在不在
输出的边界情形	最后一段 / 空结果 / 0:0

状态	容器
网格	list of list + 方向数组
两端操作	deque
光标	对顶栈
回合切换	turn ^= 1
状态机	dict[(状态, 输入)] = 新状态

高频坑	对策
多组数据没给组数	读到 EOF：buffer.read().split()
循环结束后的收尾输出	循环外补一次
新一段开始要重置	找齐所有需要归零的变量
bytes 迭代出 int	c == 48 或提前 .decode()
大小写	Yes / YES / yes 逐字符核对
浮点参与判定	改用整数（m*3//2）
日期	自己写 12 行，别用 datetime
闰年	(y%4==0 and y%100!=0) or y%400==0，只有 3 月起 +1
\(10^5\) 行输出	"\n".join 一次写出
「伪模拟」	操作可逆且状态空间小 → 先做代数分析