我的算法修炼之路--6 ——模幂、构造、背包、贪心、剪枝、堆维护六题精析
💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
算法画解 ✅
C++ ✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
前言
这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
对应题目点链接即可做。
本期涉及算法： 数学（可取模的快速幂），构造（图），01背包（问题转化），贪心算法，dfs暴搜+剪枝，模拟+小根堆维护最小值。
题目清单
1.转圈游戏
解法：数学 + 快速幂
n个数一圈（循环），计算（x + m * 10^k）% n的值即为移动后的位置。
由于 0 < k < 10^9, 就是10(109),非常的大，需要用到可以取模的快速幂，一边乘一边取模。用long long来存。
代码：
#include<iostream>usingnamespace std;typedeflonglong LL; LL n, m, k, x; LL qpow(LL a, LL b, LL p){ LL ret =1;while(b){ if(b &1) ret = ret * a % p; b >>=1; a = a * a % p;}return ret;}intmain(){ cin >> n >> m >> k >> x; cout <<(x + m *qpow(10, k, n))% n << endl;return0;}2.System Administrator（系统管理员）
解法：构造
要满足题目要求：去掉一个点后，图不连通，那么就构造一个点v左边连一个点，右边连n - 2个点。因为这道题目的边有限，且要用完，这种方式连的边最多，且满足题目要求。
重要的性质：
n个点如果至少要连n - 1条边， 所以m < n - 1时，连通图就不存在。所以 m > n - 1;
当有一个顶点与v相连，并且与其他顶点都不相连时，最大的边数可由以下方法来求：对于一个无向图，n个顶点，最多有n(n - 1) / 2条边。（结论），因为每一个点可以和剩下的n-1个点连一条边，那么就是n(n - 1), 且因为两个点只有一条无向边，会多算一次就/2。综上，可以算满足题目要求的情况：一个点连左边一个点，边数1，这个点加上右边一共n - 1个点边数(n - 1) * (n - 2) / 2 + 1。所以 m < (n - 1) * (n - 2) / 2 + 1。
综上所述，n - 1 < m < (n - 1) * (n - 2) / 2 + 1,可以用于判断m是否合法。
如果m在范围内，那么图存在，一定能构造出来，可以先在v的左边放置一个顶点w,在另一边放剩余的n-2个点，将所有的点(除了v本身)，连在v上，然后将它们（除了w）相互连接起来。
代码：
#include<iostream>usingnamespace std;typedeflonglong LL; LL n, m, v;intmain(){ cin >> n >> m >> v;if(m< n -1|| m >(n -1)*(n -2)/2+1){ cout <<-1<< e
