「USACO Plan A」BZOJ1600 To BZOJ1625(Except BZOJ1608)

Problems - Click Here

25/25

  

Preface

  加入版权号后有点小激动(雾),终于不用体验那捉急的搜索速度了。。。

  正好NOIP也要来了,就打算刷下USACO的题目,不过题量有点大,所以打算分成几个Plan来完成。。。

  

BZOJ1600

Solutions

  此题的难点在于如何判断四边形是否合法

  不难发现,对于一个合法四边形,任意三边之和必定大于第四条边。换言之,每条边的长度必须小于总长的一半

  基于这种限制条件,跑一遍DP求方案数即可。

  

CODE

CODE - Click Here

  

BZOJ1601

Solutions

  最后的方案必定为一棵森林,而每棵树的根节点为水库,其余则是通过边来连接。

  换言之,现在的问题有两点,一是如何找到水库的建造位置,二是如何得到最优的连边方案

  问题二显然是最小生成树问题,可以解决。而对于问题一,我们不妨建造一个根,所有的树都连向这个根,并将水库的花费转换为连边的花费,这样问题一就转换成问题二了。

  直接跑一遍MST即可。

  

CODE

CODE - Click Here

  

BZOJ1602

Solutions

  树上任意两点距离问题。经典问题,求一次LCA即可。

  

CODE

CODE - Click Here

  

BZOJ1603

Solutions

  给出的是树,直接DFS即可。用异或简化操作。

  

CODE

CODE - Click Here

  

BZOJ1604

Solutions

  这是道好题

  看到这种题,首先的想法应该是通过单调性来解决。但是,由于$x$和$y$之间有相互制约的关系,其中一个值改变,会影响到另外一个值的合法区间。因此,解决这道题的关键就在于,将$x$与$y$进行分离

  设两个点的坐标分别为$(x_1,y_1)$,$(x_2,y_2)$,则曼哈顿距离$dis=|x_1-x_2|+|y_1-y_2|$。

  去绝对值可得下列四条等式,

  $dis=x_1-x_2+y_1-y_2 \iff dis=(x_1+y_1)-(x_2+y_2)$

  $dis=x_1-x_2+y_2-y_1 \iff dis=(x_1-y_1)-(x_2-y_2)$

  $dis=x_2-x_1+y_1-y_2 \iff dis=(x_2-y_2)-(x_1-y_1)$

  $dis=x_2-x_1+y_2-y_1 \iff dis=(x_2+y_2)-(x_1+y_1)$

  对于任意一种情况,曼哈顿距离必定为上列等式的其中一种

  设$x’_1=x_1+y_1, \, y’_1=x_1-y_1, \, x’_2=x_2+y_2, \, y’_2=x_2-y_2$

  则$dis=max(|x’_1-x’_2|,|y’_1-y’_2|)​$,即为切比雪夫距离公式

  因此,若要满足$dis \leq C$,则必须满足$|x’_1-x’_2| \leq C , |y’_1-y’_2| \leq C$,这样就成功实现了$x$与$y$的分离

  分离后,做法就十分明显了。首先保证$x’$单调,其次用Treap来维护$y’$,保证$y’$单调,合法方案用并查集维护一下即可。

  

CODE

CODE - Click Here

  

BZOJ1605

Solutions

  DP

  首先奶牛的总数是$\leq k$的,因此不会出现剩余指挥次数而某堆奶牛已经跳完的情况

  设$f[k][i][j]$表示指挥了$k$次以后,最后横纵坐标偏移$(i,j)$,其中$i,j \in [-k,k]$的解。

  则转移方程为$f[k][i][j]=min(f[k-1][i’][j’]+cow)$,其中$cow$表示偏移$(i,j)$后,跳下的奶牛数且$(i’,j’)$ 与$(i,j)$的曼哈顿距离为1。

  对于方案的求法,可以用一个$k$的四进制数来存取。而题目要求的最小方案,则可以分别将$E,N,S,W$与$0,1,2,3$对应,这样就可以直接判断来比较方案大小了。

  

CODE

CODE - Click Here

  

BZOJ1606

Solutions

  背包DP,做法类似BZOJ2748

  

CODE

CODE - Click Here

  

BZOJ1607

Solutions

  就是求有多少个约数,用类似于筛法的写法求即可。

  

CODE

CODE - Click Here

  

BZOJ1609

Solutions

  典型的最长上升子序列问题,跑一遍DP即可。

  

CODE

CODE - Click Here

  

BZOJ1610

Solutions

  N那么小,直接$N^2$求出所有斜率,去重即可。

  

CODE

CODE - Click Here

  

BZOJ1611

Solutions

  根据给出的流星信息,得到每个格子的最早的被破坏时间,跑一次BFS即可。

  

CODE

CODE - Click Here

  

BZOJ1612

Solutions

  原本还想弄拓扑排序的,不过不是那么好搞。

  直接每个点正向边和反向边分别跑一遍DFS,看该点能否到达所有点即可。

  

CODE

CODE - Click Here

  

BZOJ1613

Solutions

  DP

  设$f[i][j]$为第$i$分钟,疲劳值为$j$时的最优解。

  则,转移方程为$\begin{cases} f[i][0]=max(f[i-k][k]),0 \leq k \leq min(i,m) \\ f[i][j]=f[i-1][j-1]+d_i,j>0 \end{cases}$

  

CODE

CODE - Click Here

  

BZOJ1614

Solutions

  这k次免费必定是用在目标路径上的前k大长度,换言之题目要求1到N路径中第$k+1$大的数值最小

  注意到答案是有单调性的,因此我们可以二分答案,现在的问题是如何判断答案的合法性。

  假设二分的答案为$x$,那么小于x的长度都当做0,而大于x的长度都当做1,此时1到N的最短路径实质是x在1到N路径上的最小排名。只需要判断该数值与k的大小关系,即可判断答案的合法性。

  

CODE

CODE - Click Here

  

BZOJ1615

Solutions

  DFS

  暴力$N^2$连边,然后搜一下即可。

  

CODE

CODE - Click Here

  

BZOJ1616

Solutions

  DP

  设$f[T][i][j]$为T时刻,走到$(i,j)$坐标的路径数。

  转移方程为$f[T][i][j]=\sum f[T][x][y]$,其中$(i,j)$与$(x,y)$的曼哈顿距离为1,且$(x,y)$为合法格子。

  

CODE

CODE - Click Here

  

BZOJ1617

Solutions

  DP

  设$f[i]$为送$i$头奶牛过河时的最优方案。

  则转移方程为$f[i]=f[i-k]+2*M+\sum_{i=1}^k M_i,1 \leq k \leq i$

  

CODE

CODE - Click Here

  

BZOJ1618

Solutions

  背包DP

  

CODE

CODE - Click Here

  

BZOJ1619

Solutions

  找最高点,最高点必定是小山丘的顶峰。因此从最高点开始入手,做DFS

  

CODE

CODE - Click Here

  

BZOJ1620

Solutions

  答案具有单调性,现在的问题是如何判断答案合法

  利用简单的反证法,可以得知按照Deadline的先后顺序完成任务是最优的。通过这个性质,可以在$O(N)$内判断答案是否合法。

  

CODE

CODE - Click Here

  

BZOJ1621

Solutions

  直接DFS

  每次都会分一半,所以实际上DFS的次数只有$log \, N$级别而已,时间复杂度同理。

  

CODE

CODE - Click Here

  

BZOJ1622

Solutions

  模拟

  照着做就好了,用个数组保存指针即可。

  

CODE

CODE - Click Here

  

BZOJ1623

Solutions

  速度的减少只和牛的数量有关。因此速度小的在前必定是比速度大的在前优。

  基于该原则,我们可以对速度排序。然后依次放入车道,放不了的直接跳过即可。

  

CODE

CODE - Click Here

  

BZOJ1624

Solutions

  航行顺序是确定的。也就是说,如果要使得总危险指数最小,只需要保证航行到相邻小岛的危险指数最小即可。这是最短路径问题,跑一边Floyd即可。

  

CODE

CODE - Click Here

  

BZOJ1625

Solutions

  经典01背包

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang