「USACO」BZOJ1600 To BZOJ1625(Except BZOJ1608)

2017-06-25 题目集合 Viewed times

Problems - Click Here

25/25

前言

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

　　正好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