第 49 章　模拟

配套例题：BISHI10 小红的字符串修改、BISHI11 变幻莫测、BISHI12 元素方碑、 BISHI13 九倍平方数、BISHI14 特殊的科学计数法、BISHI15 小红的夹吃棋、 BISHI16 计算一年中的第几天、BISHI17 纸牌游戏、BISHI18 多项式输出、 BISHI19 乒乓球、BISHI20 回文日期 来源：无固定课件来源，本章从题单中的模拟题归纳共性

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

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

---

49.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」

---

49.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 之间来回切

---

49.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 用法里最高频的坑，见 20-输入输出处理。

三、输出格式

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

"%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

---

49.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 条几乎是模拟题的固定考点。 只要题目里出现「分段 / 分局 / 分组」，就一定要问： 最后一段没走完怎么办？新一段开始时要重置什么？

---

49.5　例题

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

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

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/BISHI16.py。

BISHI17　纸牌游戏（简单）

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

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/BISHI17.py。

BISHI19　乒乓球（简单）

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

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

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")

这题把 49.4 的清单考了个遍：

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

题解见 solutions/BISHI19.py。

BISHI15　小红的夹吃棋（简单）

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

枚举全部可能被夹的位置——\(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")

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

题解见 solutions/BISHI15.py。

BISHI11　变幻莫测（简单）

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

这题看着要 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/BISHI11.py。

其余五题的归属

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

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

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

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

---

49.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 一次写出
「伪模拟」	操作可逆且状态空间小 → 先做代数分析