AC. 梦想

frank_c1

USACO Dec. 16 通关记

发布于2016年12月20日 | 暂无评论 | 851阅读 | 比赛经历

第一次打USACO月赛。赛中晋级制赞,实时反馈制赞。然而题目难度不敢恭维啊。

Bronze

square : 界出最小覆盖矩形的长和宽取max就是正方形的边长。

blocks : 注意到每个字母贡献独立。每张卡片取较多数目的那一面就好。

cowsignal : 数组的基本操作。

Silver

haybales : 二分/STL均可。

citystate : 暴力记录所有状态统计答案即可。注意题意注意特判。

moocast : 根据题意连边后一遍传递闭包。

Gold

moocast : 最小生成树。

checklist : f[i,j,0/1]表示当前完成前者i个,后者j个,位置在0/1的最小花费。注意边界。

laser : BFS一波。

Platinum

triangles : 考虑容斥。可以转化为求一条线段的某一侧有多少点和两条线段夹着多少点。后者极角排序解决。

team : 先排序,f[i,j,k]表示现在考虑前者前i个,后者前j个,选出k个的方案数。

roboherd : K短路模型。不过数据范围较大,A*无法通过。论文方法,可持久化可并堆上之。可能需要卡卡空间。

就贴一波Platinum的代码吧。