【Plan B】#2
Silver第二波。然后就打算做Gold组了。USACO的Gold组有时候还是会有神题的。
其实Silver是有170+道的,Gold是190+
现在已完成:
50/50
[BZOJ1664 USACO]County Fair Events 参加节日庆祝
排序完贪心
[BZOJ4100 USACO]Bessie Goes Moo
首先我们把所有数Mod7储存,然后直接\(7^7\)的枚举
[BZOJ4101 USACO]Trapped in the Haybales
★做法就是乱搞,但是太神了说不出来。。。
[BZOJ4102 USACO]Bessie
其实预处理两两点对的距离+给点按价值排个序,然后就\(O(n^2)\)DP乱搞了
[BZOJ3888 USACO]Stampede
★预处理出每只羊出现的时间,然后按纵坐标从小到大观察(其实就是不重叠区间的维护,得OrzSet的写法
[BZOJ3890 USACO]Meeting Time
Dij的变种
[BZOJ3889 USACO]Cow Routing
双值最短路=裸最短路
[BZOJ3943 USACO]SuperBull
最大生成树,边权就是xor咯
[BZOJ3942 USACO]Censoring
★依次把S串添加进答案串C,当C的后缀=T时删掉(KMP可搞,可Hash容易写
[BZOJ3016 USACO]Clumsy Cows
差分序列+贪心修改
[BZOJ3017 USACO]Cow Breeds
差分序列,然后\(f(i,j)\)表示前i个数中A串的差分前缀和为j的方案数(B串的差分前缀和可以相减得到,压掉一维
[BZOJ3018 USACO]Distant Pastures
枚举起点跑SPFA
[BZOJ3315 USACO]Pogo-Cow
\(f(x,y)\)表示倒数第二次在x且倒数第一次在y时的最大价值。然后再倒过来做一遍
[BZOJ3300 USACO]Best Parenthesis
弄个栈
[BZOJ3301 USACO]Cow Line
预处理出个阶乘,没了
[BZOJ3298 USACO]Cow Checkers
★博弈论,自己推推?
[BZOJ3432 USACO]Cross Country Skiing
转成MST
[BZOJ3433 USACO]Recording the Moolympics
★右端点从小到大排序,能放就放
[BZOJ3893 USACO]Cow Jog
弄一个队列,从左到右加牛,维护牛群
[BZOJ3892 USACO]Marathon
弄个\(n^2\)的DP
[BZOJ3891 USACO]Piggy Back
最短路后枚举汇合地点
[BZOJ3540 USACO]Fair Photography
★把0看做-1,前缀和处理,那么中间一段平衡的区间,两段的前缀和应该是一样的
[BZOJ3479 USACO]Watering the Fields
又是MST
[BZOJ3314 USACO]Crowded Cows
从左到右扫一遍,从右到左扫一遍
[BZOJ3431 USACO]Bessie Slows Down
拍完序后照做就行
[BZOJ3299 USACO]Corn Maze 玉米迷宫
最短路或BST
[BZOJ2015 USACO]Chocolate Giving
最短路
[BZOJ2100 USACO]Apple Delivery
又是最短路
[BZOJ3402 USACO]Hide and Seek 捉迷藏
哭了还是最短路
[BZOJ3403 USACO]Cow Line 直线上的牛
一个deque解决
[BZOJ3412 USACO]Music Notes乐谱
二分查找
[BZOJ3410 USACO]Selfish Grazing 自私的食草者
★右端点从小到大排序,左端点从大到小排序,贪心选
[BZOJ3449 USACO]Secret Code
DP
[BZOJ4096 USACO]Milk Scheduling
★弄个堆,按截止时间加入,每个时间贪心地选一个最大价值的
[BZOJ3480 USACO]Mooo
先求出每个位置的声音总和,然后无限背包
[BZOJ3296 USACO]Learning Languages
并查集
[BZOJ2101 USACO]Treasure Chest 藏宝箱
DP,然后滚动数组
[BZOJ2017 USACO]硬币游戏
DP
[BZOJ3538 USACO]Dueling GPS
最短路
[BZOJ3297 USACO]Forgot
DP+字符串
[BZOJ3411 USACO]Bobsledding 高山滑雪
★弄个栈,然后不断维护转折点
[BZOJ2020 USACO]Buying Feed, II
显而易见的贪心
[BZOJ2021 USACO]Cheese Towers
DP背包。由贪心可知不小于\(k\)的先放,然后小的先放。
[BZOJ3405 USACO]Grazing2 移动牛棚
DP,相邻的距离只有d和d+1两种可能
[BZOJ2016 USACO]Chocolate Eating
二份答案(看翻译后的结果貌似是能不按顺序吃的,可原题貌似有说得按顺序吃。。。
[BZOJ3313 USACO]Farmer John has no Large Brown Cow
字符串的一道恶心题。。。(字符串长度不大于10,所以可以用个longlong存下来
[BZOJ3539 USACO]Odometer
★是数位DP没错,可还要处理2233这种算了两次的特殊情况。。。
[BZOJ2102 USACO]The Trough Game
枚举所有答案\(2^n\),然后判断合不合法就行
[BZOJ4097 USACO]Vacation Planning
Flody的最短路
[BZOJ3448 USACO]Auto-complete
建棵Trie然后dfs序列然后二分查找(此题无限RE,连官方std也是。。。交了个他人Pascal版本的。。。
Update 8.25:
B站月榜(云神的号我重新刷回了前100)ᕕ( ᐛ )ᕗ
没像上次一样,这次不手贱地交完了
暑假刷题还是太慢了啊。。。平均下来每天3道的速度。。。