BZOJ上的USACO 第一弹

听说刷BZOJ上的USACO题目比较涨rank,于是我也开始了开心的划水生活~在这里贴一些题目的代码和思路,如果感觉比较好的题目用★标注出来,也会单独写写。

现在做了几题:

50/50

终于填完了,写题写的好慢啊QAQ。再弄个第二弹。

1599: [Usaco2008 Oct]笨重的石子

不再赘述。反正是个傻逼题。

1603: [Usaco2008 Oct]打谷机

同上

★1600: [Usaco2008 Oct]建造栅栏

四边形存在的条件:任意三条边之和大于第四条边。等价于任意一条边不超过周长的1/2。可以dp。

★1601: [Usaco2008 Oct]灌水

最小生成树,建立超级源和超级汇,注意连边。

1602: [Usaco2008 Oct]牧场行走

树上点对距离,直接用LCA处理。

1610: [Usaco2008 Feb]Line连线游戏

计算几何水题。

1625: [Usaco2007 Dec]宝石手镯

01背包裸题。

1606: [Usaco2008 Dec]Hay For Sale 购买干草

直接dp就可以了,刚学了bitset优化,就试了一下。

★1607: [Usaco2008 Dec]Patting Heads 轻拍牛头

就是一个筛法,和素数筛差不多,然而弱有点忘了筛法怎么打了,所以标注一下。题意不是很明确,用筛法求出这n个数中每个数有多少个约数,有个地方需要注意就是输出的时候需要减去自身。

1618: [Usaco2008 Nov]Buying Hay 购买干草

完全背包裸题,但是一边和学长聊天一边写,出了不少bug。以后写题还是要有紧迫感。

初始化dp[0]=0,其余均为Inf.因为不知道最后可能买了多少干草,直接把H+max(p)就好啦。

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

dp[i][j]表示排到第i头牛,以j结尾的答案。枚举合法的上一个位置的数字和当前位的数字,递推一下。

★1679: [Usaco2005 Jan]Moo Volume 牛的呼声

找规律,发现排序后,a[i-1]到a[i]的距离被计算的次数就是这条线段左边和右边的端点数目相乘。算是个乱搞吧。

★1657: [Usaco2006 Mar]Mooo 奶牛的歌声

单调栈。正的维护一遍,反的再维护一遍。

1631: [Usaco2007 Feb]Cow Party

正反建两次图跑最短路,然后统计答案。update:有人说spfa会T,但是我还是写了,以后需要注意一下范围。毕竟spfa的复杂度。有点玄学。

1621: [Usaco2008 Open]Roads Around The Farm分岔路口

记忆化搜索。但是不是很会算复杂度。。。贴个代码吧。

1634: [Usaco2007 Jan]Protecting the Flowers 护花

贪心一下,这种题目,就考虑相邻两头牛互换下是否变优的情况进行排序。

1611: [Usaco2008 Feb]Meteor Shower流星雨

bfs,需要注意这个第一象限是没有上边界和右边界的。因为这个wa了一次。

★1612: [Usaco2008 Jan]Cow Contest奶牛的比赛

一开始想成了Tarjan后来发现不对,直接Floyd算出点与点之间可达的情况就好了。然后统计一下每个点可以到达的点和可以到达他的点的和是不是等于n-1,如果是这个点的位置就确定了。

1613: [Usaco2007 Jan]Running贝茜的晨练计划

dp水过,dp[i][j]对应第i分钟j为疲劳值使的答案,那么讨论一下,若j>0,那么一定只能从dp[i-1][j-1]+d[i]递推归来。若j=0的话,我可以这dp[i-j][j]递推过来,或者dp[i-1][0],因为我可以多休息几分钟。。。

★1614: [Usaco2007 Jan]Telephone Lines架设电话线

二分答案然后跑最短路,设大于mid的边权为1,不大于的为0.看最短路是不是超过k。注意一个坑点,我是二分的数组下标,但是答案可能为0,所以二分的时候L从0开始。

1626: [Usaco2007 Dec]Building Roads 修建道路

裸最小生成树。

★1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

拓扑排序后dp,p1[i]是从起点到i点的路径方案数,看上去这个就是我们要求的东西,但是题意的意思是所有边中被经过次数最多的一条,那么我们必须要保证i->j在我们经过的方案里才可以计数。那么反向再来一遍就好了。貌似和之前一道题很像,都是预处理出从两个点各自到两个端点的方案数,然后相乘计算出这条边的答案。不贴代码了QAQ。

1724: [Usaco2006 Nov]Fence Repair 切割木板

哈夫曼树。

1725: [Usaco2006 Nov]Corn Fields牧场的安排

状压dp。

1726: [Usaco2006 Nov]Roadblocks第二短路

次短路,用spfa维护一下。

★1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛

煞笔题,结果我没理解路线的意思,以为走过的点就不能再走了。然后就写了好久,然后发现看错题后,就随便写了个搜索加剪枝。。。

1617: [Usaco2008 Mar]River Crossing渡河问题

随便dp一下,注意要加上每次返回的时间,最后那个减去。

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

bfs一下。

1677: [Usaco2005 Jan]Sumsets 求和

类似于完全背包。

1636: [Usaco2007 Jan]Balanced Lineup

没有修改的RMQ问题,开两个ST表即可。

1622: [Usaco2008 Open]Word Power 名字的能量

n,m太小啦,暴力枚举。

1623: [Usaco2008 Open]Cow Cars 奶牛飞车

考虑贪心,在一个车道上车速小的车肯定放在靠前的位置。所以按照车速从小到大排序,每次加入车的时候一定是加入车数更小的车道内。

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

floyd求出来任意点对之间的最短路后按照题目顺序走一走求和即可。

★1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典

是个关于字符串匹配的dp题目。因为目标串和匹配的串长度较小,所以只需要一位位暴力匹配就好了。代表以第i个字符为止,最少需要去掉的字母的数目。假设我们从第i个字符往前推能够找到一个匹配的单词,假设长度为len。那么,cnt是我们在匹配过程中发现的不匹配的字符数目。

★1628: [Usaco2007 Demo]City skyline

单调队列,复习一下单调队列还是很有必要的。思路就是维护一个单调递增的队列,碰到比队尾高的就加进来,答案加1.如果比队尾低的,就不断地删去队尾元素,直到找到比他低的(或和他相同)。比他低的话就加1.因为在这之前没出现过这个高度。

★1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

非常妙。。。链接

 

★1635: [Usaco2007 Jan]Tallest Cow 最高的牛

类似于某道叫做礼物的cf题目,就是考虑维护一个差分序列sum。当a能看到b的时候,其实a,b之间的关系我们并不知道,但是我们唯一知道的是a和b之间的高度都比a和b小。我们可以用sum[a+1]–,sum[b]++。这样就可以清楚的把这一段的高度情况表示出来。最后每个高度计算出sum的前缀和加上H即可。这样的话就是O(n)复杂度了。

1637: [Usaco2007 Mar]Balanced Lineup

先排序,把0种族看成1,1种族看成-1.那么如果前缀和sum[L-1]和sum[R]相等那么就意味着L-R这一段区间是平衡的。用一个map记录一下每个前缀和第一次出现的位置,扫一遍。

1639: [Usaco2007 Mar]Monthly Expense 月度开支

二分答案,验证是否可以分为m个月。验证的时候扫一遍就可以了。

1640: [Usaco2007 Nov]Best Cow Line 队列变换

貌似以前做过。。。就是贪心的从两头取,然后遇到两头相同就继续往下一个比较,直到可以区分。发现自己写这种字符串题目总是细节有Bug….

1708: [Usaco2007 Oct]Money奶牛的硬币

完全背包。

1652: [Usaco2006 Feb]Treats for the Cows

水水的区间dp。

1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏

floyd预处理一下。

1642: [Usaco2007 Nov]Milking Time 挤奶时间

先按照时间的顺序排序,然后dp。dp方程:且满足

1643: [Usaco2007 Oct]Bessie’s Secret Pasture 贝茜的秘密草坪

dp一下就可以了。

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

排个序,二分验证一下就没了。

3384: [Usaco2004 Nov]Apple Catching 接苹果

简单dp。

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

写了个辣鸡BFS。。。加入队列的时候再考虑方向一维就可以了。

1646: [Usaco2007 Open]Catch That Cow 抓住那只牛

写了个辣鸡bfs。。。发现数组开小了。

1650: [Usaco2006 Dec]River Hopscotch 跳石子

写了个辣鸡二分加贪心,结果没出样例,发现需要排序。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注