码蹄杯模拟赛 Python 解题复盘总结

2301_80395772

515人浏览 · 2026-04-24 20:39:01

2301_80395772 · 2026-04-24 20:39:01 发布

码蹄杯模拟赛 Python 解题复盘总结

比赛时间：2026年4月24日
比赛平台：码蹄杯（Matiji）
参赛语言：Python 3

前言

本次模拟赛遇到了三道比较有代表性的算法题，涉及枚举优化、二维前缀和降维、 区间查询（莫队算法）等核心知识点。本文将详细复盘每道题的解题思路、踩坑记录与优化过程，帮助自己在正式比赛前查漏补缺。

第一题：统计合法四元组

题目大意

给定长度为 $n$ 的数组 $a$ ，统计满足以下条件的四元组 $(q, w, e, r)$ 的数量：

下标严格递增： $\leq q < w < e < r \leq n$
数值满足： $a_q < a_w = a_e > a_r$
结果对 $10007$ 取模

数据范围： $\leq 3000$

我的初始思路

看到"统计四元组"，第一反应是四重循环暴力枚举，但 $O(n^4)$ 在 $n = 3000$ 时直接爆炸（ $3000^4 \approx 8 \times 10^{13}$ ），肯定超时。

优化思路：拆分 + 预处理

核心思想：把四元组拆成中间一对相等的数，左右分别统计。

对于每一对 $(w, e)$ 满足 $w < e$ 且 $a_w = a_e$ ：

left[w]：在 $w$ 左边（ $q < w$ ），满足 $a_q < a_w$ 的数量
right[e]：在 $e$ 右边（ $r > e$ ），满足 $a_r < a_e$ 的数量

则以 $(w, e)$ 为中间点的合法四元组数量为：left[w] * right[e]

代码实现

MOD = 10007

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    # 预处理 left[i]: i 左边比 a[i] 小的数的个数
    left = [0] * n
    for i in range(n):
        cnt = 0
        for j in range(i):
            if a[j] < a[i]:
                cnt += 1
        left[i] = cnt
    
    # 预处理 right[i]: i 右边比 a[i] 小的数的个数
    right = [0] * n
    for i in range(n-1, -1, -1):
        cnt = 0
        for j in range(i+1, n):
            if a[j] < a[i]:
                cnt += 1
        right[i] = cnt
    
    ans = 0
    # 遍历所有 w < e 且 a[w] == a[e] 的对
    for w in range(n):
        for e in range(w+1, n):
            if a[w] == a[e]:
                ans = (ans + left[w] * right[e]) % MOD
    
    print(ans % MOD)

if __name__ == "__main__":
    main()

踩坑记录

关于 right 数组的循环方向：

刚开始对 right 序列移动下标写错，后来想到要从后往前遍历：

for i in range(n-1, -1, -1):

原因：right[i] 统计的是 $i$ 右边比 $a [i]$ 小的数。必须从数组末尾开始，先处理最右边的元素（右边没有数，直接为0），再往左处理。如果正着遍历，计算 i=0 时后面的数还没处理，无法统计右边。

数组	含义	遍历方向	原因
`left[i]`	$i$ 左边比 $a [i]$ 小	从左到右	统计左边
`right[i]`	$i$ 右边比 $a [i]$ 小	从右到左	统计右边

复杂度分析

预处理 left： $O(n^2)$
预处理 right： $O(n^2)$
统计所有 $(w, e)$ 对： $O(n^2)$
总复杂度： $O(n^2)$ ，对于 $n = 3000$ ， $3000^2 = 9,000,000$ ，Python 可以轻松通过。

第二题：统计 1 多于 0 的子矩阵

题目大意

给定 $\times m$ 的 0-1 网格，统计有多少个子矩阵满足：矩阵中 1 的数量 > 0 的数量。

数据范围： $\leq 100$

核心思路：数值转换 + 降维 + 前缀和

第一步：数值转换

把 0 变成 -1，1 保持 1。则：

子矩阵中 1 的数量 > 0 的数量
$\Leftrightarrow$ 子矩阵元素之和 > 0

第二步：枚举上下边界，降维成一维

固定上边界 top 和下边界 bottom，把这两行之间的每一列压缩成一个数 col_sum[j]，表示第 $j$ 列从 top 到 bottom 的元素和。

原二维问题转化为：在 col_sum 数组中，统计有多少个子数组的和 > 0。

第三步：前缀和 + 二分统计

对 col_sum 计算前缀和 pre，则子数组 [l, r) 的和 = pre[r] - pre[l]。

要求 pre[r] - pre[l] > 0，即 pre[r] > pre[l]（其中 $l < r$ ）。

问题转化为：统计前缀和数组中，满足 $l < r$ 且 pre[r] > pre[l] 的 $(l, r)$ 对数。

可以用树状数组或归并排序统计逆序对的思路解决，这里用 bisect 维护有序列表：

import bisect

sorted_pre = []
cnt = 0
for x in pre:
    idx = bisect.bisect_left(sorted_pre, x)  # 找有多少个 pre[l] < x
    cnt += idx
    bisect.insort(sorted_pre, x)  # 插入当前值

完整代码

def main():
    import sys
    import bisect
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr]); ptr += 1
    m = int(input[ptr]); ptr += 1
    
    grid = []
    for _ in range(n):
        row = list(map(int, input[ptr:ptr+m]))
        ptr += m
        # 把 0 变成 -1，1 保持 1
        transformed = [1 if x == 1 else -1 for x in row]
        grid.append(transformed)
    
    ans = 0
    
    # 枚举上边界 top
    for top in range(n):
        col_sum = [0] * m
        # 枚举下边界 bottom
        for bottom in range(top, n):
            # 把当前 bottom 行加到 col_sum
            for j in range(m):
                col_sum[j] += grid[bottom][j]
            
            # 计算前缀和
            pre = [0] * (m + 1)
            for j in range(m):
                pre[j+1] = pre[j] + col_sum[j]
            
            # 统计 pre[r] > pre[l] 的对数
            sorted_pre = []
            cnt = 0
            for x in pre:
                idx = bisect.bisect_left(sorted_pre, x)
                cnt += idx
                bisect.insort(sorted_pre, x)
            
            ans += cnt
    
    print(ans)

if __name__ == "__main__":
    main()

复杂度分析

枚举 top： $O (n)$
枚举 bottom： $O (n)$
更新 col_sum： $O (m)$
前缀和 + 二分统计： $\log m)$
总复杂度： $O(n^2 \cdot m \log m)$

对于 $\leq 100$ ： $100^2 \times 100 \times \log 100 \approx 7 \times 10^6$ ，完全可以通过。

暴力解法对比

如果不优化，直接枚举所有子矩阵的左上角和右下角，再用二维前缀和求和，复杂度是 $O(n^2 m^2)$ ， $100^4 = 10^8$ ，Python 可能会超时。

第三题：区间众数出现次数（莫队算法）

题目大意

给定长度为 $n$ 的序列， $q$ 次询问区间 $[l, r]$ 中，出现次数最多的数的出现次数。

数据范围： $\leq 10^4$

我的初始代码（超时）

import sys
input = lambda: sys.stdin.readline().strip()

n, q = map(int, input().split())
a = list(map(int, input().split()))

for _ in range(q):
    flag = [0] * 1000001  # ❌ 致命错误1：每次创建百万级数组
    l, r = map(int, input().split())
    for i in range(l-1, r):
        flag[a[i]] += 1
    print(max(flag))  # ❌ 致命错误2：每次扫描百万级数组求max

超时原因分析

每次查询创建 [0]*1000001：查询 1 万次 = 创建 100 亿个空间，内存和时间都爆炸
每次遍历整个区间统计：最坏情况 $10^4 \times 10^4 = 10^8$ 次循环
每次 max(flag) 扫描 100 万个数：巨量无用操作
逐行 input() + 逐次 print()：IO 极慢

改进版（能运行但仍可能超时）

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr])
    q = int(data[ptr+1])
    ptr += 2
    a = list(map(int, data[ptr:ptr+n]))
    ptr += n

    output = []
    for _ in range(q):
        l = int(data[ptr]) - 1
        r = int(data[ptr+1]) - 1
        ptr += 2

        cnt = {}
        max_cnt = 0
        for i in range(l, r+1):
            num = a[i]
            cnt[num] = cnt.get(num, 0) + 1
            if cnt[num] > max_cnt:
                max_cnt = cnt[num]
        output.append(str(max_cnt))
    
    print('\n'.join(output))

main()

改进点：

用字典代替百万级数组
边遍历边更新最大值，避免最后 max()
一次性读入 + 一次性输出

但：数据范围 $n,q=10^4$ 时，最坏情况仍是 $10^8$ 次操作，Python 大概率超时。

终极解法：莫队算法

莫队算法是解决无修改区间查询的经典离线算法，核心思想是通过合理排序查询，减少区间移动的总次数。

莫队核心思想

分块：把数组分成大小为 $\sqrt{n}$ 的块
排序查询：按左端点所在块排序，同一块内按右端点排序（奇偶优化）
滑动窗口：用两个指针维护当前区间，只通过"加一个数"或"删一个数"来调整
维护答案：实时维护当前区间的最大出现次数

莫队代码（AC版本）

import sys
import math

def main():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx])
    q = int(data[idx+1])
    idx += 2
    a = list(map(int, data[idx:idx+n]))
    idx += n

    # ========== 莫队核心1：分块 ==========
    block = int(math.sqrt(n)) + 1

    # 读取查询，保存原始顺序
    queries = []
    for i in range(q):
        l = int(data[idx]) - 1
        r = int(data[idx+1]) - 1
        queries.append((l, r, i))
        idx += 2

    # ========== 莫队核心2：排序 ==========
    # 按左端点块号排序，同一块内偶数块r升序，奇数块r降序（减少指针移动）
    queries.sort(key=lambda x: (x[0] // block, x[1] if (x[0]//block) % 2 == 0 else -x[1]))

    # ========== 莫队核心3：滑动指针 ==========
    res = [0] * q           # 存储答案
    cnt = [0] * (10**6 + 10)  # 每个数字出现次数
    frq = [0] * (n + 10)     # 出现次数为c的数字有多少个
    maxf = 0                # 当前最大出现次数
    cl, cr = 0, -1          # 当前指针位置

    # 添加数字x到当前区间
    def add(x):
        nonlocal maxf
        frq[cnt[x]] -= 1
        cnt[x] += 1
        frq[cnt[x]] += 1
        if cnt[x] > maxf:
            maxf = cnt[x]

    # 从当前区间删除数字x
    def remove(x):
        nonlocal maxf
        frq[cnt[x]] -= 1
        cnt[x] -= 1
        frq[cnt[x]] += 1
        # 如果当前最大次数的freq为0，说明没有数字出现这么多次了
        if frq[maxf] == 0:
            maxf -= 1

    # 处理每个查询
    for l, r, i in queries:
        # 扩展左边界
        while cl > l:
            cl -= 1
            add(a[cl])
        # 扩展右边界
        while cr < r:
            cr += 1
            add(a[cr])
        # 收缩左边界
        while cl < l:
            remove(a[cl])
            cl += 1
        # 收缩右边界
        while cr > r:
            remove(a[cr])
            cr -= 1
        
        res[i] = maxf

    # 按原始顺序输出
    print('\n'.join(map(str, res)))

if __name__ == "__main__":
    main()

复杂度对比

算法	时间复杂度	操作次数（n=q=10^4）
暴力（百万数组）	$\cdot n + q \cdot V)$	~ $10^{12}$ （卡死）
暴力（字典优化）	$\cdot n)$	$10^8$ （超时）
莫队算法	$O(n\sqrt{n})$	$\approx 10^6$ （AC）

通用技巧总结

1. 快速读入

# 最快：一次性读入所有数据
data = sys.stdin.read().split()

# 较快：逐行快速读入
input = sys.stdin.readline

千万不要用普通 input() 处理大数据！

2. 快速输出

# 把结果存列表，最后一次性输出
output = []
# ... 处理中 append ...
print('\n'.join(map(str, output)))

千万不要每次查询都 print()！

3. 区间查询问题选型

问题类型	推荐算法	复杂度
无修改，离线查询	莫队算法	$O(n\sqrt{n})$
有修改，离线查询	带修莫队	$O(n^{5/3})$
在线查询，可预处理	线段树/树状数组	$\log n)$
静态区间最值	ST表	$\log n)$ 预处理， $O (1)$ 查询

4. Python 竞赛避坑

坑点	解决方案
创建超大数组 `[0]10*6`	用字典或 `collections.Counter`
多次 `max()` 扫描	边遍历边维护最大值
四重/五重循环	考虑降维、前缀和、莫队等优化
递归深度超限	`sys.setrecursionlimit(300000)`
整数溢出	Python 自动处理大整数，放心