【原创】USACO 2020-2021赛季试题解析系列(2月晋级赛)

发布于 2021-03-03 09:38


大家好,USACO 2月赛赛题解析如期而至!截至北京时间周二晚,USACO 本赛季第三场晋级赛正式结束,  满分同学会当场晋级,没有当场晋级的同学可以耐心等待一周之内出成绩。


【导语】这个月的赛题依然重视考查参赛者的题目理解能力、观察推理能力和算法建模能力,不少赛题代码量都挺小的,但是不太容易想到。有思路后实现起来比较容易的,用一个字描述就是“活”。参赛者刚接触了一些算法后,对于比较模板型的题目解决起来相对容易,但是想在实战中取得好成绩,需要经过时间磨砺的。所以千万不要等到赛前才火急火燎的开始准备,短时努力下想能升金升铂金,这样“雄心勃勃的计划导致你失机会,不能以参加lucky draw的心态来面对竞赛更不要轻易拿极少数天才型选手的学习经历往自己身上套此外,验丰富教练指导固能大大提升学习效率,但是也不能让选手一口气吃成个胖子,所以提早规划,给自己预留充分时间很重要。


下面来说说Benjamin Qi大佬, 本月他全面回归,各个级别都有他出的题,尤其是金级和铂金组,每道题都有他的身影,能者多劳,命题工作量巨大啊。


本次金级组居然第二第三题连考两道动态规划题(DP),以往是必考一道,同学们DP要好好学,学不好DP就过不了Gold。


本月比赛整体难度和上个月相当,更多内容,请参考下文解析(题解图片可放大阅读)。


本赛季截止当前德儿塔学生累计铂金排名前5强1人,10人晋级铂金,22人晋级黄金,银级若干(人数较多,不一一统计),全部成绩等待官网公布结果。群众的眼睛是雪亮的,成绩不是靠口头喊出来的,而是需要一步一步长期耕耘才能结出硕果。能够在官方题解公布之前,原创各大组别题解的机构,是真硬核!



以下内容是各大级别的赛题解析,供同学们参考交流。想要咨询参赛和备考冲刺计划的同学,可以扫描文末二维码,添加老师微信获取。



第1

题目解析:

模拟题,逐条读入数据模拟计算每头牛的生肖偏移量即可。

(下方代码可以左右滚动阅读)

int pivot = cowId[s];if (previous) {    if (cowZodiacId[pivot] > cowZodiacId[id]) {        offset[id] = offset[pivot] - (cowZodiacId[pivot] - cowZodiacId[id]);    } else {        offset[id] = offset[pivot] - (cowZodiacId[pivot] - cowZodiacId[id] + 12);    }} else {    if (cowZodiacId[id] > cowZodiacId[pivot]) {        offset[id] = offset[pivot] + (cowZodiacId[id] - cowZodiacId[pivot]);    } else {        offset[id] = offset[pivot] + (cowZodiacId[id] - cowZodiacId[pivot] + 12);    }}





第2

题目解析:

每次加入一头牛,判断一下该牛是否舒服,如满足上下左右相邻位置有3头牛,那么答案加1。接着判断是否导致该头牛的上下左右相邻位置的牛变得舒服或从舒服变为不舒服。

void add(int i, int j) {    cow[i][j] = 1;
if (cnt[i][j] == 3) ans++;     cnt[i - 1][j]++; if (cow[i - 1][j]) { if (cnt[i - 1][j] == 3) ans++; else if (cnt[i - 1][j] == 4) ans--; } // 其余位置处理类似}




第3

题目解析:

本题主要考察思维,想到思路后,代码实现相当的简单。不难发现,如果是顺时针,那么右转次数一定比左转次数多,反之,左转次数多。

int cnt = 0;for (int j = 1; j <= len; j++) {    if (turnright(j)) cnt++;    if (turnleft(j)) cnt--;}if (cnt > 0)    cout << "CW" << endl;else    cout << "CCW" << endl;




第1题

题目解析




第2题

题目解析:



第3

题目解析:




第1

题目解析:




第2

题目解析:

本题是一道标准的区间DP,Gold级别很久没有碰到代码实现如此方便的赛题了,几行代码即可搞定。

for (int i = n; i > 0; i--) {    f[i][i] = 1;    for (int j = i + 1; j <= n; j++) {        f[i][j] = f[i][j - 1] + (a[i] != a[j]);        for (int k = i; k < j; k++) {            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);        }    }}



第3

题目解析:


你的同学都来自哪里?

学生遍布Exeter、Andover、Deerfield、WRA、Fay等美国学校和包玉刚、星河湾、复旦附中、上外附中、深中、深外、深国交、贝赛斯、UWC常熟、人大附中、顺义国际等国内中学。


对于含金量和竞争力如此高的赛事,你是否已经动了心?


德儿塔USACO教练团队为你量身定制竞赛方案,高效备赛。USACO各个级别辅导课程,C++/Java编程语言均可,就等你来!