stdKonjac's Blog

An AC a day keeps the WA away ~

【HDU ACM Steps刷题记录 Chapter3】

源代码

https://github.com/stdKonjac/OJ-Submits

刷题记录

2018.9.16

3.1.1 超级楼梯:简单递推,第\(k\)阶楼梯只能由第\(k-1\)和第\(k-2\)阶楼梯跳到,不难得出递推关系式:
$$
\begin{equation}
F[i]=\left\{
\begin{array}{lr}
1 & & {i=1,2} \\
F[i-1]+F[i-2] & & {i\ge3}
\end{array}
\right.
\end{equation}
$$

因此预处理出前40阶楼梯的方案数即可。

2018.9.17

3.1.5 Tiling_easy version:设当前砖位置为\(n\),则铺它之前要铺满前\(n-1\)或\(n-2\)块砖,下面分情况讨论:

①铺满前\(n-1\)块砖:此时第\(n\)块砖只能竖着放。

②铺满前\(n-2\)块砖:此时\(n-1\)与\(n\)两块砖可由\(2×1\)的砖竖着放两块或者横着放两块,但是竖着放两块的情况,即第\(n\)块是竖着放的,已经被包含在①中了,所以我们只考虑横着放两块的情况。或者是放一块\(2×2\)的砖,所以此时一共有两种情况,那么我们不难得出递推式:

$$
\begin{equation}
F[n]=\left\{
\begin{array}{lr}
1 & & {n=0,1} \\
F[n-1]+2*F[n-2] & & {n\ge2}
\end{array}
\right.
\end{equation}
$$
由于\(n\le30\),预处理出前30项即可。

3.1.4 折线分割平面:和Chapter2中三角形那道题类似。假设现在平面中只有一条折线,我们添加第二条折线,但是我们把它拆成两条直线来考虑,第一条直线,最多与前面的那条折线产生2个交点,这条直线本身被划分成三部分,每部分都可以切割出一个新的平面。同理,我们再添加第二条直线,则总共可以产生4个交点,两条直线组合成的折线一共被分成了6个部分,其中,除了最端点的“尖角”(我们看作一个部分)只能新增一个平面外,这条直线其余被切分的4段都各能增加一个平面。

《【HDU ACM Steps刷题记录 Chapter3】》

现在我们把情况推广到n条折线。对第n条折线来说,它的每条直线最多与前面每一个折线有2个交点,则总共能有\(2*(n-1)=2n-2\)个交点,这条直线被划分为\(2n-2+1=2n-1\)个部分,另一个直线同理,则一共可以划分为\(2n-1)*2=4n-2\)个部分,其中,除了尖角的两部分外,其余的\(4n-4\)个部分每部分都能新增一个平面,最后尖角的两部分一起能增加一个平面,因此每条折线最多能够增加\(4n-4+1=4n-3\)部分。所以我们不难得出递推式:

$$
\begin{equation}
F[n]=\left\{
\begin{array}{lr}
2 & & {n=1} \\
F[n-1]+4n-3 & & {n\ge2}
\end{array}
\right.
\end{equation}
$$

2018.9.19

3.1.3 母牛的故事:找规律的水题,打打表就可以发现递推式如下:

$$
\begin{equation}
F[n]=\left\{
\begin{array}{lr}
n & & {n\le3} \\
F[n-1]+F[n-3] & & {n\ge4}
\end{array}
\right.
\end{equation}
$$

3.1.6 统计问题:设第n步总的方案数为\(F[n]\),其中横着走的方案数有\(horizon[n]\)种,向上走的方案数有\(vertical[n]\)种,显然有\(F[n]=horizon[n]+vertical[n]\)。

考虑横着走的方案,所有横着走的方案,要么是由上一步横着走得来的,此时这一步横着走只能向一个方向,这种情况共有\(horizon[n-1]\)种方案;要么是由上一步向上走得来的,此时这一步横着走可以走两个方向(左或者右),这种情况共有\(2*vertical[n-1]\)种方案,于是我们有:
$$horizon[n]=horizon[n-1]+2*vertical[n-1]$$
再来考虑向上走的方案,无论上一步是横着走的,还是向上走的,这一步都能向上走,所以这种情况共有\(F[n-1]\)种方案,即:
$$vertical[n]=F[n-1]$$
所以我们不难得出如下递推式:
$$
\begin{equation}
\left\{
\begin{array}{lr}
horizon[n]=horizon[n-1]+2*vertical[n-1] & & {n\ge1} \\
vertical[n]=F[n-1] & & {n\ge1} \\
F[n]=horizon[n]+vertical[n] & & {n\ge1}
\end{array}
\right.
\end{equation}
$$
注意一下初始情况\(F[0]=1,vertical[0]=0,horizon[0]=2\)。

2018.9.27

3.1.7 Children’s Queue:我们假设\(F[n]\)为长度为\(n\)的合法序列的个数,要使一个队伍结尾合法,有两种结尾方式:M或FF。

首先考虑M,M能接在任何一个合法的序列的后面,所以结尾为M共能贡献\(F[n-1]\)种方案。

再考虑FF,如果FF是接在一个合法的序列后,则能贡献\(F[n-2]\)种方案;如果FF是接在一个不合法的序列后(即以MF结尾的序列),则此时最末尾确定为MFFF,此时能贡献\(F[n-4]\)种方案。

综上,我们可以得到递推式:\(F[n]=F[n-1]+F[n-2]+F[n-4]\),因为本题数据较大,需要使用高精度加法。

注意处理\(n=1,2,3\)的情况,总结下来递推式为:
$$
\begin{equation}
F[n]=\left\{
\begin{array}{lr}
1 & & {n=0,1} \\
2 & & {n=2} \\
4 & & {n=3} \\
F[n-1]+F[n-2]+F[n-4] & & {n\ge4}
\end{array}
\right.
\end{equation}
$$
3.1.2 一只小蜜蜂…:简单递推,设\(F[n]\)为从a到n的方案数,第n格只能从第n-1格或第n-2格走来,所以不难得出下列递推式:
$$
\begin{equation}
F[n]=\left\{
\begin{array}{lr}
1 & & {n=a,a+1} \\
F[n-1]+F[n-2] & & {{a+2}\le{n}\le{b}}
\end{array}
\right.
\end{equation}
$$
本题注意使用long long,否则会WA。

2018.9.28

3.1.8 Queuing:矩阵快速幂入门题。

我们定义一个“”合法”序列为不含FMF和FFF的序列。

首先我们考虑所有倒数3位结尾的情况,分别为:FFF FFM FMF FMM MFF MFM MMF MMM

其中 FFM FMM MFF MFM MMF MMM是6种合法的结尾,我们不难注意到:

①当最末尾为M时,只要前\(n-1\)位是一个合法序列,那M一定可以接上成为一个新合法序列,所以最末尾接M能贡献\(F[n-1]\)种方案。

②当最末尾为F时,我们还不能确定接上后是否合法,再往前推。

I.我们先看MMF这种情况,这种情况无论最末四位是MMMF还是FMMF都是合法的,所以以MMF结尾,只要前\(n-3\)位是一个合法序列即可,所以最末尾接MMF能贡献\(F[n-3]\)种方案。

II.再考虑MFF这种情况,向前推一位得FMFF MMFF,其中FMFF不合法,所以只考虑最后4位仍不能得出结论,我们再往前推,FMMFF MMMFF这两种都是合法的,也就是说只要前\(n-4\)位合法,MMFF接上就可成为一个新的合法序列,这种接法共能贡献\(F[n-4]\)种方案。

综上,得出递推式子:
$$
\begin{equation}
F[n]=\left\{
\begin{array}{lr}
1 & & {n=0} \\
2 & & {n=1} \\
4 & & {n=2} \\
6 & & {n=3} \\
F[n-1]+F[n-3]+F[n-4] & & {n\ge4}
\end{array}
\right.
\end{equation}
$$
由于本题需要取模,而频繁取模会导致超时,故可将矩阵快速幂运用于递推式中,根据递推式子我们不难构造出以下式子:
$$
\begin{bmatrix}
F[n] \\
F[n-1] \\
F[n-2] \\
F[n-3]
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
F[n-1] \\
F[n-2] \\
F[n-3] \\
F[n-4] \\
\end{bmatrix}
$$
我们设矩阵
$$
A=
\begin{bmatrix}
1 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}
,
B=
\begin{bmatrix}
F[3] \\
F[2] \\
F[1] \\
F[0] \\
\end{bmatrix}
,
C=
\begin{bmatrix}
F[n] \\
F[n-1] \\
F[n-2] \\
F[n-3]
\end{bmatrix}
$$
进一步递推可得出:\(C=A^{n-3}B\)

回忆快速幂的核心代码:

我们只需要把普通乘法换成矩阵乘法,将取模应用到矩阵中的每个元素中即可。

3.2.1 Max Sum:简单DP,用\(maxSum[n]\)记录以n为右边界,向左延伸的最大子段和,因为前面的最大子段和可能出现负数,所以显然有:\(maxSum[n]=max(maxSum[n-1]+x,x)\),其中x为当前数字。对每一个\(maxSum[n]\),更新时同时更新最大子段的起始和结束位置即可。

3.2.2 Common Subsequence:最大公共子序列模板题,偷懒就用\(n^{2}\)算法了。设\(dp[i][j]\)表示字符串A在i处,字符串B在j处时的最长公共子序列,显然有\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])\),如果此时i处与j处的字母一样,则进一步比较\(dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)\),最后的答案就是\(dp[lenA][lenB]\) (我的字符串是从1开始存的,如果从0就是\(dp[lenA-1][lenB-1]\))。

2018.9.29

3.2.3 Super Jumping! Jumping! Jumping!:简单DP,设\(maxScore[i]\)表示到i为止的最大子序列和,不难得出递推式:\(maxScore[i]=max(maxScore[j]+data[i],maxScore[i]) (j<i)\),最后找所有\(maxScore[i]\)中最大的那个就行了。

3.2.6 数塔:简单dp,设\(dp[i][j]\)表示到第i行j列的最大和,根据题目显然有\(dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+tower[i][j]\),从上到下算一遍即可。

2018.9.30

3.2.5 Monkey and Banana:最长递减子序列的变形题,设\(dp[i]\)表示到第i块砖为止的最大高度,因为一块砖可以随意翻动,所以相当于六块不可翻动的砖:\((x,y,z)\),\((x,z,y)\),\((y,x,z)\),\((y,z,x)\),\((z,x,y)\),\((z,y,x)\),显然“底盘”越大且越高的砖放在下面越好,所以我们按照x越大越好,x一样y越大越好,y一样z越大越好的排序规则对所有处理后的砖块排序,然后不难得出递推式\(dp[i]=max(dp[i],dp[j]+block[i].z) (j<i并且i可以叠在j上)\),最后在所有的\(dp[i]\)中取最大值即可。

2018.10.1

3.2.4 Humble Numbers:先来考虑一个很简单暴力获取丑数表的思路:将已知的所有丑数都乘2/3/5/7,将得到的所有结果中最小的那个记为新的丑数。深入思考,其实并不需要这么麻烦,由于我们得到的丑数都是依次递增的,所以对于2,必定存在一个丑数\(y\)使得比\(y\)小的丑数乘2都小于等于当前最大丑数,\(y\)或比\(y\)大的丑数乘2都大于当前最大丑数,所以我们只需要记录这个\(y\)的位置就好,对于3、5、7也是同样的思路。

那么分界点怎么推进呢?假设\(x_1\)为2的分界点,若\(F[n]=F[x_1]*2\),则显然有:\(F[x_1+1]*2>=F[n]\)并且\(F[x_1+1]\)之前的丑数乘2都小于等于\(F[n]\),所以分界点只需要简单加1即可,对3、5、7同理。

因此,设\(F[n]\)代表第n个丑数,\(F[x_1]\),\(F[x_2]\),\(F[x_3]\),\(F[x_4]\)分别代表上面说的乘2/3/5/7丑数的分界点,不难得出以下状态转移方程式:\(F[n]=min(F[x_1]*2,F[x_2]*3,F[x_3]*5,F[x_4]*7)\),若\(F[n]=F[x_1]*2\),则\(x_1\)++,对\(x_2\),\(x_3\),\(x_4\)同理。初始值设为:\(F[1]=1\),\(x_1=x_2=x_3=x_4=1\)即可。

2018.10.2

3.2.8 命运:设\(dp[i][j]\)为走到点\(x,y\)的最大点数和,根据题意可推出:

①\(dp[i+1][j]=max(dp[i+1][j],dp[i][j]+map[i+1][j])\)

②\(dp[i][j+1]=max(dp[i][j+1],dp[i][j]+map[i][j+1])\)

③\(dp[i][k*j]=max(dp[i][k*j],dp[i][j]+map[i][k*j]),(k*j\le m)\)

初始值全部赋值为\(-inf\),\(dp[1][1]=map[1][1]\)即可。

3.2.7 免费馅饼:我们可以逆向来思考题目,设掉落最晚的那个馅饼的掉落时间为\(maxT\),则题目变为从第\(maxT\)秒开始接,到第\(0\)秒时在5处能接到最多的馅饼为多少。设\(dp[i][j]\)为第i秒在j处能接到的最多的馅饼,\(map[i][j]\)为在第i秒掉落在j处的馅饼总数,根据题意,若在点\(x\)处,则可跑到\(x+1\),\(x-1\)或待在\(x\)处接馅饼,于是可写出状态转移方程式:

①若\(j=0\),只能待在原地或从右边跑来,则有\(dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+map[i][j]\)

②若\(j=10\),只能待在原地或从左边跑来,则有\(dp[i][j]=max(dp[i+1][j],dp[i+1][j-1])+map[i][j]\)

③若\(1\le j \le 9\),则可待在原地或从左右跑来,则有\(dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+map[i][j]\)

从\(i=maxT\)时往前推即可,最后的答案就是\(dp[0][5]\)。

3.3.1 Bone Collector:01背包模板题,\(dp[j]\)表示背包容量为j时的最大价值,不难得出状态转移方程式\(dp[j]=max(dp[j],dp[j-volume[i]]+value[i],(j-volume[i]\ge 0)\),依次枚举物品和体积即可。注意优化为一维数组的话枚举\(j\)为从大到小枚举。

3.3.4 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活:多重背包模板题,\(dp[j]\)表示金额为j时最多可买的大米重量,则不难得出状态转移方程式:
$$
dp[j]=max(dp[j],dp[j-k*rice[i].p]+k*rice[i].h)(j\ge k*rice[i].p,0\le k\le rice[i].c)
$$

2018.10.6

3.3.2 Coins:多重背包+二进制优化。设\(dp[x]\)表示价格上限为\(x\)时用这些硬币可以构成的最大价格,显然我们要找的就是在\([1,m]\)中有多少个\(dp[x]\)满足:\(dp[x]=x\)。这样的话我们可以把每种硬币的面值等同于背包问题中物品的重量(或者体积啦),不难得出一个基础的状态转移方程式:\(dp[j]=max(dp[j],dp[j-k*item[i].weight])\)其中\(j-k*item[i].weight\ge 0\)并且\(k \in [1,item[i].count]\),但是如果一个一个枚举k的话在本题的较大数据下会超时,这时就要涉及到对这个问题的一系列优化了。

①首先,假如\(item[i].count*item[i].weight>m\)的话,相当于在最大只有m容量的情况下i这个物品可以随便取都是够的,于是这是只需要用完全背包的思路来处理第i个物品。

②如果\(item[i].count*item[i].weight\le m\),我们假设有7个物品i,7的二进制表示为111,111=100+010+001,我们只需要把它拆成3个物品,它们的价值和重量分别为单个物品i的重量和价值乘4、2、1就可以通过组合达到取小于等于7的任意数量物品i的效果,这就是所谓的“二进制优化”了,我们不需要再枚举k,只需要按照上述处理物品i即可。然后我们就把问题转化成了01背包,使用01背包的转移方程式即可解决问题。

算法的核心代码如下,以后可以作为此类多重背包的模板用了:

2018.10.7

3.3.3 I love sneakers!:分组背包。设\(dp[i][j]\)表示1~i每个品牌都有选到的情况下总钱数为j能买到的最大价值,对于物品x,如果不选则它,则\(dp[i][j]\)不变;如果将它作为第i个品牌的第一件选到的物品,则\(dp[i][j]=max(dp[i][j],dp[i-1][j-item[x].weight]+item[x].value)\);如果将它作为第i个品牌非第一件选到的物品,则\(dp[i][j]=max(dp[i][j],dp[i][j-item[x].weight]+item[x].value)\),综合一下可得状态转移方程式:

因为式子太长了看着扎眼,设:

\(dp[i][j]=a\)

\(dp[i-1][j-item[x].weight]+item[x].value=b\)

\(dp[i][j-item[x].weight]+item[x].value=c\)

\(dp[i][j]=max(a,b,c)\)

最终答案就是\(dp[S][M]\)

注意不能写成这种形式:

\(dp[i][j]=max(dp[i][j],dp[i-1][j-item[x].weight]+item[x].value)\)

\(dp[i][j]=max(dp[i][j],dp[i][j-item[x].weight]+item[x].value)\)

因为\(item[x].weight\)可能为0!这样第二个方程式就变成了:\(dp[i][j]=max(dp[i][j],dp[i][j]+item[x].value)\),由于value大于等于0,这个式子必然触发,而同时如果触发了第一个式子,相当于选了物品x,此时又触发第二个式子,相当于选了两次物品x,必然会导致错误的结果。

另外,由于value可能等于0,因此在初始化dp数组时,需要全部初始化为-1,只有\(dp[0][k],(1\le k\le m)\)的值为0,这样如果最后的答案\(dp[S][M]<0\),就是不可能的,输出“Impossible”,否则输出\(dp[S][M]\)。

3.3.5 Ahui Writes Word:假装是完全背包,其实是多重背包+二进制优化……由于N很大,C也很大,直接上完全背包的N*C稳稳的TLE,注意到每个物品的value和weight都很小,在\([0,10]\)间共11种情况,也就是说就算有100000个物品,本质不同(value和weight都不同)的物品最多也只有11×11=121个,所以我们只需要统计每种本质不同的物品有多少个就可以避免枚举巨大的N,将问题转化为多重背包做了。顺便为了保证速度,直接上二进制优化吧。

大概的核心代码是这样的:

3.3.6 ACboy needs your help:分组背包。设 \(dp[i][j]\)表示考虑前i门课,总上课天数为j的最佳方案,由于第i门课只能选一种上课天数,相当于第i组物品中只能选一个,于是如果不选,则有\(dp[i][j]=max(dp[i][j],dp[i-1][j])\);如果选,则有\(dp[i][j]=max(dp[i][j],dp[i-1][j-item[k].weight]+item[k].value)\),即核心的状态转移方程式为:

\(dp[i][j]=max(dp[i][j],dp[i-1][j],dp[i-1][j-item[k].weight]+item[k].value)\)

综合一下则有下面的核心代码:

2018.10.8

3.3.7 Proud Merchants:贪心+01背包。从样例中就可以注意到买物品的顺序会对后面能否买物品产生影响。假设我们现在有M元钱,有连个物品\(x\)和\(y\),且有\(M\ge Q[x]\),\(M\ge Q[y]\),考虑M满足什么条件才能既买\(x\)又买\(y\)。

①如果M先买\(x\),则剩下\(M-P[x]\)元,需要满足\(M-P[x]\ge Q[y]\),也就是\(M\ge P[x]+Q[y]\)才能再买\(y\)。

②如果M先买\(y\),则剩下\(M-P[y]\)元,需要满足\(M-P[y]\ge Q[x]\),也就是\(M\ge P[y]+Q[x]\)才能再买\(x\)。

显然,假设我们的总钱数为\(S\),如果要都买\(x\),\(y\),肯定\(M\)越小越好,因为这样意味着\(S-M\)更大,也就是说,能有更多的钱去买别的东西。所以如果先买\(x\)再买\(y\),需要满足的条件就是\(P[x]+Q[y] < P[y]+Q[x]\) ,等价于\(P[x]-Q[x] < P[y]-Q[y]\),所以我们依照\(P[x]-Q[x]\)的差值大小排序,小的在前能够满足最优购买顺序。一旦确定顺序,剩下的就是一个简单的01背包问题了。

但是由于01背包在进行状态转移时,循环顺序为逆序,实际上是一个逆向购买的过程。它每次的最后一个商品是确定购买的,然后再来推前面的商品。因此,我们推出的\(P[x]-Q[x]\)从小到大排序是正常顺序购买,也就是我们需要反着排,按照\(Q[x]-P[x]\)从小到大排(或\(P[x]-Q[x]\)从大到小排)即可。

3.3.8 最大报销额:网上怎么一大堆乘100的解法,我很怀疑其正确性……比如遇到很多100.9999999这样的数据,说不定会有问题?总之感觉靠谱一点的解法反倒不像背包问题了。

靠谱解法:设\(dp[i]\)表示报销第i张发票(前提它可以报销)的最大报销额,则不难得出\(dp[i]=max(dp[i],dp[j]+value[i])\),其中\(0 \le j < i且dp[j]+value[i]\le Q\),核心代码如下:

 

点赞

发表评论

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

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.