#include <bits/stdc++.h>
using namespace std;

int main() {
    // 将 cin/cout 重定向到文件
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 你的解题代码

    return 0;
}

重要： 2020 年起，大多数 USACO 题目使用标准 I/O。始终查看题目说明！

7.1.3 四个级别

USACO 有四个竞赛级别，各有不同难度：

图示：USACO 级别金字塔

USACO Divisions

金字塔展示了 USACO 从底部入门级 Bronze 到顶部精英级 Platinum 的四个级别，每个层级都需要掌握其下方的概念。

🥉 Bronze

受众： 有基础编程知识的初学者
算法： 模拟、暴力、基本循环、简单数组
典型复杂度： 对小 N 是 O(N²) 或 O(N³)，有时凭借洞察是 O(N)
N 约束： 通常 ≤ 1000 或非常小
晋级阈值： 得分 750/1000 或以上（具体阈值因赛而异）

🥈 Silver

受众： 中级程序员
算法： 排序、二分查找、BFS/DFS、前缀和、基础 DP、贪心
典型复杂度： O(N log N) 或 O(N)
N 约束： 最大 10^5
晋级阈值： 750+/1000

🥇 Gold

受众： 进阶程序员
算法： Dijkstra、线段树、进阶 DP、网络流、LCA
典型复杂度： O(N log N) 到 O(N log² N)
N 约束： 最大 10^5 到 10^6

💎 Platinum

受众： 顶尖选手
算法： 高难组合数学、进阶数据结构、计算几何
顶尖选手有资格参加 USACO 决赛营，并可能入选 IOI 队伍（每年选 4 人）

7.1.4 评分

评分规则

每道题有多个测试点（通常 10–15 个），通过每个测试点得到部分分。

每道题约 333 分
总分：每场约 1000 分
具体细分因赛而异

「全对才行」的误区

人们以为必须完美解法才行，不是的！ 较简单情况（较小 N、特殊结构）的部分分可以让你达到晋级所需的 750+。尤其在 Bronze，有很多部分分策略。

部分分策略

若无法完全解决一道题：

解决小数据： 若 N ≤ 20，O(N!) 或 O(2^N) 的暴力通常能通过几个测试点
解决特殊情况： 若图是树，或所有值相等，先解决这些
始终输出某个答案： 若认为答案总是「YES」或某个常数，试几个测试点看看
优雅地超时： 确保部分解法不崩溃——TLE 比运行时错误好

7.1.5 竞赛时间管理

4 小时策略

前 30 分钟： 读完全部 3 道题。先别写代码，只是理解题目并思考。

确认哪道题看起来最简单
记下边界情况或特殊条件
开始在脑中形成思路

第 1-2 小时： 解最简单的题（通常是题 1 或题 2）。

实现、用样例测试、调试
争取至少一道题 100%

第 2-3 小时： 攻第二简单的题。

若卡住，考虑部分分做法

最后一小时： 要么完成第三道题，要么整合/调试已有的解法。

剩 30 分钟时：停止加新代码，专注测试和修 bug

读题

在写任何代码之前，花 5-10 分钟读每道题：

再读一遍约束条件（N、值的范围、特殊条件）
在纸上手动推演样例
思考：「这让我想到什么算法？」

卡住了怎么办

手动试小例子——能发现什么规律？
考虑更简单的版本：N=1 时怎么样？N=2？N=10？
想想：这是图论题吗？DP？排序/贪心题？
先写暴力——它可能够快，或帮助你理解结构

7.1.6 常见错误模式

1. 差一错误

// 错误：漏掉最后一个元素
for (int i = 0; i < n - 1; i++) { ... }

// 错误：访问 arr[n]——越界！
for (int i = 0; i <= n; i++) { cout << arr[i]; }

// 正确
for (int i = 0; i < n; i++) { ... }      // 0-indexed
for (int i = 1; i <= n; i++) { ... }     // 1-indexed

2. 整数溢出

int a = 1e9, b = 1e9;
int wrong = a * b;            // 溢出
long long right = (long long)a * b;  // 正确

3. 未初始化变量

int ans;  // 未初始化——有垃圾值！
// 始终初始化：
int ans = 0;
int best = INT_MIN;

4. 空输入/边界情况答案错误

// 若 n = 0 怎么办？
int maxVal = arr[0];  // n = 0 时崩溃！
// 检查：if (n == 0) { cout << 0; return 0; }

5. 用 `endl` 代替 `"\n"`

// 慢（每次都清空缓冲区）
for (int i = 0; i < n; i++) cout << arr[i] << endl;

// 快
for (int i = 0; i < n; i++) cout << arr[i] << "\n";

6. 未处理所有情况

仔细读题。「所有奶牛高度相同怎么办？」「N=1 怎么办？」测试这些边界情况。

7.1.7 Bronze 题型速查表

类别	描述	关键技术
模拟	按步骤执行指令	仔细实现；用数组/映射
计数	统计满足条件的元素数	循环、前缀和、哈希映射
几何	网格上的点、矩形	仔细处理索引，避免浮点误差
基于排序	排序并检查性质	`std::sort` + 扫描
字符串处理	操作字符序列	字符串索引、映射
Ad Hoc	巧妙观察，无标准算法	仔细读题，找规律（见第 7.3 章）

7.1.8 Bronze 题目完整分类

Bronze 题目分为以下 10 类，了解分类能帮你立即识别模式：

#	类别	描述	关键做法
1	模拟	按给定规则逐步执行	仔细实现，用数组
2	计数/迭代	统计满足条件的元素数	嵌套循环、前缀和
3	排序 + 扫描	排序，再用简单检查扫描	`std::sort` + 线性扫描
4	网格/二维数组	处理二维网格中的格子	仔细索引，BFS/DFS
5	字符串处理	操作字符序列	字符串索引、映射
6	暴力搜索	尝试所有可能	对小 N 用嵌套循环
7	几何（整数）	网格上的点、矩形	整数运算，不用浮点
8	数学/取模	数论、规律	取模运算、公式
9	数据结构	用合适的容器	Map、set、优先队列
10	Ad Hoc/观察	巧妙洞察，无标准算法	仔细读题，找规律——见第 7.3 章深入讲解

7.1.9 Silver 题目分类

Silver 题目需要更复杂的算法，以下是主要类别：

类别	关键算法	N 约束	所需时间
排序 + 贪心	排序 + 扫描、区间调度	N ≤ 10^5	O(N log N)
二分查找	二分答案、参数搜索	N ≤ 10^5	O(N log N) 或 O(N log² N)
BFS/DFS	最短路、分量、洪水填充	N ≤ 10^5	O(N + M)
前缀和	一维/二维区间查询、差分数组	N ≤ 10^5	O(N)
基础 DP	一维 DP、LIS、背包、网格路径	N ≤ 5000	O(N²) 或 O(N log N)
DSU	动态连通性、Kruskal MST	N ≤ 10^5	O(N α(N))
图 + DP	树上 DP、DAG 路径	N ≤ 10^5	O(N) 或 O(N log N)

USACO 的时间复杂度限制

这很关键：USACO 题目时间限制严格（通常 2-4 秒）。用这张表确定所需算法复杂度：

N（输入规模）	所需复杂度	允许的算法
N ≤ 10	O(N!)	排列暴力
N ≤ 20	O(2^N × N)	状压 DP、全搜索
N ≤ 100	O(N³)	Floyd-Warshall、区间 DP
N ≤ 1,000	O(N²)	标准 DP、逐对处理
N ≤ 10,000	O(N² / 常数)	有时优化后的 O(N²) 可行
N ≤ 100,000	O(N log N)	排序、BFS、二分查找、DSU
N ≤ 1,000,000	O(N)	线性算法、前缀和
N ≤ 10^9	O(log N)	二分查找、数学公式

⚠️ 经验法则： 每秒约 10^8 次简单运算。N=10^5 时，O(N²) = 10^10 次运算 → 超时。需要 O(N log N) 或更好。

7.1.10 如何补题——卡住时

「补题」是指竞赛中解不出的题，在看提示或题解后重新解。这是提高 USACO 水平最重要的技能。

补题步骤

第一步：先自己挣扎（30-60 分钟）

不要立即看题解，挣扎能建立直觉
试小例子（N=2, N=3），有什么规律？
想：「这道题闻起来像什么算法？」

第二步：获取提示，不是答案

只看题解的第一行：「这是 BFS 题」或「先排序」
只靠那个提示再试一次

第三步：读完整题解

慢慢读，理解算法为什么有效，不只是是什么
问自己：「我缺少了什么洞察？我为什么没想到？」

第四步：从零实现

不要复制题解代码，自己写
这才是真正学习发生的地方

第五步：找到自己的差距

问题是不认识算法类型？→ 多学题型模式
问题是实现？→ 练习更快编码，更好地学习 STL
问题是观察/洞察？→ 练习思考性质和不变量

7.1.11 USACO 模式速查表

模式	识别关键词	算法
网格最短路	「最少步数」「迷宫」「BFS」	BFS
每个格子到最近X的距离	「最近的火」「到最近X的距离」	多源 BFS
排序 + 扫描	「相近」「最大间隔」	排序后检查相邻对
二分答案	「最大化最小距离」「最小化最大值」	二分 + 检查
滑动窗口	「子数组和」「连续」「窗口」	双指针
连通分量	「区域」「岛屿」「组」	DFS/BFS 洪水填充
动态连通性	「合并组」「添加连接」	DSU
最小生成树	「最便宜地连接」「道路网络」	Kruskal
统计对数	「满足条件的对有多少」	排序 + 双指针或二分
一维 DP	「决策的最优序列」	DP 数组
网格 DP	「网格中的路径」「矩形区域」	二维 DP
活动选择	「最多不重叠事件」	按结束时间排序，贪心
前缀和区间查询	「[l,r] 的和」「二维矩形和」	前缀和
拓扑顺序	「先修课」「依赖顺序」	拓扑排序
二部图检查	「能否 2-染色」「有奇数环吗」	BFS 2-染色

7.1.12 精炼的竞赛策略

前 5 分钟至关重要

在写第一行代码之前：

读完全部 3 道题（先看标题和约束）
估计难度： 哪道最简单？（Bronze/Silver 通常是题 1）
注意关键约束： N ≤ ？时间限制，特殊条件
在脑中分类每道题（用上面的分类法）

部分分策略

即使无法完全解一道题，也要争取部分分：

📄 即使无法完全解一道题，也要争取部分分：

Bronze（N ≤ ~1000）：
  - 暴力 O(N²) 或 O(N³) 通常能通过几个测试点
  - 「解决小数据」做法：N ≤ 20 → 暴力

Silver（N ≤ 10^5）：
  - O(N²) 解法通常能通过 4-6/15 个测试点（部分分！）
  - 先实现暴力，再优化

始终：
  - 确保代码能编译并运行（无运行时错误）
  - 对每个测试点都输出一些东西，即使是错的
  - 错误答案好过崩溃

提交前调试清单

所有给定样例输出正确？
边界情况：N=1？
整数溢出？（值 > 10^9 时用 long long）
数组越界？（仔细设定数组大小）
循环中差一错误？
用的是 "\n" 而非 endl？
读取了正确数量的测试点？

本章总结

📌 核心要点

主题	要点
形式	每年 4 场，各 4 小时，3 道题
级别	Bronze → Silver → Gold → Platinum
评分	每场约 1000 分，晋级需 750+
部分分	对小数据的暴力也能得分
时间管理	先读完所有题，从最简单的开始
常见 bug	溢出、差一、未初始化变量

❓ 常见问题

Q1：USACO 使用什么语言？推荐 C++ 吗？

A：USACO 支持 C++、Java、Python。强烈推荐 C++——速度最快（Python 慢 10-50 倍），STL 丰富。Java 也可以，但比 C++ 慢约 2 倍且更冗长。本书全程使用 C++。

Q2：从 Bronze 晋级 Silver 需要多久？

A：因人而异。有编程背景的学生通常 2-6 个月（每周练习 5-10 小时）。完全初学者可能需要 6-12 个月。关键不是时间，而是有效练习——做题 + 读题解 + 反思。

Q3：竞赛期间可以上网查资料吗？

A：可以查通用参考资料（如 C++ 参考文档、算法教程），但不能查现成的 USACO 题解或获得他人帮助。USACO 是开放资源但独立完成的。

Q4：答案错误有罚分吗？

A：没有。USACO 允许无限次重新提交，只有最后一次提交算数。所以先提交部分正确的解法、再优化是明智的策略。

Q5：什么时候应该放弃一道题转向下一道？

A：若已经卡了 40+ 分钟且没有新思路，考虑转向下一道。但切换前先提交当前代码以获取部分分。若最后有时间再回来。

🔗 与其他章节的联系

第 2.1-2.3 章（第二部分）涵盖 Bronze 所需的所有 C++ 知识
第 3.1-3.11 章（第三部分）涵盖 Silver 的核心数据结构和算法
第 5.1-5.4 章（第五部分）涵盖 Silver/Gold 边界的图论
第 4.1-4.2、6.1-6.3 章（第四、六部分）涵盖 Silver/Gold 的贪心和 DP
第 7.2 章延续本章，深入讲解解题策略和思维方法
第 7.3 章深入讲解 ad hoc 题目——Bronze 中 10-15% 需要创造性观察而非标准算法的题

C++ 竞赛编程：USACO 学习指南