ZaynusX的博客

41 完全二叉树的权值解题日期：250219解题用时：40min题目来源：蓝桥杯真题题目难度：中等题目标签：2019，二叉树，省赛 题意整理完全二叉树，每个节点都有一个权值，现在要把相同深度的节点的权值加在一起，想指导哪个深度的节点权值之和最大？ 解题思路根据完全二叉树的性质进行公示推导。注意数组越界的问题，会导致运行错误。 完全二叉树的性质 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 #include <iostream>#include <climits> // 用于 INT_MINusing namespace std;// 计算 2^iint fd(int i) { if (i == 0) return 1; // 2^0 = 1 int result = 1; while (i > 0) { result *= 2; ...

动态规划（Dynamic...

树形动态规划（Tree DP）是一种在树结构上进行动态规划的算法，常用于解决与树相关的最优化问题。其核心思想是利用递归和子问题分解，通过子树的结果推导出当前节点的结果。 核心思想 树结构：树是一种无向无环图，具有层次性，通常以根节点为起点。 动态规划：通过子问题的解推导当前问题的解，避免重复计算。 基本步骤 状态定义：为每个节点定义状态，表示以该节点为根的子树的性质。 状态转移：根据子节点的状态推导当前节点的状态。 递归求解：从叶子节点开始，递归计算每个节点的状态。 结果获取：最终结果通常存储在根节点或通过遍历所有节点得到。 常见问题 最大独立集：选择不相邻的节点，使权重和最大。 最小点覆盖：选择最少的节点覆盖所有边。 最长路径：找到树中最长的路径。 示例：最大独立集 状态定义：dp[u][0]表示不选节点u时的最大权重，dp[u][1]表示选择节点u时的最大权重。 状态转移： 不选u：dp[u][0] = sum(max(dp[v][0], dp[v][1]))，v为u的子节点。 选u：dp[u][1] = weight[u] +...

在C++中，sort 是标准库 <algorithm> 中的一个函数，用于对数组或容器中的元素进行排序。它使用高效的排序算法（通常是快速排序或内省排序），能够对任意可比较的元素进行排序。 基本用法sort 函数的基本语法如下： 123#include <algorithm> // 必须包含这个头文件sort(start, end); start：指向排序范围的起始位置的迭代器（或指针）。 end：指向排序范围的结束位置的迭代器（或指针），不包括这个位置。 sort 默认按升序排序。 示例 1：对数组排序1234567891011121314151617#include <iostream>#include <algorithm> // 包含 sort 函数using namespace std;int main() { int arr[] = {5, 2, 9, 1, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 ...

完全二叉树（Complete Binary Tree）是一种特殊的二叉树，具有以下性质： 1. 定义完全二叉树是指一棵二叉树中，除了最后一层外，其余层都是满的，并且最后一层的节点都集中在左侧。 2. 性质（1）节点编号与层次关系 如果将完全二叉树的节点从上到下、从左到右依次编号（从 1 开始），则对于任意节点 i： 其左子节点的编号为 2i。 其右子节点的编号为 2i + 1。 其父节点的编号为 ⌊i / 2⌋（向下取整）。 （2）高度与节点数的关系 设完全二叉树的高度为 h，节点数为 n，则： 高度 h = ⌊log₂n⌋ + 1。 节点数的范围是：2^(h-1) ≤ n ≤ 2^h - 1。 （3）结构特点 完全二叉树的最后一层节点从左到右依次排列，不会出现中间空缺的情况。 如果最后一层不满，则所有节点都集中在左侧。 （4）与满二叉树的关系 满二叉树是完全二叉树的特例，即所有层都满的完全二叉树。 完全二叉树不一定是满二叉树，但满二叉树一定是完全二叉树。 （5）数组存储 完全二叉树可以用数组高效存储，因为节点编号与数组下标有直接的对应关系。 节点 i...

31 凯撒加密解题日期：250218解题用时：4min题目来源：蓝桥杯真题题目难度：中等题目标签：2020，模拟，省模拟赛 题意整理凯撒加密原版。 解题思路直接计算推导，注意特判xyz。 AC代码123456789101112131415161718#include <bits/stdc++.h>using namespace std;int main(){ string s,s2; cin>>s; int len=s.length(); for(int i=0;i<len;i++){ if(s[i]>='x'){ s2+=(s[i]+'d'-'a'-26); } else{ s2+=(s[i]+'d'-'a'); } } cout<<s2; return 0;} 32...

双指针（Two Pointers）是一种常用的算法技巧，主要用于处理数组或链表等线性结构的问题。其核心思想是使用两个指针（或索引）来遍历数据结构，通过指针的移动来解决问题。 双指针的常见应用场景 有序数组的两数之和：在有序数组中查找两个数，使它们的和等于目标值。 移除元素：在数组中移除特定值的元素，同时保持原数组顺序。 反转数组或字符串：通过双指针从两端向中间遍历，实现反转。 链表中的环检测：使用快慢指针判断链表中是否存在环。 滑动窗口：通过双指针维护一个窗口，解决子数组或子字符串问题。 双指针的分类 同向双指针：两个指针从同一侧开始移动，通常用于滑动窗口或移除元素。 对向双指针：两个指针分别从两端向中间移动，适用于有序数组的两数之和或反转问题。 快慢指针：两个指针以不同速度移动，常用于链表中的环检测或找中点。 示例1. 有序数组的两数之和给定一个有序数组 nums 和目标值 target，找到两个数使它们的和等于 target。 1234567891011def two_sum(nums, target): left, right = 0, len(nums) -...

21 机器人塔解题日期：250217解题用时：63min题目来源：蓝桥杯真题题目难度：中等题目标签：2016，位运算，国赛，DFS 题意整理有两种机器人A和B，A只能站在AA或者BB之上，B只能站在AB或者BA之上。输入A和B人数，求能形成的花样总数。 解题思路枚举底层的所有可能性，先不考虑m和n的数量，在枚举的过程中进行判断。由底层计算出上一层，循环往复，统计总共的1和0的数目，再与m和n进行判断。使用位运算，快速遍历和计算。 AC代码123456789101112131415161718192021222324252627282930313233343536#include<iostream>#include<bitset>#include<cmath>using namespace std;int n, m;bool check(int now, int num){ int num_a = 0, num_b = 0; for(int i = num ; i >= 1 ;...

DFS（深度优先搜索） 和 BFS（广度优先搜索） 是两种经典的图遍历算法，广泛应用于树、图等数据结构的搜索问题。下面我们详细介绍它们的原理、区别以及C++实现模板。 1. DFS（深度优先搜索）核心思想 DFS 从起点开始，沿着一条路径尽可能深入地搜索，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。 使用 栈（递归或显式栈）来实现。 特点 适合解决 连通性、路径搜索、拓扑排序 等问题。 空间复杂度较低（与递归深度相关）。 不一定能找到最短路径。 应用场景 图的连通性检测。 寻找所有可能的路径。 拓扑排序。 解决回溯问题（如八皇后、数独）。 C++ 模板12345678910111213141516171819202122232425262728293031323334#include <iostream>#include <vector>using namespace std;void dfs(int node, vector<vector<int>>& graph,...

11 分球解题日期：250206解题用时：34min题目来源：蓝桥云课题库题目难度：简单题目标签：数学，排列组合 题意整理![[Pasted image 20250206162600.png]] 解题思路高中数学排列组合，第一反应隔板法。将n个球和k-1个隔板进行排序，总数为n+k-1 组合数公式为C(m,r)=m!/r!(m-r)! 此时m=n+k-1;r=k-1;但是后来尝试之后发现这道题目有很多坑。比如整数除法。将res存为double之后，最后不能使用cout输出。一定要使用printf。#### AC代码12345678910111213141516171819202122232425#include <iostream>using namespace std;double factor(int n){ int k=n; double res=1; while(k>=1) { res*=k; k--; } return res;}int...