bzoj-USACO除草计划A

我已经做了30/30


1229: [USACO2008 Nov]toy 玩具

这题是餐巾计划的加强版,三分性质的证明见VFK博客

我们先三分玩具数总数,然后考虑对于每次使用玩具先暂时存入一个队列

当我们发现现有的玩具不够的时候,从队列末尾查找能否慢洗,可以的话就慢洗

不然就找快洗,这个过程可以用三个队列模拟出

这样时间复杂度就是O(n\log E)


1230: [Usaco2008 Nov]lites 开关灯

线段树裸题,维护一个标记和区间和即可,时间复杂度O(n\log n)


1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛

裸的LIS


1699: [Usaco2007 Jan]Balanced Lineup排队

裸RMQ即可


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

切割的过程反过来思考就是合并的过程,然后就是合并果子了。


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

状压DP(我状压姿势真是太弱了QAQ)

dp[i,j]表示第i行状态为j的答案

直接暴力转移dp[i,j]=\sum dp[i-1,k]

枚举的时候判断状态是否合法即可,时间复杂度O(n^{2}\times 2^{m}\times 2^{m})

忘记对答案取模wa了好几发QAQ


1726: [Usaco2006 Nov]Roadblocks第二短路

次短路,跑SPFA的时候顺带维护一下即可


1231: [Usaco2008 Nov]mixup2 混乱的奶牛

dp[i,j]表示现在选了奶牛j,当前已经选择的奶牛状态为i的方案数

dp(i,j)=\sum_{k\in i'} dp(i',k)

其中i'代表删去j的集合,时间复杂度为O(2^{n}\times n^{2})


1572: [Usaco2009 Open]工作安排Job

带修改的贪心,能选就选,不能选就和当前已经选的最小值进行比较择优选择。

时间复杂度O(n\log n)


1232: [Usaco2008Nov]安慰奶牛cheer

模拟样例发现每条边的边权都被算了两次,两端各被算了一次,于是按照这个重新赋值边权,构造最小生成树,答案加上最小的点权即可。


1233: [Usaco2009Open]干草堆tower

很神的结论题,主要突破点在于发现底部最窄那么层数一定最高

具体的算法代码的前面已经写了


1571: [Usaco2009 Open]滑雪课Ski

dp[i][j]表示到达时间点i,能力值为j所滑过的最大次数的

dp[i][j]\left\{\begin{matrix}dp[m[k]][o] & (1\leq k\leq s)\\ dp[i-d[k]][c[k]]+1 & (1\leq k\leq )\\ dp[i-1][j] & \end{matrix}\right.

显然对于同样在\alpha点结束的课程,我们一定会选择开始较靠后的点,这样就能节约中间差的时间

而对于一个山坡,我们肯定选择当前能力范围内,需要时间最短的山坡

于是这题就巧妙地由普通dp变成了贪心以及前缀数组优化dp的好题


1574: [Usaco2009 Jan]地震损坏Damage

考虑到一个点无法和1连通

那么他所相邻的点一定也无法和1连通

不然就矛盾了

那么从最小化原理来考虑,我们只需要当做他相邻的点无法和1连通即可

然后跑一边并查集判断连通

然后发现神TMO((n+m)\alpha)O(n+m)卡掉了

无奈写了BFS 1


1575: [Usaco2009 Jan]气象牛Baric

这题想了很久没有结果,主要归根于没有思考到强制第i位必取的方向

那么我们设f(i,j)表示已经扫描到第i位,且该位必选,选了以后一共有j个数据被选的最小误差

然后可以在O(n^{3})的时间内预处理,O(n^{3})转移


1576: [Usaco2009 Jan]安全路经Travel

考虑先构造最短路径树,那么对于每一条非树边,我们考虑把它加入图中的代价

不妨设u->v,那么一定可以在树上找一条路径从1->lca(u,v)->v->u->x\;(x\in {lca(u,v)->u})

而这条路径的代价为d[lca(u,v)]+d[v]-d[x]+d[u]

为了最小化这个式子,我们考虑最小化d[lca(u,v)]+d[v]+d[u],这个可以用树链剖分+线段树维护

lca可以直接用树剖求


1577: [Usaco2009 Feb]庙会捷运Fair Shuttle

考虑这么一个结论:对于一些牛,我们肯定会优先选择先下车的牛

这是为什么呢?当前的事情当前做,这样就能给后续的状态腾出空间

而每头牛的价值又是一样,所以大可以把多余的调整过去

然后这题就变成了区间操作,线段树维护即可


1579: [Usaco2009 Feb]Revamping Trails 道路升级

根据k\leq20,很容易想到分层图

而如果直接分层图的话,那么这道题的边集大小为M*N*K,显然是要爆炸

但是我们可以从动态规划的角度来思考,

dp[i][j]表示到达第i层的第j个点的最小值

那么有

dp[i][j]=min\begin{Bmatrix}dp[i-1][k],dp[i][k]+w\end{Bmatrix}

而我们发现这里出现了本层的状态,直接dp会有后效性,怎么办呢?

联想到dijkstra其实本质上是一种贪心,而这个决策转移也可以用dijkstra的思想来维护!

于是就直接跑k次dijkstra即可


1578: [Usaco2009 Feb]Stock Market 股票市场

考虑对于一支股票,与其把它拖到后面卖,不如明天就卖

为什么呢?因为你可以在明天卖然后再在明天等量购买

这样我们就可以用天数为阶段划分

对于每个阶段则是一个完全背包,最大收益累加到上限即可

时间复杂度O(NMC)


1584: [Usaco2009 Mar]Cleaning Up 打扫卫生

乱搞好题啊我曹QQ图片20160501171336

很容易想到一个动态规划的思路dp[i]=min\begin{Bmatrix}dp[j]+cnt[j+1,i]\end{Bmatrix}

其中cnt[j+1,i]表示区间[j+1,i]中本质不同的数的个数,这样时间复杂度为O(N^{2})

首先如果整个序列划分成n段的话,那么答案显然就是n

于是我们得知对于每一个阶段i,它的有效决策一定不会超过\sqrt{i}

所以我们可以令b[j]表示某个b[j]满足[b[j],i]中恰好有j个本质不同的数

那么怎么在最快的时间内维护b[j]呢?我们考虑增量法

对于我们当前的枚举的段[1,i],然后我们将i右移

这个时候,我们要考虑,如果i[1,i]中出现过了的话,我们就不用修改

因为等价于没有多出来的本质不同的数

但如果没有出现过的话,我们需要移动b[j]使得正好遇到一个已经出现过的数

b[j]==last[b[j]],其中last[i]表示s[i]在当前扫描的段中最后出现的位置

那么怎么判断它是否出现过了呢?可以用map维护,但这样会多出个log

实际上我们发现只需要考虑s[i]上一次出现的位置p,如果p>b[j]的话就意味着已经出现过了

这样一来,时间复杂度为O(n\sqrt{n})


1585: [Usaco2009 Mar]Earthquake Damage 2 地震伤害

给定一张无向图,最小化割集s使得1无法到达特定点集t,且割集与特定点集与1不能有交集。

不明白为什么要拆点QWQ,考虑对于每个没有被点到的点,就一定可以花1的代价去删掉它

就有i->i'=1

其次,对于其他的点,则i->i'=\infty

对于原图中的边x,y则考虑x'->y=y'->x=\infty

构造可以到达1的集合s,不可到达1的集合t

那么有s->1=\infty,对于每个被提到的点,有i'->t=\infty

然后就是一个裸的最小割即可,神TM ISAP卡dinic


1593: [Usaco2008 Feb]Hotel 旅馆

考虑构造一棵线段树,维护[l,r]中最大连续子段的长度,以及lm,rm

其中lm,rm分别表示最大的满足[l,l+lm-1]=[r-rm+1,r]=0的值


1592: [Usaco2008 Feb]Making the Grade 路面修整

dp[i][j]表示扫描到第i个数,将他修改为j,使得整个序列满足要求的最小答案

dp[i][j]=min\begin{Bmatrix}dp[i-1][k]+abs(k-a[i])\end{Bmatrix}

首先我们发现修改的数太大,但有一个结论是我们修改的结果一定是原序列中的数

我也不会证明

所以我们暴力枚举即可,然后对于k可以维护一个前缀最小值数组

时间复杂度O(n^{2})


1600: [Usaco2008 Oct]建造栅栏

dp[i][j]表示前i个栅栏和为j的方案数

dp[i][j]=\sum dp[i-1][j-k]


1602: [Usaco2008 Oct]牧场行走

我就当练模板了= =


1603: [Usaco2008 Oct]打谷机

很容易看出这是一个树上路径异或和的问题,由于异或和也有前缀和性质,所以直接上树剖就好啦


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

新姿势~!

对于两点(x1,y1),(x2,y2),令(x=x+y,y=x-y),则他们的曼哈顿距离可以表示为max\begin{Bmatrix}x1-x2,y1-y2\end{Bmatrix}

于是这题我们可以先变换坐标,然后根据横坐标排序

利用two pointers进行维护当前的区间

然后对于纵坐标采用平衡树维护,每次类似插入链表,取前驱后继,然后比较y坐标差值,使用并查集维护连通块

时间复杂度O(n\log n\alpha(n))


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

考虑对于每个数直接暴力枚举倍数

由基本数论可知,n以内x的倍数个数为\frac{n}{x}

而根据调和级数\sum_{i=1}^{n}\frac{n}{i}=n\log n

我们直接把每个数存入桶中,然后进行类似筛法的操作

时间复杂度O(n\log n)


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

f[i][j],g[i][j]分别表示把第i个数改成j,使得前i个数满足单调上升/单调下降的答案

f[i][j]=min\begin{Bmatrix}f[i-1][k]\end{Bmatrix}\;\;(k=1~j)

g[i][j]=min\begin{Bmatrix}g[i-1][k]\end{Bmatrix}\;\;(k=j~3)


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

很容易抽象成一个图的模型

a>b等价于a->b

然后对图跑传递闭包,如果每个点都和其他点有明确的大小关系,那么他的排名也就确定了


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

dp[i][j]表示时间为i疲劳度为j的最远距离

然后我发现居然i=1,j=2+可以dp不知道为什么QWQ求大佬指教

说好的第一个状态的疲劳值是0呢?人与人之间最基本的信任呢?