通过动态规划，某一个区间 GCD 可由前一个子区间的 GCD 与最后一个元素GCD 得到，处理所有区间的最大公因数，然后直接查表输出结果。 #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> h(n); for (int i = 0; i < n; i++) { cin >> h[i]; } vector<vector<int>> f(n, vector<int...

预处理每个数的最小质因数，再递推计算每个数的质因数个数，最后在区间 [N, M] 内找出最大值。 #include <bits/stdc++.h> using namespace std; int p[10000001]; //最小质因数 int c[10000001]; //质因数个数 void get(int b) { for(int i=0; i<=b; i++) { p[i] = i; } for(int i=2; i*i<=b; i++) { if(p[i] == i) { // i是质数 for(int j=i*i; j<=b; j+=i) { if(...

先序序列首元素为根节点、中序序列分割左右子树，然后递归递归处理左、右子树后，输出根节点即为后序序列 #include <bits/stdc++.h> using namespace std; string a,b; // 递归求后序 void ans(int x,int y,int p,int q) { if(x>y||p>q) return ; // 范围无效 // a[x]是根，在中序b中找根的位置i int i=b.find(a[x]); ans(x+1,x+i-p,p,i-1); ans(x+i-p+1,y,i+1,q); //左、右子树处理完后输出根 cout...

由于是先序遍历，所以在读入根节点和左右孩子结点后，可以直接在已经构造的序列里面查找，如果找到了，直接在这个根节点后插入左右孩子结点，如果没找到，就把根节点和左右孩子插到最后 #include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; char a,b,c; // a:root，b:left，c:right vector<char> s; while(t--){ cin>>a>>b>>c; // 找到root在当前序列中的位置 auto it...

后序序列的最后一个是根节点，在中序序列中找到根节点，可将序列分为左子树和右子树，然后递归处理左右子树，输出先序序列。 #include <bits/stdc++.h> using namespace std; string b, a; // 递归求先序 void ans (int x, int y, int p, int q) { if (x > y || p > q) return; char root = a [y]; // 后序最后一个元素是根节点 cout << root; // 优先输出根节点 int i = b.find (root); // 中...

通过递归构造二叉树，根据字符串类型确定节点类型，再对构造的树进行后序遍历输出结果 #include<bits/stdc++.h> using namespace std; struct FBINode { char type; // 节点类型 FBINode* left; FBINode* right; FBINode(char t) : type(t), left(nullptr), right(nullptr) {} }; // 判断字符串对应的节点类型 char getNodeType(const string& s) { bool has0 = false, has...

采用并查集解决问题，分成两个集合查询和视频相关度，然后将二者按降序排序，从高到低处理，逐步合并满足条件的边，用并查集维护连通集合大小，根据k的从大到小，避免了重复对并查集的构建，如果k变小，就直接把符合条件的新的视频加进来，最后直接得到查询结果。 #include<bits/stdc++.h> using namespace std; struct E { int x, y, z; }; E f[100005]; struct Query { int k, v, idx; } q[100005]; int n, Q; int a[100005]; int sz[100005]; i...

从大到小排序，依次找出最大的怨气值，使得所有罪犯对可以被分到两个监狱。采用贪心 + 并查集维护对立关系，若某对罪犯已在同一集合，无法分到不同监狱，则该怨气值就是最大的怨气值。 #include<bits/stdc++.h> using namespace std; struct E { int x, y, z; }; E f[100005]; // 存储罪犯怨气关系 int n, m; int a[20005]; // 并查集父节点数组 int b[20005]; // 记录对立监狱的罪犯 // 按怨气值降序排序 bool cmp(E a, E b) { return a.z &g...

采用并查集维护村庄的连通关系，按公路修复时间升序处理，每次合并公路连接的村庄，直到所有村庄连通，此时的时间即为最早连通时间 #include<bits/stdc++.h> using namespace std; int fa[10000]; int n,m; // 存储公路信息 struct node {int x,y,t; }a[1000000]; bool cmp(node fir,node sec) { return fir.t<sec.t; } int gf(int x) { if(fa[x]==x) return x; return fa[x]=gf(fa[x])...

主要用到了并查集，先遍历所有空洞，标记与上下表面连通的空洞，同时检查当前空洞与已遍历空洞的连通性，连通则合并； 遍历所有上表面连通空洞和下表面连通空洞，如果存在连通的结果就输出 Yes，否则输出 No。 #include<bits/stdc++.h> using namespace std; int f[1001]; int gf(int x) { if (x != f[x]) f[x] = gf(f[x]); return f[x]; } // 计算球心距离平方 long long dis(long long x, long long y, long long z, long l...

有向图的排序问题，统计每个课程的入度，优先选择入度为 0 的课程，然后逐步消除依赖，最终得到合法的学习顺序。 class Solution { public: vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { vector<int> in(numCourses, 0); // 入度数组 vector<vector<int>> adj(numCourses); // 邻接表 for (auto& p : pr...