HLAIA-光子

回溯与剪枝 当递归所衍生出的子节点不符合条件时，就该“看到不对劲就撤退”——中途停止并返回。这个思路就是回溯。在回溯中用于减少子节点的拓展函数就是剪枝函数。 其难度主要在于拓展子节点的时候如何构造停止递归并返回的条件。 以HDU 2553 N皇后为例 题目 不同行: old_x≠new_xold\_ x \not= new\_ xold_x=new_x 不同列: old_y≠new_yold\_ y \not= new\_ yold_y=new_y 不同对角线: abs(old_x−new_x)≠abs(old_y−new_y)abs(old\_ x - new\_ x) \not= abs(old\_ y - new\_ y)abs(old_x−new_x)=abs(old_y−new_y) 代码 12345678910111213141516171819202122232425262728293031323334353637383940#include <bits/stdc++.h>using namespace std;int...

容斥原理 集合 SSS 的子集 A1A_1A1​ 有性质 p1p_1p1​ ，A2A_2A2​ 有性质 P2P_2P2​ ， …\dots… ， AnA_nAn​ 有性质 PnP_nPn​ 。 那么，集合 SSS 中具有性质 P1,P2,…,PnP_1,P_2,\dots,P_nP1​,P2​,…,Pn​ 的集合个数为 ∣⋂i=1nAi∣=∑i=1n∣Ai∣−∑1≤i≤j≤n∣Ai∩Aj∣+∑1≤i≤j≤k≤n∣Ai∩Aj∩Ak∣−⋯+(−1)n+1∣∩i=1nAi∣\Big|\bigcap_{i=1}^nA_i \Big| = \sum_{i=1}^n\left| A_i\right| - \sum_{1 \leq i \leq j \leq n} \left| A_i \cap A_j \right| + \sum_{1 \leq i \leq j \leq k \leq n} \left| A_i \cap A_j \cap A_k \right| - \dots + (-1)^{n+1} \left| \cap_{i=1}^n A_i...

ITA练习赛2 B 这道签到题我交了7发… 最初把题目看成了任意两个元素互素，结果怎么提交都不对，就发现看错题了… 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+5;int n,a[maxn];map <int,int> ma;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n; a[0] = -1; bool pd; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=2;i<=n;i++){ if(__gcd(a[i],a[i-1]) != 1){ cout << "-1\n";...

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

拓扑排序 拓扑排序不是对数字进行大小排序的那种排序，而是对一系列事物的顺序关系和依赖关系进行排序，属于图论。拓扑排序的排序结果通常不是唯一的。 一个图能进行拓扑排序的充要条件是它是一个**有向无环图(DAG) **。 拓扑排序需要用到点的入度(Indegree)和出度 (Outdegree) 入度：以点$ v 为终点的边的数量，称为为终点的边的数量，称为为终点的边的数量，称为 v $的入度。 出度：以点$ u 为起点的边的数量，称为为起点的边的数量，称为为起点的边的数量，称为 u...

逆序对 最简单的求逆序对的方法：冒泡排序，时间复杂度$ 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...

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] -...

树形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...