Complete Search 完全搜索

完全搜索（暴力枚举）是最基础的算法思想：枚举所有可能的解，逐一检查。适用于数据规模小、状态空间有限的题目。USACO Bronze 中大量题目都可以用完全搜索解决。

题目列表

#	题目	来源	难度
01	Milk Pails	USACO 2016 Feb Bronze	⭐⭐
02	Diamond Collector	USACO 2016 US Open Bronze	⭐⭐
03	Daisy Chains	USACO 2015 Dec Bronze	⭐⭐
04	Counting Liars	USACO 2022 US Open Bronze	⭐⭐
05	Cow Gymnastics	USACO 2015 Jan Bronze	⭐⭐⭐
06	Bovine Genomics	USACO 2017 US Open Bronze	⭐⭐⭐

---

01. Milk Pails

题目链接

题目描述

给定 X、Y、M，求 aX + bY 不超过 M 的最大值，其中 a, b 为非负整数。

数据范围：1 <= X, Y <= 100，1 <= M <= 1000。

示例

输入：

17 25 77

输出：

76

解释： 取 a = 3, b = 1，3 × 17 + 1 × 25 = 76。

思路及解法

枚举 a 和 b 的所有合法组合：

• a 的范围：0 <= a <= M // X；
• b 的范围：0 <= b <= M // Y；
• 对每组 (a, b)，计算 aX + bY，若不超过 M，更新答案。

代码

def solve():
    x, y, m = map(int, input().split())
    ans = 0
    for a in range(m // x + 1):
        for b in range(m // y + 1):
            total = a * x + b * y
            if total <= m:
                ans = max(ans, total)
    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O((M/X) \times (M/Y))$，最坏 $O(M^2)$。
• 空间复杂度：$O(1)$。

---

02. Diamond Collector

题目链接

题目描述

给定长度为 N 的数组和 K，输出最长子序列的长度，要求子序列中任意两数之差不超过 K。

数据范围：1 <= N <= 1000，1 <= K <= 10000。

示例

输入：

5 3
1
6
4
3
1

输出：

4

解释： 选 1, 4, 3, 1，最大值减最小值 = 3 ≤ K。

思路及解法

枚举每个数 x 作为最小值，统计满足 x <= y <= x + K 的 y 的个数，取最大值。

易错点：不能用 abs(y - x) <= K，否则可能把差值超过 K 的两个 y 同时算入。

代码

def solve():
    n, k = map(int, input().split())
    a = [int(input()) for _ in range(n)]

    ans = 0
    for x in a:
        cnt = 0
        for y in a:
            if x <= y <= x + k:
                cnt += 1
        ans = max(ans, cnt)

    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(N^2)$。
• 空间复杂度：$O(N)$。

---

03. Daisy Chains

题目链接

题目描述

给定 n 朵花的美丽值，求有多少个子数组的平均值恰好等于其中某朵花的美丽值。

数据范围：1 <= n <= 100。

思路及解法

枚举所有子数组 [i, j]，计算平均值，检查区间内是否存在某朵花的美丽值等于平均值。

代码

def solve():
    n = int(input())
    a = [int(input()) for _ in range(n)]

    ans = 0
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += a[j]
            length = j - i + 1
            # 平均值 = total / length，判断区间内是否有花等于它
            if total % length == 0:
                avg = total // length
                for k in range(i, j + 1):
                    if a[k] == avg:
                        ans += 1
                        break

    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(n^3)$，n <= 100 时约 $10^6$，可以通过。
• 空间复杂度：$O(n)$。

---

04. Counting Liars

题目链接

题目描述

给定 N 头牛的陈述：

• L p：Bessie 的位置 ≤ p；
• G p：Bessie 的位置 ≥ p。

求至少需要多少头牛说谎，才能让剩下的陈述存在某个位置 x 同时满足。

数据范围：1 <= N <= 1000，0 <= p <= 10^9。

示例

输入：

2
G 3
L 5

输出：

0

解释： 3 ≤ x ≤ 5 有解，无需说谎。

思路及解法

把所有 (p, 类型) 按 p 升序排序。枚举每个 p_i 作为分界点 x：

• 左侧的 L 说谎：p < x 的 L；
• 右侧的 G 说谎：p > x 的 G。

用前缀和统计左侧 L 数量，后缀和统计右侧 G 数量，取最小值。

代码

def solve():
    n = int(input())
    cows = []
    for _ in range(n):
        typ, p = input().split()
        cows.append((int(p), typ))
    cows.sort()

    left_lying = [0] * n
    for i in range(1, n):
        left_lying[i] = left_lying[i - 1]
        if cows[i - 1][1] == 'L':
            left_lying[i] += 1

    right_lying = [0] * n
    for i in range(n - 2, -1, -1):
        right_lying[i] = right_lying[i + 1]
        if cows[i + 1][1] == 'G':
            right_lying[i] += 1

    ans = n
    for i in range(n):
        ans = min(ans, left_lying[i] + right_lying[i])
    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(N \log N)$，排序开销。
• 空间复杂度：$O(N)$。

---

05. Cow Gymnastics

题目链接

题目描述

给定 K 次训练中 N 头牛的排名，求有多少对牛 (i, j) 满足：在所有训练中，i 始终排在 j 前面。

数据范围：1 <= K <= 10，1 <= N <= 20。

思路及解法

用二维布尔数组 a[i][j] 表示「牛 i 在牛 j 前面」是否在所有训练中成立。

对每次训练，枚举所有 (i, j) 对，如果 i 在 j 前面，标记 a[i][j] = True。

最后统计满足 a[i][j] == True 且 a[j][i] == False 的对数。

代码

def solve():
    k, n = map(int, input().split())
    a = [[False] * n for _ in range(n)]

    for _ in range(k):
        b = list(map(int, input().split()))
        b = [x - 1 for x in b]
        for i in range(n):
            for j in range(i + 1, n):
                a[b[i]][b[j]] = True

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            if a[i][j] ^ a[j][i]:
                ans += 1

    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(K \times N^2)$。
• 空间复杂度：$O(N^2)$。

---

06. Bovine Genomics

题目链接

题目描述

给定 N 头有斑点牛和 N 头无斑点牛的基因序列（长度为 M），求有多少列满足：该列中有斑点牛的基因与无斑点牛的基因完全不同（无交集）。

数据范围：1 <= N, M <= 100。

思路及解法

对每一列，统计有斑点牛出现的基因种类，再检查无斑点牛是否有相同基因。若无交集，则该列合法。

代码

def solve():
    n, m = map(int, input().split())

    spot = [input().strip() for _ in range(n)]
    plain = [input().strip() for _ in range(n)]

    ans = 0
    for j in range(m):
        spot_set = set()
        for i in range(n):
            spot_set.add(spot[i][j])

        valid = True
        for i in range(n):
            if plain[i][j] in spot_set:
                valid = False
                break

        if valid:
            ans += 1

    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(M \times N)$。
• 空间复杂度：$O(N)$。

---

总结

题目	核心技巧	时间复杂度
Milk Pails	双重枚举	$O(M^2)$
Diamond Collector	枚举最小值 + 统计区间	$O(N^2)$
Daisy Chains	枚举子数组 + 平均值判断	$O(n^3)$
Counting Liars	排序 + 前缀和/后缀和	$O(N \log N)$
Cow Gymnastics	二维布尔数组标记	$O(K \times N^2)$
Bovine Genomics	逐列检查 + 集合去重	$O(M \times N)$

完全搜索的通用套路：

1. 明确枚举对象：枚举起点、终点、子集、排列，还是某个分界点；
2. 确定枚举范围：根据约束条件缩小范围，避免无效枚举；
3. 检查每个候选解：用 $O(1)$ 或 $O(n)$ 时间验证；
4. 优化：排序、前缀和、集合去重、剪枝。

Bronze 题目特点：数据规模小（$N \le 1000$），$O(N^2)$ 甚至 $O(N^3)$ 都能通过，重点是思路清晰、边界正确。

相关题目

• USACO 2016 Feb Bronze. Milk Pails
• USACO 2016 US Open Bronze. Diamond Collector
• USACO 2015 Dec Bronze. Daisy Chains
• USACO 2022 US Open Bronze. Counting Liars
• USACO 2015 Jan Bronze. Cow Gymnastics
• USACO 2017 US Open Bronze. Bovine Genomics