NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#1

NanoApe posted @ 2015年8月04日 14:54 in 蒟蒻不做题提前退役 , 1010 阅读

听说屯题刷更爽?

先做USACO的Silver组题。全程拿Greens的号测。

现在已完成:

50/50

[BZOJ1601 USACO]灌水

裸MST

[BZOJ1602 USACO]牧场行走

裸树上点对距离

[BZOJ1599 USACO]笨重的石子

裸DP

[BZOJ1600 USACO]建造栅栏

裸DP

[BZOJ1603 USACO]打谷机

一个dfs即可

[BZOJ1610 USACO]连线游戏

枚举两两点的斜率,然后快排

[BZOJ1625 USACO]宝石手镯

背包DP

[BZOJ1606 USACO]购买干草

bitset优化裸背包?

[BZOJ1607 USACO]轻拍牛头

按权值扫一遍

[BZOJ1609 USACO]麻烦的聚餐

简单DP

[BZOJ1618 USACO]购买干草

背包DP

[BZOJ1679 USACO]牛的呼声

扫一遍,维护后缀和

[BZOJ1657 USACO]奶牛的歌声

扫一遍,签到题

[BZOJ1631 USACO]Cow Party

正反边做两次最短路

[BZOJ1621 USACO]Roads Around The Farm 分岔路口

记忆化搜索就行

[BZOJ1611 USACO]Meteor Shower 流星雨

跑一遍最短路或者搜索+最优性剪枝

[BZOJ1626 USACO]Building Roads 修建道路

MST

[BZOJ1614 USACO]Telephone Lines 架设电话线

二分答案后跑最短路,大于答案的路长设为1,小于等于答案的路长设为0,跑最短路看是否超过K。

[BZOJ1616 USACO]Cow Travelling 游荡的奶牛

直接DP

[BZOJ1612 USACO]Cow Contest 奶牛的比赛

★把胜负关系看成单向边,用Flody求出任意两点互连情况,然后判定(若能到达这个点的点数+这个点能到达的点数=n-1即名次确定)

[BZOJ1677 USACO]Sumsets 求和

直接DP不解释

[BZOJ1636 USACO]Balanced Lineup

就是你了线段树!

[BZOJ1617 USACO]River Crossing 渡河问题

\(n^2\)的DP

[BZOJ1628 USACO]City skyline

贪心从左到右扫一遍

[BZOJ1633 USACO]The Cow Lexicon 牛的词典

★从后往前DP,\(f[i]\)表示\(s[i..n]\)最少删掉几个字母就能匹配

[BZOJ1635 USACO]Tallest Cow 最高的牛

★差分序列,就是指\(f[i]=k[i]-k[i-1]\)中\(f[i]\)的序列,假如a能看到b则\(f[a+1]--,f[b]++\)

[BZOJ1682 USACO]Out of Hay 干草危机

其实就是做MST

[BZOJ1688 USACO]Disease Manangement 疾病管理

枚举K种病的集合,然后看哪种集合能选最多的牛

[BZOJ1648 USACO]Cow Picnic 奶牛野餐

K次dfs,\(O(kn)\)的复杂度

[BZOJ1637 USACO]Balanced Lineup

差分序列上场!

[BZOJ1624 USACO]Clear And Present Danger 寻宝之路

Flody后直接算

[BZOJ1639 USACO]Monthly Expense 月度开支

二分答案后直接贪心选

[BZOJ1620 USACO]Time Management 时间管理

从后往前安排工作

[BZOJ1634 USACO]Protecting the Flowers 护花

序列贪心,按\(t/d\)的顺序从小到大排列。

[BZOJ1629 USACO]Cow Acrobats

序列贪心,按\(w+s\)的顺序从小到大排列。

[BZOJ1660 USACO]Bad Hair Day 乱发节

用栈从左到右扫一遍。

[BZOJ1651 USACO]Stall Reservations 专用牛棚

答案就是最多同时喝水数,把每个区间分成开始喝和停止喝两种操作

[BZOJ1627 USACO]穿越泥地

最短路

[BZOJ1646 USACO]Catch That Cow 抓住那只牛

弄个DP

[BZOJ3391 USACO]Tree Cutting 网络破坏

dfs一遍看子树大小

[BZOJ3393 USACO]Laserphones 激光通讯

最少转弯路。其实就是最短路。

[BZOJ3404 USACO]Cow Digit Game 又见数字游戏

N范围不大,可以预处理出所有状态的博弈态。

[BZOJ2014 USACO]Chocolate Buying

贪心,先买最便宜的

[BZOJ1674 USACO]Part Acquisition

其实就是最短路

[BZOJ1655 USACO]Dollar Dayz 奶牛商店

DP搞一搞就行

[BZOJ1662 USACO]Round Numbers 圆环数

一个数位DP

[BZOJ1644 USACO]Obstacle Course 障碍训练课

同BZOJ3933

[BZOJ1643 USACO]Bessie's Secret Pasture 贝茜的秘密草坪

预处理出\(f[i,j]\)(表示i个正方形数能组成j吗)

[BZOJ1623 USACO]Cow Cars 奶牛飞车

排序完小的先跑

[BZOJ3390 USACO]Bad Cowtractors 牛的报复

最大生成树=MST


登录 *


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