给一个基环树森林，求每棵树的直径的和，基环树的直径定义为，从一个点出发只能走到没走过的点（即一个环不能把所有边都选），所经过的路径边权和最大 这题不是很难，只是略微麻烦，代码也好打，一遍就过了对于每棵基环树独立搞 先找到这棵树的环，这个过程分为两步，第一步找到换上的一条边，可以利用类似网络流的存边方法给走过的边记录是否走过，给走过的点标记是否走过，当走一条没走过的边可以走到走过的点，说明这条边是环上的边，第二步从环上的点出发如果走一条没走过的边发现可以走到环上的点，说明这个点就在环上 找到环后，基环树会是这样的： 以下称环上的点的子树指的就是，以环上一点作为根节点，屏蔽要经过环上其它点的...

给对区间，要求每对区间恰好选一个使得选出来的个区间有交集，问有多少方案数 注意到区间的值域也是，考虑从值域入手，也就是枚举每个点看有多少种方案使最后的交集包含这个点设有对区间的两个区间都包含这个点，那么就有种方案显然，这样的方法会算重，因为不同的点可能对应相同的选择方案，考虑当前枚举的点是，假设对应的方案数为，如果点相比点没有新增的区间，也没有减少区间，那么和方案数是完全一样的，如果比新增了一些区间并没有减少区间，那么对应的方案数是包含了对应的方案数的，新增的方案数是二者的差，而如果减少了一些区间，那么我们记减少了后对应的方案数为，新增的方案数仍然是二者的差，我们只需维护这个过程即可，总复杂...

个物品有长和宽，个盒子也有长和宽，一个盒子最多可以装一个物品，问个物品能否都放进盒子，物品和盒子不能旋转先离散化长和宽，将物品和盒子按照长从大到小排序考虑到当前物品时将所有长大于等于当前物品的盒子全部放进一个权值线段树，权值线段树维护长大于等于当前物品的并且宽为的盒子有多少个，则在线段树上二分出宽刚好大于x的位置，将对应数量减即可 我是傻子，用multiset不需要离散化还自带二分和删除，就当是线段树二分练手吧 include<cstdio> include<algorithm> usingnamespacestd; constintmaxn=2e5+10; con...

也许更好的阅读体验 个球排成一列，每个球都有自己的颜色，每个球的颜色都互不相同，且均在范围内，第个球的颜色为。你需要将这些球重新排序使得第个球的颜色为。另外，你还有个颜色为 由于这些球的性质特殊，你只能通过以下两种方式将他们排序： 将一个颜色为的球插入到序列中的任意一个位置。显然你只能执行这种操作次，因为你只有个颜色为 选择一个和零球相邻的非零球，将其取出并放到序列中的任意一个位置。每执行一次这种操作将会产生 你可以以任意顺序执行这些操作，在所有操作完成后，所有颜色为 对所有的求出答案。 考虑放在某个位置后，如果有一个数不在旁边，并且想让这个来取出，那么必须把之间的球都取走 取出的球...

也许更好的阅读体验 给你一棵有个结点的树，定义为将在原树中所有距离大于等于的点对间连一条无向边所构成的无向图（距离定义为简单路径中边的数量）。 对于所有，求中连通块的数量。 设树的直径为，对于的情况，中没有边，连通块的数量为 以下是我的思考过程，逐渐从比较麻烦的想法变得简单 可以先看正解，没看懂再回来看 考虑从大变小的过程，之前连了的边变小后也会连，因此可以考虑每次增加的新点 这时候想到了直径，假设整棵树只有一条直径，时，只有直径的两个端点是连在一起的，考虑变小的过程，因为任意一个点到其它点最远的距离就是到这条直径的某个端点，最开始两个端点连了边，当变小，可以认为从直径的一个端点出发最...

也许更好的阅读体验 给一个长度为的环，上面有条线段，问在第条线段必须被选中的条件下覆盖整个环最少需要多少线段，不存在线段覆盖线段的情况，注意是线段，和之间少了这一段 用倍增，预处理出一个类似表的表出来环的问题先倍长数组，然后将线段也双倍将线段按照左端点大小排序，由于不存在线段覆盖情况，因此可以肯定没有两条线段有端点相等的情况，并且左端点更大的线段右端点也更大设表示排序后第条线段开始往后挑选条线段并且使得覆盖的长度最长，最后一条线段的序号考虑状态转移时并不是直接等于，因为最后一条线段是已经被选了的，因此应该从下一条线段开始这里的下一条线段并不是序号+1，而应该是左端点在最后一条线段右端点范围内...

个点，每个点有点权，有个区间，要选择一些点使得所有区间里都有点，求最小总点权 广东省赛好水啊，感觉单挑都可以至少题这题属于一眼题了，不知为何过的很少设表示这个区间全部满足条件并且选择了的最少花费令有一个点且点权为，则答案就是转移方程其中要满足之间没有要求区间，考虑的合法区间，假设为，当变为时，如果有一个区间以i结尾并且左端点在之间，那么对于来说，的区间会变小，这个过程中，的区间只会越来越往右变小，因此可以用单调栈维护这个 include<cstdio> include<algorithm> definelllonglong usingnamespacestd; co...

也许更好的阅读体验 个点编号，每个点有点权，要求选若干个点使得总点权最小，其中编号为和的点必须选且点权为，同时满足任意两个被选的点之间的距离不超过，此外还会给一个串，表示这些点是否为必选的点现在会给个询问，每个询问为如果将编号为的点权修改为的答案会是什么多组数据 最近做做往年题，这题算是个金牌题，做的快可以摸金的那种，意外地发现很简单没有修改的话是个很经典的单调栈优化设表示这个区间满足条件且在i选了i的最小花费，转移方程为，这个过程单调栈优化可以做到，其中属于对于某个位置必须选择，那么就在计算该位置的值后将单调栈清空再将该位置放进去，相当于之后的选择一定有这个位置了正着做和反着做差不多，再设...

也许更好的阅读体验 给个区间，需要在每个区间选一个数，使得将这些数与起来的结果最大，个区间相互独立（即可选择相同的数） 从大到小考虑每一位是否能填，同时构造出每个区间选的数是什么设表示第个区间在满足之前贪心的条件下，目前选的数是什么，现在考虑到第位了，假设第位为，则会变成，之后能表达的数在区间范围内如果这个区间和有交集，则说明第个区间在满足前面位的情况下第位可以为，若所有区间第位都可为，那么所有的，否则就要考虑第位是否为若本就不可为自不必说，而如果第位可以为，也可不为，我们可以考虑设之前说的区间为，现在我们其实并不关心第位如何，为也好，不为也好，只要能让我们在考虑之后的某位能为时能尽可能满足...

也许更好的阅读体验 给个数，将这个数所有子区间的作为一个集合，求最小的没有出现在中的数有个数，所有子区间的构成集合，第一个未出现的数是， 考虑已知一个区间的，此时将区间往两边扩大，是不降的 在知道上面之后，我们想要知道所有区间的中最小的未出现过数，因此我们不需要一开始就知道所有的，考虑按从小到大构造出，又知道区间在区间变大的过程中是一直增大的 立马就能想到用一个小根堆，最开始将每个位置上的数存进去表示以这个位置作为区间的起点，用表示当前考虑是否是答案，每次取出最小的数出来看是否等于，如果等于那么就不能作为答案，需要增大，然后将堆顶的元素取出来让它的区间往右走一步再重新插进堆中，这样就能保证当...

也许更好的阅读体验 在一个行列的网格图上随机选择个点。定义当前局面的分数为最小的可以围住这 请求出所有局面中分数的期望值，输出时对取模。 先说经典的容斥方法，考虑围住这个点的矩形的大小为个点全部落在这个矩形范围内的方案数为接下来考虑围住个点的最小矩形并不是的方案数而这种情况下，一定有一条边上没有点容斥的方法就出来了，每次考虑几条边上没有点然后考虑一下是什么样的情况，如何加减即可 另一种方法是直接推设表示围住个点的矩形大小为的方案数则很容易有复杂度是的，对这个式子变形其中都可看为常量，我们只需维护这几个前缀和就可以方便的转移了: include<iostream> usingn...

也许更好的阅读体验 简述 cdq分治是一种思想：将问题从中间分成两个部分，并且满足只有一部分（设为左）对另一部分（设为右）有贡献，右部分对左部分是没有贡献的，然后计算左部分对右部分的贡献，再继续分治。最简单的运用应该就是归并排序求逆序对吧，将序列分成两半，然后考虑左边序列的数对右边序列的数构成了多少逆序对。 正确性 拿求逆序对举例，在分治的过程中，左边序列中的逆序对已经在左边求完了，右边序列中的逆序对也求完了，只剩下还有左边序列中的数与右边序列中的数构成的逆序对还没求，因此只需处理左边与右边的数构成的逆序对数量。 运用 二维偏序 二维平面上有若干个不同的点，求有多少个点对满足要求会求逆序对首...

也许更好的阅读体验 include<stdio.h> include<string.h> / ALTERNATINGBITANDGO-BACK-NNETWORKEMULATOR:VERSION1.1J.F.Kurose ThiscodeshouldbeusedforPA2,unidirectionalorbidirectional datatransferprotocols(fromAtoB.Bidirectionaltransferofdata isforextracreditandisnotrequired).Networkproperties: onewa...