HLAIA-光子

基环树 基环树不是树，而是只有一个连通环的图，它有$ n 个点和个点和个点和 n $条边。 无向图上的基环树。在一颗基于无向图的无根树加上一条边，就形成了基环树。去掉环上任意一条边，基环树就变成了一颗真正的树 有向图上的基环树。一个有向无环图，如果能在图中加一条边形成一个自连通的环，则形成一颗基环树。把环看成一个整体，根据它与环外点的关系，把基环树分为两种：内向树，环外的点只能进入环内，所有边都指向环；外向树，环外的点无法进入环内，所有边都背离环。 （图是丑了一点，意思到位就行…） 基环树的找环问题，就是“图的连通性”的一个简化问题。 无向图，用拓扑排序的BFS找出环，操作结束后，度数大于$ 1 的点就是环上的点。具体做法：①计算所有点的度数；②把所有度数为的点就是环上的点。具体做法：①计算所有点的度数；②把所有度数为的点就是环上的点。具体做法：①计算所有点的度数；②把所有度数为 1 的点入队；③队列弹出度数为1的点，把它连的所有边都去掉，并将边所连的邻居点的度数减的点入队；③队列弹出度数为1的点，把它连的所有边都去掉，并将边所连的邻居点的...

拓扑排序 拓扑排序不是对数字进行大小排序的那种排序，而是对一系列事物的顺序关系和依赖关系进行排序，属于图论。拓扑排序的排序结果通常不是唯一的。 一个图能进行拓扑排序的充要条件是它是一个**有向无环图(DAG) **。 拓扑排序需要用到点的入度(Indegree)和出度 (Outdegree) 入度：以点$ v 为终点的边的数量，称为为终点的边的数量，称为为终点的边的数量，称为 v $的入度。 出度：以点$ u 为起点的边的数量，称为为起点的边的数量，称为为起点的边的数量，称为 u $的出度。 一个点的入度为0，说明它是起点，是排在最前面的；一个点的出度为0，说明它是终点，排在最后面。 拓扑排序的简单的图遍历，用BFS和DFS都能实现。 基于BFS的拓扑排序 (1)无前驱的顶点优先 先输出入度为0的点(无前驱，优先级最高)，以下是具体步骤： 找所有入度为0的点，放入队列作为起点，这些点谁先谁后没有关系。如果找不到入度为0的点，说明这个图不是DAG，不存在拓扑排序。 弹出队首元素a，将a的所有邻居点入度-1，入度减为0的邻居点入队。没有减为0的不入队。 继续上述操作，直到队列...

逆序对 最简单的求逆序对的方法：冒泡排序，时间复杂度$ O(n^2) $ 直接给无优化的代码，不解释了： 123456789101112131415161718#include <bits/stdc++.h>using namespace std;int a[10] = {3,5,7,9,2,1,4,6,8,10};int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n = 10, cnt = 0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(a[j] < a[i]){ swap(a[i],a[j]); cnt++; } cout << cnt << '\n'; ...

区间DP 以一道模板题目为例----石子合并 不能用贪心，会陷入局部最优解。用DP求解 定义dp[i][j]为合并第i堆到第j堆的最小花费 状态转移方程为： dp[i][j] = min(dp[i][k] + dp[k+1][j] + w[i][j])，i <= k < j，w[i][j]表示第i堆到第j堆的石子总数，可以用前缀和计算。dp[1][n]就是答案 复杂度O(n3)，可以用四边形不等式优化到O(n2) 自顶向下的思路： 计算大区间[i,j]的最优值时，合并它的两个子区间[i][k]和[k+1][j]，对所有可能的合并(i <= k < j)采取最优合并。子区间再分解为更小的区间，最小区间[i,i+1]只包含两堆石子 自底向上的编程： 先在小区间进行DP得到最优解，再逐步合并小区间为大区间。以下是code： 123456789101112const int INF = 0x3f3f3f3f;int dp[n][n] {}; //C++11特性，集成初始化为0for(int len = 2; len <= n; ...

蓝桥杯15届国赛B 题目可以在官网https://www.lanqiao.cn/上查到 填空A 暴力找每个长度为8~16的子区间，然后判断是否满足条件即可 12345678910111213141516171819#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); string s = " kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th"; int si = s.size()-1, sum = 0; for(int i=1;i<=si;i++){ bool num = 0, fu = 0; for(int j=i;j<=i+15 &am...

CF1013 div3 给个题目链接，就不一题一题截图了：https://codeforces.com/contest/2091 F 比较好的思路：dp+前缀和 用u[i][j]表示从i-1排满足距离条件的点到点(i,j)的所有走法之和，状态转移方程为： u[i][j] = (prep[i-1][r2] - prep[i-1][l2]); 用p[i][j]表示在第i排满足距离条件的点横着走到点(i,j)的所有走法之和，状态转移方程为： p[1][j] = (preu[1][r1] - preu[1][l1]); 用preu[i][j]表示第i排的u的前缀和 用prep[i][j]表示第i排的p的前缀和 先特殊处理第1排（起始排），再从2排到n排逐排处理 比较我硬着头皮写的思路和官解的思路，我发现两个本质上差不多，就是实现方法不同 来看看我写的屎： （dp+BFS） 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585...

树形DP 首先是树的储存，树的储存是图的储存的特殊情况，可以用邻接表储存，或链式向前星 洛谷P2015二叉苹果树 定义状态dp[u][j]表示以节点u为根的子树上留 j 条边时的最多苹果数量。dp[1][q]就是答案。 状态转移方程：dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w) 其中，v 是 u 的一个子节点。dp[u][j]的计算分以下两部分： dp[v][k]：在v上留k条边 dp[u][j-k-1]：除了v上的k条边，以及u-v边，那么以u为根的这棵树上还有j-k-1条边，它们在u的其他子节点上 总复杂度小于O(n3) PS： 这道题是无向图储存，因为题目没有说明输入的两个节点哪个是爹哪个是儿，所以要push_back两次，然后在搜的时候跳过father j 循环必须递减，例如dp[u][5]会用到dp[u][4]和dp[u][3]等等，若是递减循环，先算5，再算4，再算3…dp[u][5]用到的是dp[u][4]和dp[u][3]的原值；若是递增循环，dp[u][5]就会用到dp[u][4]和dp[u...

本部蓝桥试炼 续上回 B 线段树板子，但奈何我现在没法手撕线段树哇(码太长了) 遂选择树状数组，但是–按理说树状数组（nlog2n）的复杂度是能过此题的，而且赛后题解里也说了树状数组能过，为什么才拿25分？？ (后来发现问题了–忘记取模，唉) 题补就写线段树的吧 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e5+10;const int mod = 1e9+7; int a[N]; int tree[N<<2]; int tag[N<<2]; int ls(int p){return p<<1;...

牛客月赛113 A 签到 12345678910111213141516#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int sum = 1; string s; cin >> s; for(char i : s){ if(i == '-') sum -= 1; else sum *= 2; } cout << (sum >= 2025 ? "YES\n" : "NO\n"); return 0;} B 统计相邻相同字符即可 12345678910111213141516#include <bits/stdc++.h>using namespace std;int ...

牛客周赛86 A 签到 1234567891011#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int x,y; cin >> x >> y; cout << (y%x ? y/x+1 : y/x) << '\n'; return 0; } B 贪心，很明显删除全部负数就可以使总和最大，也就是把正数相加 1234567891011121314151617181920212223#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 2e5+1;signed main(void){ ios::sync_with_stdio(fals...