思路： 一个骨牌覆盖两个相邻的格子，也就是相邻的格子有边相连，不相邻的格子没有边相连，所以可以分成两个集合，是偶数的和是奇数的分开，恰好与“0要素”对应。每个格子只能被1张骨牌覆盖，恰好与“1要素”对应。将没有被禁止的格子分成左右两个集合，建一个左集合节点到右集合节点的有向图（根据具体实现的原理可以不需要右集合节点到左集合节点的边）是一张二分图。最多有多少条匹配边就是这题的结果复杂度有点高：经常重复敲的代码尽量写成函数，写错了容易找到问题，也美观。 MyCode： #include<bits/stdc++.h> using namespace std; typedef long l...

思路：求某个点使得它到图中的所有点的最大距离最小。首先直接找图的直径是不对的，比如环上等距的三个点，然后其中一个点往外扩展了一个点，由于我求出来的点之后按理要放在直径的中点上，但这种情况显然不满足。对于这种带了环的题目（又叫基环外向树），我们一般是断掉环上的某一条边，再作考虑。把环上的某一条边断掉变成树再求直径就没问题了。首先外送快餐店送餐的路径不会经过完整的一个环，所以断边对正确答案没有影响。因为环上的点有两个条路径，所以删掉不会导致“错过正确答案”。先跑一遍dfs，找出环上的点编号(环上有top条边)，以及点i和i+1的边的编号是i，点top和1的边编号top。我们不知道断掉那条边最优，所...

思路：注意输入的的意思，强制在线处理。求一个区间的众数不具有区间“区间可加性”，树状数组和线段树去维护非常困难，而分块大段维护、局部朴素就非常的适合。看完题解自己在实现有点难度，蓝书就点拨一下，不给多余提示。 这题是要用到桶的，所以先把出现的离散化到自然数上。将序列分成段，每段的长度为，不一定要是，比如这题可以是，每一段的左右端点以及某个下标对应那个段也可以不用数组存，这里我分成了段。选两个段的端点组成新的区间，统计这个区间的众数，同时统计第段数字出现次数的前缀和（这里和蓝书描述不太一样，蓝色是说用存区间每个数出现的次数，数组都开不了这么大，应该只是为了点拨一下，让读者自己思考怎么实现，反复看...

题意：一颗n个节点n-1条边的树，T X Y表示给节点x及其子树涂色，C X表示询问节点X的颜色（初始都是-1） 思路：（不要漏写运算符了）vis标记入度大于等于1的点，未标记的点就是根结点。dfs序可以把子树映射到连续的区间上，维护每个节点的dfs序以及子树最后一个节点的dfs序。区间修改单点查询，修改因为是覆盖的，所以不需要lazy标记和向上更新信息，查询时，如果当前区间被涂色了，就输出，反之继续查询子区间，直到 Code： #include<algorithm> #include<cstring> #include<cstdio> #include&l...

题意：1-n个地道，m个次操作，D代表摧毁第i个地道，Q代表查询包含第i个地道的最大连续地道数目，并输出。R代表修复最近摧毁的那个地道。 第二次写了，看到题目有大致的思路，但还是不知道具体怎么实现。 思路：可以维护一个区间的左连续区间长度li[]，以及右连续区间长度ri[]。如果左孩子区间整个区间是连续的，那么当前节点的左连续区间长度等于左孩子区间长度加右孩子的左连续区间长度；当前节点的右连续区间长度的求法一样。 难点在怎么去找第i个地道的最大连续地道数目。如果不在当前区间的左或者右连续区间，那么接着访问包含节点i的区间。如果i在当前节点的左或者右连续区间，且当前节点是根结点，那么答案就是这个...

题意：给一个序列，有俩种操作，一种是求区间和，一种是将区间每个数开根号后向下取整（QQ浏览器翻译成了四舍五入，坑了我很久）。 思路：因为是对区间内的每个数开根号，没有办法用延迟更新，但是取根号在6，7次就会到1，所以如果父节点的权值等于r-l+1就不用往下跟新了，因为这个区间里每个数都是1，这样修改的复杂度就很低了总复杂度是 题目说的是对x到y进行操作，并没有说明x、y的大小关系，所以x可能会大于y，需要交换x、y Code： #include<algorithm> #include<cstring> #include<cstdio> #include&lt...

题意：给一个数组，每次询问一个区间，输出区间内最大值和最小值的差。 思路：维护一个区间最小值，一个区间最大值 Code： #include<algorithm> #include<cstring> #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int maxn=50007; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 |...

题意：n次操作，每次给出x1,x2,c，表示在区间[x1,x2]上涂上颜色c，如果能看到颜色i，就输出i并输出颜色i有几个不相交的区间。 思路：对于线段而言，如果长度大于等于1，它的两端被别的颜色占了，那么这个颜色还是能看到的。但如果涂区间内的点，如果长度等于1，它的两端被别的颜色占了，那么这个颜色是看不到的（线段树可以处理这种情况）。对输入的x1、x2扩大两倍，使得涂线段问题变成涂点的问题，便于线段树维护。 Code： #include<algorithm> #include<cstring> #include<cstdio> #include<io...

题意：屠夫的钩子有三种连起来，他可以改变某一段的钩子种类来改变钩子的长度m次。问m次后改变链子的长度。 思路：这个算是区间赋值吧，在最后在输出整个区间的和，lazy标记和处理完孩子后更新当前节点一个不能少。因为是赋值，所以lazy标记不要去累加。 Code： #include<algorithm> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; const int maxn=1e5+7; inline ll read() { ll s = 0, w =...

题意：输入t组数据，输入n代表有n块广告牌，按照顺序贴上去，输入区间，问贴完以后还有多少块广告牌可以看到（因为有的被完全覆盖了）。输入：2 4表示这块广告牌占了第2、3、4个格子。思路：这是占格子类型的题，Count the Colors是涂颜色的问题两者有点区别。可以理解为这题是涂[l,r]上的点，而Count the Colors是涂[l,r]上的线段输入的区间太大，不能直接用线段树求，需要先离散化。将左右端点离散化，先用数组存每一个端点，排序然后去重，每个端点离散化后的值就是它在数组中的下标。考虑到一个区间两个端的格子被覆盖对它的影响，如果这个区间格子为那么它就被完全覆盖了，如果这个区间...

二分图：左集合的点永远向右集合连边，右集合的点永远向左集合连边，但是集合内不能相互连边 二分图的充分必要条件：至少有两个顶点且没有奇环 二分图的匹配（判断是否有奇环）1.黑白染色 2.如果是不断加入边，然后判断是否是二分图，用并查集 二分图最大匹配问题：匈牙利算法算法思路：1.对于一个男孩子x，如果他喜欢女孩子y，且女孩子y没有舞伴——让他们配对2.如果y有了舞伴，x还是会去尝试邀请y，如果y发现她的舞伴z可以换一个舞伴，y就主动抛弃掉z（在确定z可以和别人牵手以后），和x成为舞伴增广路（交错路）：通过把原来的匹配边边成非匹配边、非匹配边变成匹配边，使得匹配的边数加一（走的路径是匹配边和非匹配...

能够解决的问题:1.求LCA2.求最小生成树3.维护链上信息(最大最小，链上和等)4.维护联通性5.维护子树信息(需要配合树)6.优化单纯性算法，在的复杂度下求最大流（这两个是在它的论文最开头提到的，资料比较少）（以上现在只是听过） 看别的大佬博客入门：【参考博客】链剖分一般分为三种：重链剖分，也就是我们常提到的“树剖”，剖分的原理是把节点个数最多的儿子当做重儿子长链剖分，并不是很常见，可以求级祖先，原理是把深度最深的儿子当做重(长)儿子实链剖分，也就是所用到的剖分方法 树剖的共同思想是把一棵树划分成若干条不相交的链，满足：1.每一个点恰好属于一条链2.在同一条链中不存在深度相同的点这样我们就...

怕npy的牛牛 思路：以当前端点为右区间向，一个指针指向合法左端点最远的位置，维护最大的区间长度其实就是一个队列，因为要枚举左端点，所以左端点要入队同时要保证队列中所有的元素和发，如果同时出现了'n'、'p'、'y'，则不断出队直到区间合法，得到该左端点对应的最大合法区间 Code： #include <bits/stdc++.h> using namespace std; typedef long long ll; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 返回符合题意的最长的子串长...

思路：从中分解出最长的连续因子，可以先分解的因子，然后双指针去找。1.如果所取因子与已经选了的因子递增，且它们的乘积小于等于n，那么选上这个点2.如果不递增，则不要以前取了的因子3.如果当前的因子和已经选了的因子的乘积不是n的因子了，那么将前面的因子抛弃（给当前的因子一个机会）直到乘积是n的因子 如果写的时候思路不清晰，执行上面的步骤容易出错，如果每次枚举递增因子序列的起点，然后分解n，从而找到递增因子序列，这样不容易出错，出错了也容易发现并解决。我的思路重点放在了因子上，写的时候概念变淡了，忽视了递增子序列必须是n的因子（写的时候会忘的，比如，求出了，明显是错的，没想到会出现这个情况）。同时...