第一题 递推式 T(n)2T(n-1)1第一步不要急着套公式很多同学一看到递推式就想到 Master 定理。但是 Master 定理只适用于T(n)aT(n/b)f(n)例如T(n)2T(n/2)n而本题是T(n)2T(n-1)1这里不是n 变成 n/2而是n 变成 n-1所以Master 定理不能使用第二步不断展开这是解决这种题目的最好办法。原式T(n)2T(n-1)1继续展开第一次T(n) 2[ T(n-1) ] 1把T(n-1)继续展开2[2T(n-2)1]1整理4T(n-2)3继续展开4[2T(n-3)1]3得到8T(n-3)7再展开16T(n-4)15大家发现规律了吗第三步寻找规律展开几次后T(n)2T(n-1)1 T(n)4T(n-2)3 T(n)8T(n-3)7 T(n)16T(n-4)15整理一下展开次数结果12¹T(n-1)122²T(n-2)332³T(n-3)742⁴T(n-4)15观察常数1 3 7 15是不是2¹-1 2²-1 2³-1 2⁴-1所以可以猜到展开 k 次后T(n) 2^k T(n-k) (2^k-1)第四步一直展开到底什么时候停止一直展开到T(1)即可。此时kn-1于是T(n) 2^(n-1)T(1) 2^(n-1)-1由于T(1)只是一个常数。例如T(1)1那么T(n) 2^(n-1) 2^(n-1)-1 2^n-1于是时间复杂度就是O(2^n)第五步为什么是指数级我们画递归树更容易理解。第一层T(n)第二层T(n-1) T(n-1)因为前面有2于是出现两个。第三层每个又变成两个。于是4个第四层8个第五层16个整个递归树就是T(n) / \ T(n-1) T(n-1) / \ / \ T(n-2)... T(n-2)...每下降一层节点数量乘2。高度约n因此总节点数1248... ≈2^n所以复杂度就是O(2^n)七级竞赛中常见递推复杂度总结递推式时间复杂度典型算法T(n)T(n-1)1O(n)线性递归T(n)T(n-1)nO(n²)递归累加T(n)2T(n-1)1O(2ⁿ)指数递归如朴素斐波那契变形T(n)T(n/2)1O(logn)二分查找T(n)T(n/2)nO(n)折半递归T(n)2T(n/2)nO(nlogn)归并排序T(n)2T(n/2)1O(n)完全二叉递归第2题 唯一分解定理答案D这题考的是基础知识。什么叫唯一分解定理任何大于1的整数都可以写成若干质数相乘例如12 2×2×3182×3×3602×2×3×5而且这种分解方式唯一。A为什么正确如果已经知道每个数最小质因子例如12 最小质因子2那么12 ↓ 2 ↓ 6 ↓ 2 ↓ 3 ↓ 结束一次一次除即可。因此非常快。B为什么正确欧拉筛为什么快因为每个合数 只会被最小质因子筛掉一次例如12不会被3 4 6重复处理。因此O(n)C为什么正确假设91如果2 3 5 7都不能整除。而√91≈9那么说明它没有小质因子。根据唯一分解定理它一定是质数。D为什么错误埃氏筛埃拉托斯特尼筛为什么是O(nloglogn)主要原因是不断标记倍数不是因为唯一分解定理。所以D错。第3题 最长公共子序列LCS答案B题目说LCS5什么叫公共子序列例如ABCDEF AEDCF公共子序列可以是ACF不用连续。为什么B正确既然最长公共子序列长度5说明至少有5个字符能够匹配。因此至少有5个公共字符正确。A为什么错编辑距离和LCS关系是编辑距离≠LCS不能直接推出。C为什么错公共子串要求连续公共子序列不用连续完全不是一个概念。例如ABCDE AXBYCZDELCSABCDE 长度5最长公共子串只有DE长度2。D为什么错两个串长度完全可以不同。例如ABCDE XXABCDEYYLCS还是5。第4题 树的度数之和答案B树有一个重要性质边数n-1每条边连接两个点。所以度数总和 2×边数 2(n-1)因此答案就是2n-2为什么例如1 | 2 / \ 3 4边数3度数1 3 1 1加起来6 2×3永远成立。考试一定要记住树 边n-1 度数和2(n-1)属于必考公式。第5题 哈希表答案D题目问错误的是哪一个。A正确装载因子元素个数/桶数越大说明越挤。冲突自然越多。B正确开放定址删除不能直接删。否则查找链断掉。因此一般要删除标记实现复杂。C正确链地址法最坏情况所有元素进一个桶。变成链表。复杂度O(n)D错误很多同学最容易掉坑。哈希表平均O(1)不是总是O(1)如果发生大量冲突仍然可能O(n)所以D错误。第6题 Kruskal算法答案B贪心Kruskal流程第一步排序最小边 ↓ 第二小 ↓ 第三小第二步依次加入。第三步如果形成环跳过。否则加入。为什么叫贪心因为每一步都选择当前最便宜并且希望最终也是最优。这就是Greedy常见算法分类算法思想Kruskal贪心Prim贪心Dijkstra贪心归并排序分治快速排序分治背包DP动态规划八皇后回溯第7题 二分答案奶牛放置问题答案B3这是竞赛中的经典模型——二分答案 贪心检验。第一步 排序数组1 2 8 4 9排序后1 2 4 8 9第二步 二分答案搜索最小间距dist初始l0 r8第一次mid(081)/2 4尝试距离4。放牛第一头1第二头5 8第三头12 没有只能放2头。失败。r3第二次l0 r3 mid2放牛1 4 8成功。l2第三次mid3放牛1 4 8仍成功。l3结束。答案3为什么check()使用贪心check()总是尽量把下一头牛放在最靠前且满足距离要求的位置。这样能为后面的牛留下尽可能多的空间因此如果这种放法都放不下k头牛其他放法也不可能成功。这就是二分答案中常见的“贪心验证”。第一部分1~7题知识点总结这7道题几乎覆盖了七级算法竞赛中的核心基础题号知识点必须掌握1递推式时间复杂度、递归树★★★★★2唯一分解定理、欧拉筛、埃氏筛★★★★★3最长公共子序列LCS与最长公共子串区别★★★★★4树的性质边数与度数和★★★★★5哈希表、装载因子、开放定址、链地址法★★★★★6Kruskal 最小生成树、贪心思想★★★★★7二分答案 贪心验证经典“奶牛放置”模型★★★★★
第一题 递推式 T(n)2T(n-1)1第一步不要急着套公式很多同学一看到递推式就想到 Master 定理。但是 Master 定理只适用于T(n)aT(n/b)f(n)例如T(n)2T(n/2)n而本题是T(n)2T(n-1)1这里不是n 变成 n/2而是n 变成 n-1所以Master 定理不能使用第二步不断展开这是解决这种题目的最好办法。原式T(n)2T(n-1)1继续展开第一次T(n) 2[ T(n-1) ] 1把T(n-1)继续展开2[2T(n-2)1]1整理4T(n-2)3继续展开4[2T(n-3)1]3得到8T(n-3)7再展开16T(n-4)15大家发现规律了吗第三步寻找规律展开几次后T(n)2T(n-1)1 T(n)4T(n-2)3 T(n)8T(n-3)7 T(n)16T(n-4)15整理一下展开次数结果12¹T(n-1)122²T(n-2)332³T(n-3)742⁴T(n-4)15观察常数1 3 7 15是不是2¹-1 2²-1 2³-1 2⁴-1所以可以猜到展开 k 次后T(n) 2^k T(n-k) (2^k-1)第四步一直展开到底什么时候停止一直展开到T(1)即可。此时kn-1于是T(n) 2^(n-1)T(1) 2^(n-1)-1由于T(1)只是一个常数。例如T(1)1那么T(n) 2^(n-1) 2^(n-1)-1 2^n-1于是时间复杂度就是O(2^n)第五步为什么是指数级我们画递归树更容易理解。第一层T(n)第二层T(n-1) T(n-1)因为前面有2于是出现两个。第三层每个又变成两个。于是4个第四层8个第五层16个整个递归树就是T(n) / \ T(n-1) T(n-1) / \ / \ T(n-2)... T(n-2)...每下降一层节点数量乘2。高度约n因此总节点数1248... ≈2^n所以复杂度就是O(2^n)七级竞赛中常见递推复杂度总结递推式时间复杂度典型算法T(n)T(n-1)1O(n)线性递归T(n)T(n-1)nO(n²)递归累加T(n)2T(n-1)1O(2ⁿ)指数递归如朴素斐波那契变形T(n)T(n/2)1O(logn)二分查找T(n)T(n/2)nO(n)折半递归T(n)2T(n/2)nO(nlogn)归并排序T(n)2T(n/2)1O(n)完全二叉递归第2题 唯一分解定理答案D这题考的是基础知识。什么叫唯一分解定理任何大于1的整数都可以写成若干质数相乘例如12 2×2×3182×3×3602×2×3×5而且这种分解方式唯一。A为什么正确如果已经知道每个数最小质因子例如12 最小质因子2那么12 ↓ 2 ↓ 6 ↓ 2 ↓ 3 ↓ 结束一次一次除即可。因此非常快。B为什么正确欧拉筛为什么快因为每个合数 只会被最小质因子筛掉一次例如12不会被3 4 6重复处理。因此O(n)C为什么正确假设91如果2 3 5 7都不能整除。而√91≈9那么说明它没有小质因子。根据唯一分解定理它一定是质数。D为什么错误埃氏筛埃拉托斯特尼筛为什么是O(nloglogn)主要原因是不断标记倍数不是因为唯一分解定理。所以D错。第3题 最长公共子序列LCS答案B题目说LCS5什么叫公共子序列例如ABCDEF AEDCF公共子序列可以是ACF不用连续。为什么B正确既然最长公共子序列长度5说明至少有5个字符能够匹配。因此至少有5个公共字符正确。A为什么错编辑距离和LCS关系是编辑距离≠LCS不能直接推出。C为什么错公共子串要求连续公共子序列不用连续完全不是一个概念。例如ABCDE AXBYCZDELCSABCDE 长度5最长公共子串只有DE长度2。D为什么错两个串长度完全可以不同。例如ABCDE XXABCDEYYLCS还是5。第4题 树的度数之和答案B树有一个重要性质边数n-1每条边连接两个点。所以度数总和 2×边数 2(n-1)因此答案就是2n-2为什么例如1 | 2 / \ 3 4边数3度数1 3 1 1加起来6 2×3永远成立。考试一定要记住树 边n-1 度数和2(n-1)属于必考公式。第5题 哈希表答案D题目问错误的是哪一个。A正确装载因子元素个数/桶数越大说明越挤。冲突自然越多。B正确开放定址删除不能直接删。否则查找链断掉。因此一般要删除标记实现复杂。C正确链地址法最坏情况所有元素进一个桶。变成链表。复杂度O(n)D错误很多同学最容易掉坑。哈希表平均O(1)不是总是O(1)如果发生大量冲突仍然可能O(n)所以D错误。第6题 Kruskal算法答案B贪心Kruskal流程第一步排序最小边 ↓ 第二小 ↓ 第三小第二步依次加入。第三步如果形成环跳过。否则加入。为什么叫贪心因为每一步都选择当前最便宜并且希望最终也是最优。这就是Greedy常见算法分类算法思想Kruskal贪心Prim贪心Dijkstra贪心归并排序分治快速排序分治背包DP动态规划八皇后回溯第7题 二分答案奶牛放置问题答案B3这是竞赛中的经典模型——二分答案 贪心检验。第一步 排序数组1 2 8 4 9排序后1 2 4 8 9第二步 二分答案搜索最小间距dist初始l0 r8第一次mid(081)/2 4尝试距离4。放牛第一头1第二头5 8第三头12 没有只能放2头。失败。r3第二次l0 r3 mid2放牛1 4 8成功。l2第三次mid3放牛1 4 8仍成功。l3结束。答案3为什么check()使用贪心check()总是尽量把下一头牛放在最靠前且满足距离要求的位置。这样能为后面的牛留下尽可能多的空间因此如果这种放法都放不下k头牛其他放法也不可能成功。这就是二分答案中常见的“贪心验证”。第一部分1~7题知识点总结这7道题几乎覆盖了七级算法竞赛中的核心基础题号知识点必须掌握1递推式时间复杂度、递归树★★★★★2唯一分解定理、欧拉筛、埃氏筛★★★★★3最长公共子序列LCS与最长公共子串区别★★★★★4树的性质边数与度数和★★★★★5哈希表、装载因子、开放定址、链地址法★★★★★6Kruskal 最小生成树、贪心思想★★★★★7二分答案 贪心验证经典“奶牛放置”模型★★★★★
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
