USACO公开赛难度高吗这个技巧可能让你题题都会-唯寻国际教育

随着编程越来越普及，很多学员开始接触到了USACO竞赛，今天为大家分析一道2020年USACO公开赛真题，顺便介绍一个“四部解题法”。

USACO公开赛难度高吗四步解题法了解一下内容图片_1

USACO公开赛：美国计算机奥林匹克竞赛

USACO竞赛指的是美国计算机奥林匹克竞赛。是一项为国际学校生或者年龄更小的学员提供的在线竞赛，旨在锻炼学员用计算机编程解决问题的能力。它的全称是USA Computing Olympiad。竞赛在家里通过网上进行。与其它竞赛不同，USACO没有学校和地区级的限制，任何学员都可以通过互联网参加。

USACO公开赛在中国的普及度并不高，是相对冷门的竞赛。这意味着参赛选手少，获奖选手也少，含金量自然更高。

值得一提的是USACO在每年12月至次年4月间，会举办4场比赛，参赛者可在同一年内多次参赛。与其他全球性赛事出分、晋级最少需要10天不同，USACO采用机器评分机制，代码提交后系统会自动给出评分。放榜也快，所以申请季的同学说不定也来得及参加。

该竞赛分为铜、银、金和铂金4级，难度依次递增。首次参赛需从铜级开始，达到一定分数可晋级下一级比赛。如果你拿到满分（或接近满分），系统会直接显示晋级，你可以在该场比赛的时间内继续挑战晋级，实力足够的情况下一场比赛就可升至铂金级；其他同学则只需等待3天左右便可知道自己的晋级结果。

2020年USACO公开赛真题解析

今年的题目是以新冠病毒为引子出题的，这里我们先找一道铜牌组的题目解析一下：

USACO公开赛难度高吗四步解题法了解一下内容图片_2

英文不好的学员也不用担心，USACO公开赛的考试非常贴心，正式考试的时候可以选择中文版本的。

在正式解析题目前，想先向大家介绍一种解题方法，这种方法出自于大数学家G-波利亚（G-Polya），他在成名以前是一名中学数学导师，计算机的鼻祖冯诺伊曼就曾经是他的学员，而当今的数学界天才人物陶哲轩，小时候也曾用这种方法来准备奥数比赛。这是一种简单，靠谱，稳定的解决问题的方法，叫做四步解题法。

理解题目

答题的时候要抓关键信息点，反复读题审题，既综合全局，又反复推敲，从题目的字里行间挖掘出一些隐含的信息，利用这些隐含信息，梳理解题思路和建立辅助方程。能用自己的话把题目讲一遍就更好了。

构思解题思路

干扰信息往往与解题的必备条件混杂在一起，若不及时识别它们，就容易受骗上当误入歧途，只有大胆地摒弃干扰信息，解题才能顺利进行。

用程序表达思路。

这一步就非常考验耐心了。

拿到题目后，首先要认真读一遍题目，从字面意思了解题目。这样题目中的已知，未知以及给出的条件等都印在了你的脑中。最重要的是，要搞清楚这道题目求的是什么，这个就是目标。简单概括的话，这道例题中给出了当前牛棚中所有牛的生病状态，也就是说，我们明确知道某一头牛到底是感染了还是没有感染。题目给出的条件是，牛之间的感染是有一个感染半径的，低于这个半径的牛之间会相互传染，而大于这个半径的牛不会相互感染。

最终题目要求的未知量是，在初始状态下，最少有几头牛是被感染的。如果你能够按照上述这样，明确的概括出已知，条件和未知，那么基本上这道题目算了理解了。

接下来，就给出这道USACO公开赛题目的代码供大家学习参考，以下是C++ 版本的实现代码：

#include USACO公开赛难度高吗这个技巧可能让你题题都会内容图片_3