USACO水题记录

10

UPD: 2018.8.27 发现写水题没有意思,还是要学点新东西,已弃坑(真香)。

找到个一个吉利的题表 Link,基本上就顺着做吧。

BZOJ1622 [Usaco2008 Open]Word Power 名字的能量

开始算错复杂度,觉得$O(nm\cdot 1000)$不对,还想了半天,发现会一个$O(nm\cdot 30 \cdot log 1000)$的貌似更优秀。后来发现$O(nm\cdot 1000)$没毛病,就直接暴力了。

BZOJ1613 [Usaco2008 Jan]Running贝茜的晨练计划

$f[i][j]$表示第$i$分钟疲劳度为$j$的最远距离。$f[i][j]$更新$f[i+1][j+1]$和$f[i+j][0]$。因为不动也可以所以$f[i][0]$更新$f[i+1][0]$,最后输出$f[n+1][0]$。

BZOJ1623 [Usaco2008 Open]Cow Cars 奶牛飞车

贪心,sort就好。我竟然没看到还有车道这种东西…

BZOJ1628 [Usaco2007 Demo]City skyline

单调栈。最开始设答案为$n$。遇到栈里面相同高度,$ans$减一。

BZOJ1633 [USACO2007 Fe]牛的词典

DP,f[i]表示前$i$位的答案,初始$f[i]=f[i-1]+1$设$t$表示从$i$往前与$j$匹配的最小花费,$f[i]=min(f[i],f[i-cost-len]+cost$)。

BZOJ1635 USACO2007 Jan 最高的牛

差分

BZOJ1636 [USACO2007 Jan] Balanced Lineup

ST表,开16就行了,开20被卡常。

BZOJ1637 [USACO2007 Mar] Balanced Lineup

sort一下,然后记$f$为1比0多$i$个时最左边的牛,算一下。

BZOJ1638 [USACO2007 Mar] 奶牛交通

对于边$(a,b)$,答案是从入度为$0$的点访问到$a$的次数乘从从$n$访问到$b$的次数。计算一个点背访问的次数时可以DP。$f[i]=\sum_{\exists~edge(j,i)}f[j]$,特殊地,对于入度为$0$的点,$f[i]$为1。正着DFS一遍,反着DFS一遍,然后乘起来取max。

BZOJ1639 [USACO2007 Mar]月度开支

二分。

BZOJ1640 [USACO2007 Nov] 队列变换

贪心。如果队头的元素和队尾相同,比较正着的字典序和反着的字典序的大小。

可以暴力,SA或者SAM。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*