美国计算机竞赛 USACO 2月竞赛结果已在官网发布,
在本次竞赛中,必果学员们都取得了优异的成绩,
两名同学晋升Platinum,
六名同学晋升Gold,
两名同学晋升Silver,
恭喜晋级的同学们!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

 

本文福利

 

扫描小助手二维码即可领取

USACO赛题完整版参考代码和竞赛资源包哦!

此外,必果学院还有USACO备赛群等你加入!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

USACO 2月竞赛结果

本轮竞赛,中国地区共有1244人参加

金级竞赛中获得800分及以上即可晋级铂金;

银级竞赛中获得700分及以上即可晋级金级;

铜级竞赛中获得700分及以上即可晋级银级。

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

USACO 2月赛题解析

Bronze赛题

01

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
枚举三元组,判断是否平行坐标轴,计算面积即可

注意:两条边向量的叉积是三角形有向面积的两倍

02

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
将一个连续不同段一起变换就是最有策略

找到所有最长连续不同段即可

03

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
每个位置可能的移动位置只有100个

所以一百步之后一定有循环节

找到每个位置的循环节即可

Silver赛题

01

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
一组点会在一个圈里跑

只要把每组求一次即可

02

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
枚举每个直角顶点

计算所有与之平行于x轴的点可以和所有与之平行于y轴的点进行组合

获得合题意的三角形

所以x和y分别计算即可

03

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
找到一条欧拉回路或欧拉路径使得路径上所有点都到12点

从每个点开始dp即可

Gold赛题

01

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
我们发现既定有限定a b x

通过所有对b有限制的a的具体开会时间得到b的时间

跑拓扑序列即可

02

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
可以按l排序或者按r排序,两种情况各有优势

第一种情况 由于有区间乘2操作 只能用线段树维护 大常数

第二种情况 可以用树状数组维护 极小常数

这里采取第一种情况

如果按l排序

考虑新加一个区间[l, r]

1. 加入以后能形成一个新的独立区间的

  • 对于区间个数 r点增加了 这样的区间个数 + 1 个
  • 对于区间贡献 r点增加了 这样的区间贡献 + r点增加的个数的贡献

2. 加入以后不能形成新的独立区间 但是结尾是r的

  • 对于区间个数 r点增加了 这样的区间个数 个
  • 对于区间贡献 r点增加了 这样的区间贡献 的贡献

3. 对于加入以后不能形成独立区间 并且结尾不是r的

  • 对于区间个数 这样的区间 其结尾点区间个数*2
  • 对于区间贡献 这样的区间 其结尾点区间贡献*2

如果按r排序

考虑新加入一个区间[l,r]

1. 加入以后形成新的独立区间

  • 对于区间个数 r点增加了 这样的区间个数 + 1 个
  • 对于区间贡献 r点增加了 这样的区间贡献 + r点增加的个数 的贡献

2. 加入以后不能形成独立区间 但是结尾是r的

  • 对于区间个数 r点增加了 这样的区间个数 个
  • 对于区间贡献 r点增加了 这样的区间贡献 的贡献

不存在第三种情况

03

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
考虑到能整除边数量的数才可能合法

对每个这样的数dp即可

Platinum赛题

01

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
每颗子树上传无法匹配的链

如果没有就上传满足下面情况的最长链

1:没有匹配

2:匹配了一条>=Minlen的链

如果子树无法匹配的链 > 1,则不能划分。

判断根是否有无法匹配的链,如果有,则不能划分。

02

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
这样的三角形中必至少有一条边斜率为1或-1

存在情况:有可能这样的三角形中有一条或两条斜率为1或-1

分别统计即可

03

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
赛题解析
必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
如果按l排序,考虑新加一个区间[l, r]

1. 加入以后能形成一个新的独立区间的

  • 对于区间个数 r点增加了 这样的区间个数 + 1 个
  • 对于区间贡献 r点增加了 这样的区间贡献 + r点增加的个数 的贡献

2. 加入以后不能形成新的独立区间 但是结尾是r的

  • 对于区间个数 r点增加了 这样的区间个数 个
  • 对于区间贡献 r点增加了 这样的区间贡献 的贡献

3. 对于加入以后不能形成独立区间 并且结尾不是r的

  • 对于区间个数 这样的区间 其结尾点区间个数*2
  • 对于区间贡献 这样的区间 其结尾点区间贡献*2

只有情况一中的贡献是有修改的

情况二中只是单纯的求和

情况三中是单纯的翻倍

所以我们可以做到递推

 
以上就是USACO2020年2月的赛题解析,
想要领取完整版参考代码的同学,
扫描下方的微信二维码,
添加小助手为好友,
发送“USACO 2月”即可。

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!

希望你们都能在竞赛中达到自己期望的等级!

必果学员在美国计算机竞赛USACO 2月比赛中2名学生晋级铂金,6名学生晋升金级!
http://www.biggerlab.com/contests/31b7c94c50/

http://www.usaco.org/

帮我点个“在看”再走吧!


0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注