二分图 定义：设G=(V, E)是一个无向图，如果顶点V可分割为两个互不相交的子集（A , B），且图中的每条边（i, j）所关联的两个定点分别属于这两个不同的顶点集，则称图G为一个二分图。 性质：定理：当且仅当无向图G的每一个环的结点数均是偶数时，图G才是一个二分图。如果无环，相当于每的结点数为 0，故也视为二分图。 问题1，判定一个图是否是二分图？如果一个图是连通的，可以用如下的染色法判定是否二分图：我们把X部的结点颜色设为0，Y部的颜色设为1。从某个未染色的结点u开始，做BFS或者DFS 。把u染为0，枚举u的儿子v。如果v未染色，就染为与u相反的颜色，如果已染色，则判断u与v的颜色是否...

题意：给出一棵有偶数的节点的树，将其分成n/2对点，并且要求n/2对点的路径之和最小 涉及知识点：思维/树上dfs 思路：树上任意两点间的距离是唯一的，题目又要求路径之和最小，所以选择两个节点，要么是父节点和其孩子节点，要么是父节点的两个孩子节点，还有一种情况是多了一个孩子节点，那么肯定要先加上到父节点的距离，然后再和另外一个节点配对。所以在树上dfs，枚举子树的节点个数，一颗子树如果节点个数为偶数，就不需要再添加节点配对，如果节点个数为奇数，需要和父节点往外的一个节点配对，那么答案就要加上这颗子树到父节点的距离 代码： #include <bits/stdc++.h> using...

学习算法——最近公共祖先  算法介绍：LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科  例题：洛谷-LCA模板题  模板代码：   #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 500005; struct node{ int t,nex; }; node a[maxn<<1]; int head[maxn],tot; void add(int x,in...

涉及知识点：字符串匹配 题意：给出母串 s，给出 m 次询问，每次询问给出的子串 si 是否是 s 的子序列 思路：如果直接考虑双重for循环比较会超时，看着是道字典树的题，但是没写过字典树，就写了个递推思路的代码，设 nex[ i ][ j ] 表示第 i 个位置的字母后第一个 j + 'a' 字母的位置，提前预处理母串s，查询子串 si 就可以简化到O( n ) 代码： #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 1e6 + 5; char s[maxn]...

题目一般风格：  原题目网址：https://www.luogu.com.cn/problem/P2371 模板代码: #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 5e5+5; ll dis[maxn]; int n; ll l , r; int a[30]; bool flag[maxn]; queue<int> q; void spfa() { for(int i=0;i<a[1];i++)dis[i] = 1e18; q.push(0)...

涉及知识点：队列/双指针 做法：我看大佬们都是写的优先队列，我这里讲一下deque（双端队列）的解法吧，原理都是一样，首先先看一下deque的写法： deque<int> q;//定义双端队列 q.push_front(x);//队列头部插入元素x q.push_back(x);//队列尾部插入元素x q.front();//引用最前面的元素 q.back();//引用最后面的元素 q.pop_front();//删除队列最前面的元素 q.pop_back();//删除队列最后面的元素 q.size();//返回双端队列大小对于题目，我们要维护一个deque区间的最大值以及最小值，...

#include<bits/stdc++.h> using namespace std; const int MAXN=200005; vector<int>G[MAXN]; int sz[MAXN],dp[MAXN],val[MAXN],n,u,v,ans[MAXN]; ///---------------------------- void dp_link(int root1,int root2) { dp[root1]+=max(dp[root2],0); } void dp_cut(int root1,int root2) { dp[root1]-=max(dp...

A:  涉及知识点： 位运算 解法：  &运算对应的二进制运算，如果第i个数的二进制第k位为1，那么它可以和其余所有二进制第k位为1的每一个数产生(1<<i)的贡献(当然也包括它本身)，所以统计二进制第k位为1的个数，最后加一下 时间复杂度： O(nlogn) 代码：  #include <bits/stdc++.h> using namespace std; #define ll long long ll a[35]; int main() { int n,x; ll ans = 0; cin>>n; for(int i=1;i<=n;i++...

涉及知识点： 前缀和 solution： 题目要求的是两段不连续长度为k的连续区间和先求一遍前缀和，然后记录第i个位置的前缀和的较大值以及后缀的较大值，最后遍历一遍答案可能为负数，记得初始化为-inf std： #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 200005; ll a[maxn],pre[maxn],f[maxn],f1[maxn],f2[maxn]; int main() { int t; scanf("%d",&t); while(t-...

涉及知识点： 区间dp solution： 划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 大多数区间dp的模板都长这样子： for(int len = 1; len <= n; len++){ for(int j =1; j + len <= n+1; j++){ int ends = j + len - 1; for(int i = j; i < ends; i++){ dp[j][lens] = min(dp[j][lens] , dp[j][i] + dp[i+1][ends] +...

题目网址：https://ac.nowcoder.com/acm/problem/50439 涉及知识点：  优先队列/贪心  做法：  每个士兵都有战力Vi和一个限制Si，我们先按照每个士兵的Si从大到小进行排序 然后我们根据排好序的士兵遍历 因为士兵的Si从大到小，所以遍历的过程中，当前遍历的士兵对应的si一定是最小 所以我们可以维护一个大小由Si较小的优先队列 如果队列大小小于当前遍历士兵的Si，就扔到优先队列里，一旦士兵的人数超过限制，出队，直到队列大小等于当前士兵的Si减一  std： #include <bits/stdc++.h> using namespace st...

折半枚举 莫队算法 二分图匹配 例题：https://ac.nowcoder.com/acm/contest/216/D 树上dp（dfs） 例题：https://ac.nowcoder.com/acm/contest/4784/G splay 例题：https://ac.nowcoder.com/acm/contest/4643/B 换根dp 例题：https://ac.nowcoder.com/acm/contest/375/C 例题：http://codeforces.com/contest/1324/problem/F 例题：http://codeforces.com/contest/...

比赛主页：https://www.jisuanke.com/contest/7332 A. Wall Street Monopoly: solution: 涉及知识点：区间dp 划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 下面我们通过一个例子来了解一下这道题是如何用区间dp求解,：   如图所示，我们设dp[i][j]代表第 i 个物体到第 j 个物体相连的最小代价 设a[i] , b[i] 代表第 i 个物体的长和宽  初始化dp[1][1] = dp[2][2] = ... = dp[n][n] =...

比赛网址：https://codeforces.com/contest/1311 A 题面： 给出a和b，一共可以执行两种操作，问你最少需要的操作次数，将a变成b操作1，可以加上任意x（x为奇数）。操作2，可以减去任意x（x为偶数） solution： 判断a和b的大小以及相差的大小，最大次数为2 std： #include <bits/stdc++.h> using namespace std; #define ll long long int main() { int t; cin>>t; while(t--) { int a,b; cin>>a>...