USACO金组

· · 个人记录

最近期中刚考完补发一篇blog

愚人节左右去打了USACO金组公开赛（？

USACO是美国信息学奥林匹克，分为铜级，银级，金级，铂金级

铂金级相当于NOI

USACO金组题目都出来了满分1000分，每道题1000/3分

T1是联合奶牛

T2是桥门

T3是排列

难度分别是 提高+/省选- 提高+/省选- 省选/NOI-

考试开始了，看了一下T1，直接prei，sufi记录上一个和下一个满足 aj=ai的位置j，一波主席树过掉

第二题题面过于恶心，还没有翻译，先去看T3

T3一共20个测试点，6个测试点是暴搜，当时断定想进铂金T3至少要通过10+个测试点（但其实不是qaq）

之后进入到了漫长的思考时间

大概想到了判定一个点在不在当前最大三角形内然后动态规划的做法，写了一个计算几何+动态规划的算法，然后调试

交上去只过了三个测试点qaq

考试只剩40分钟了，T2还一点没看。。。

赶紧去看第二题，题面虽然恶心，但直接一发统计边联通块再把每个边联通块当成点求最小生成树，过掉了

考试还有10分钟，调了调第三题，然后考试结束了

最终成绩：717

铂金晋级线：750

T3写个暴力都能得767分qaq

结果正解还和我的算法一样，应该是某个细节出问题了吧qaq

这次算是比较可惜，以后考试不能盲目追求完美，先保证暴力分数，凭自己实力也能晋级/获奖

当然因为对计算几何不太熟悉，所以编码慢，这也是需要加强的