算法竞赛进阶指南_打卡_题解_0x20

本文主要是介绍算法竞赛进阶指南_打卡_题解_0x20，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

①：小猫爬山
https://www.acwing.com/problem/content/description/167/

索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
\(1≤N≤18, 1≤Ci≤W≤108\)

一看数据范围，我们必然会去打暴力。
就有如下两个方法：

①：爆搜+剪枝：
剪枝1：我们先对小猫进行降序排序，我们就可以得到一个单调性。在dfs时，我们便可以从上一个枚举的位置开始枚举，减少时间复杂度。由于A+B=B+A，对其逆序排序后从上一个枚举的位置找起，也能减小搜索树的大小。
剪枝2：可行性剪枝，如果当\(前重量<上限重量\)，则可以选择放入或者另开缆车。否则另开一辆缆车。
注：我们以缆车数量看成一个最主要的评估状态，而不要以猫有无放入为主要评估状态，不然会经过很多重复的子状态，导致像我一样超时半天。

②：二进制枚举+递推：
这个就是我最初ac的想法了。
我们二进制枚举每一个可能出现的状态，二进制位为1时为该猫已上车，0则相反。
我们有二元组数组state，state[i]存储为i状态时最小需车量(cnt)及当前车最小承重量(w)。
我们有以下递推公式：
如果pre状态可以由i状态加入第j只重量为a[j]的小猫转移过来:
若 state[i].w+a[j]<w
 若 state[i].w+a[j]<state[pre].w且state[i].cnt\(==\)state[pre].cnt 
 则 state[pre]={state[pre].cnt,state[i].w+a[j]} 
 若 state[i].cnt<state[pre].cnt
 则 state[pre]={state[i].cnt,state[i].w+a[j]}
否则
 若 state[pre].cnt>state[i]+1
 则 state[pre]={state[i].cnt,state[i].w+a[j]}
 若 state[pre].cnt\(==\)state[i]+1
 则 state[pre]={state[pre].cnt,min(state[i].w+a[j],state[pre].w)}

②：数独：剪枝，搜索，位运算

数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。

这题的剪枝策略主要是按一定规律枚举数独的格子。
我们考虑将搜索树减小，所以我们要尽可能的少枚举点。因此我们可以优先枚举可以填充更少种类数字的格子。
在没一轮枚举中，为了将我们数独中每个格子能够填充的数字尽可能少，因此我们每轮将唯一能够确定的格子先填上。


在上述剪枝过后时间效率大大提高了，可是还是超时，这里我们就要对其常数进行优化，我们采用位运算的方法。
我们存在一个数组st[i][j],i为1,2,3分别代表行，列，从左到右从上到下的3*3小九宫格。j代表所属的第j行，列，小九宫格。
其利用九位二进制数存储该数是否能被取。有\(k=st[1][x]\)&\(st[2][y]\)&\(st[3][(x-1)/3*3+y\) \(mod\) \(3]\)
当k!=0,则存在能取的数。
当k上的二进制位只有一个1时，能够填的数唯一确定。（我们可以用lowbit运算快速求出有几位1）
\(******\)
注：位运算效率为n/32，n为二进制的位数，也就是会比原程序快上30倍左右。




③：木棒：搜索，剪枝
https://www.acwing.com/problem/content/169/

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。

我们首先设立一个st数组，表示该木棍是否被使用过。
然后我们考虑剪枝:

①：优化枚举顺序：和小猫爬山一样，我们可以降序枚举木棍。在降序的木棍长度序列中，很明显的，当存在一个木棍集A，且A.len<lim，使A.len\(==\)lim时，使用一个木棍一定优于使用两个木棍，因此在存在A.len\(==\)lim时，我们只需要枚举一次即可return，以免等效的搜索树出现。
②：剪去等效搜索树：当我们选择长度为a[i]的木棍时，若此次搜索的结果为false，这其余本次使用长度为a[i]的搜索树必然也为false，因此当我们枚举到长度为a[i]时可以continue掉。
③：这里还有一个很强的剪枝：因为我们降序枚举，当其最终枚举到了false，那么就意味着当前枚举出长度为lim的木棍集顺序不对。因此我们可以直接return当前的新木棍(tot=0)或者上一步的最后木棍(tot+a[j]=lim)。且一定return false。

④：生日蛋糕：推公式，剪枝，搜索开始不会了
https://www.acwing.com/problem/content/170/

ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕，每层都是一个圆柱体。
设从下往上数第 i 层蛋糕是半径为 Ri，高度为 Hi 的圆柱。
当 i<M 时，要求 Ri>Ri+1 且 Hi>Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 Q 最小。
令 Q=Sπ ，请编程对给出的 N 和 M，找出蛋糕的制作方案（适当的 Ri 和 Hi 的值），使 S 最小。
除 Q 外，以上所有数据皆为正整数。
\(1≤N≤10000, 1≤M≤20\)

首先不要像我读了假题。连暴力都写错
蛋糕长这样：

而不是这样：

朴素的想，我们一定会去枚举每一层的高度(h[i])和半径(r[i])。
有圆柱体体积公式\(N=\sum_{1}^{m} h[i]*r[i]*r[i]\)，我们记当前(第j层时)已经积累的体积为v，当前已经积累的面积为s。
体积也可以化简为\(N=v+\sum_{j}^{m} h[i]*r[i]*r[i]\)，且记\(H=max(h[j]...h[m])，R=max(r[j]...r[m])\)
又因为\(R_{i}>R_{i}+1 且 H_{i}>H_{i}+1\)
所以\(r[j-1]>R,h[j-1]>H\)。
因此\(N-v\lt (h[j]*r[j]*r[j])^{m-j-1}\)
我们首先枚举h再枚举r，所以有：
\(r[j]\in [j,min({\sqrt{N-v}},r[j-1]-1)]\)(此时h[j]看做常量)
\(h[j]\in [j,min((N-v)/r[j]^2,h[j-1]-1)]\)
目前为止，我们就已经确定h,r枚举范围了。
接下来，我们对其进行剪枝：

①：可行性剪枝：如果当前的体积加上未来可能的最小体积大于题目所给出的体积，必然无解。
什么时候是最小体积？必然是每一个r[j],h[j]均最小，即为j时，我们可以预处理出来，作为剪枝。
②：最优行剪枝：如果当前表面积加上未来可能最小表面积大于目前已知最小面积，必然无解。
同最小体积预处理出来最小面积。
③：最重要的最优性剪枝：我推八出来，我爬爬

第三个剪枝是最重要的，也是最难推的（）

⑤：送礼物：双向搜索，二进制枚举，二分
https://www.acwing.com/problem/content/173/

达达帮翰翰给女生送礼物，翰翰一共准备了 N 个礼物，其中第 i 个礼物的重量是 G[i]。
达达的力气很大，他一次可以搬动重量之和不超过 W 的任意多个物品
达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
\(1≤N≤46, 1≤W,G[i]≤2^{31}−1\)

我们很容易能联想到背包问题八。
不过这道题是大背包问题，无法像我们平时接触过的背包问题在多项式时间内解决。
如果考虑动态规划，背包体积过大，内存爆了，\(O(n*w)\)的时间复杂度也爆了。
我们考虑朴素的搜索。
时间复杂度\(O(2^{46})\)，必然也爆。
但是我们可以这么来想。我们将背包的物品分为数量接近的两组，不需要依据任何关键字。
我们可以预处理A组的物品价值，我们在搜索B组的物品的组合时只要在A预处理出来的价值二分查找找到重量小于等于（W-当前重量）即可。
时间复杂度\(O(n2^n)\)。
不过这道题比较恶心人，它只能用dfs过，不能二进制枚举过，会卡二进制枚举。
\(******\)
注：我校OJ上竞赛训练——动态规划——巨大背包问题，就是这个板子题但是我wa麻了，不知道锅在那了

这篇关于算法竞赛进阶指南_打卡_题解_0x20的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！