基础认知
一、二叉树种类：
1.满二叉树。记深度k，节点数量2^k-1。
2.完全二叉树：除了底层，其余全满，底部从左到右连续。
3，平衡二叉搜索树：左子树和右子树高度差不大于1。
二、存储方式：
顺序存储：已知代码i的元素，其左右“孩子”代码为2i和2i+1。
三、遍历方式：
1.深度优先搜索（前中后序遍历）【递归】【迭代】
前：中左右；中：左中右；后：左右中。
2.广度优先遍历（层序遍历）【迭代】
奇点杯试题分析
1.高效求和判断完全平方数
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;// 计算满足条件的数对数量
ll count_pairs(ll n) {ll total = 0; // 用于存储结果const ll s_limit = 2 * n; // 两个数的最大和ll k_max = static_cast<ll>(sqrt(s_limit)); // 最大可能的平方根// 确保 k_max 是最大的满足 k_max^2 <= s_limit 的整数while ((k_max + 1) * (k_max + 1) <= s_limit) ++k_max;// 遍历所有可能的完全平方数for (ll k = 2; k <= k_max; ++k) {const ll s = k * k; // 当前完全平方数const ll a = max(1LL, s - n); // i 的最小值const ll b = (s - 1) / 2; // i 的最大值if (a <= b) {total += b - a + 1; // 累加满足条件的数对数量}}return total;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll n;cin >> n; // 输入 ncout << count_pairs(n) << "\n"; // 输出结果return 0;
}难点：使用暴力法会TLE.不能使用多重循环。
2.计算连续子数组元素之和
#include <iostream>
using namespace std;
typedef long long ll;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll n;cin >> n; // 输入数组长度ll total = 0; // 用于存储最终结果for (ll i = 1; i <= n; ++i) {ll x;cin >> x; // 逐个输入数组元素total += x * i * (n - i + 1); // 计算当前元素的贡献并累加}cout << total << "\n"; // 输出结果return 0;
}难点：不能直接使用数组存放元素，会造成段错误。
3. DSU算法
#include<bits/stdc++.h>
using namespace std;int n, m, k;
int fa[100005]; // 并查集数组// 查找函数，带路径压缩
int find(int x) {if (fa[x] == x) return fa[x]; // 如果 x 是自己的父节点，直接返回else return fa[x] = find(fa[x]); // 否则递归查找，并压缩路径
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T; // 读取测试数据组数while (T--) {cin >> n >> m; // 读取节点数 n 和边数 m// 初始化并查集for (int i = 1; i <= n; ++i)fa[i] = i;// 读取 m 条边并合并集合for (int i = 1; i <= m; ++i) {int x, y;cin >> x >> y;int xx = find(x), yy = find(y); // 查找 x 和 y 的根节点if (xx == yy) continue; // 如果已经在同一个集合，跳过fa[xx] = yy; // 合并集合}cin >> k; // 读取查询数 kint st;cin >> st; // 读取起始节点 stst = find(st); // 查找 st 的根节点bool flag = 1; // 标志位，表示所有查询节点是否与 st 在同一个集合// 检查接下来的 k-1 个节点for (int i = 2; i <= k; ++i) {int ed;cin >> ed; // 读取查询节点ed = find(ed); // 查找 ed 的根节点flag &= (st == ed); // 检查是否与 st 在同一个集合}// 输出结果puts(flag ? "YES" : "NO");}return 0;
}4.计算因子并统计次数
#include <bits/stdc++.h>
using namespace std;const int MOD = 1e9 + 7;
const int MAX_A = 2e5 + 10;vector<int> get_factors(int v) {vector<int> res;for (int i = 1; i * i <= v; ++i) {if (v % i == 0) {res.push_back(i);if (i != v / i) {res.push_back(v / i);}}}return res;
}int cnt[MAX_A];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}long long ans = 0;for (int v : a) {auto factors = get_factors(v);long long sum = 0;for (int x : factors) {sum += cnt[x];}sum %= MOD;ans = (ans + sum) % MOD;cnt[v] = (cnt[v] + 1) % MOD; // 只增加当前元素的计数}cout << ans << endl;return 0;
}