NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#2

NanoApe posted @ 2015年8月12日 23:43 in 蒟蒻不做题提前退役 , 839 阅读

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道的速度。。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter