题目链接 显然，一棵树有条割边（也指桥），于是如果要使最后只有至条桥，那么当时候，实际上我们要将长度为的链给“取消割边”，而取消割边的方法就是通过连边。一条长度为的边，会产生的贡献。 所以，我们假设现在找到的一个点举例目前的根节点距离为，要找一个根节点的另一个方向的距离为，那么此时产生的贡献是。所以，我们维护一个“个数”，一个“”就可以求解了。 然后，点分治的基本操作了。 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cs...

因为边的数目很少，只有5000，那么我们不妨对边的权值排序，然后5000*5000的进行枚举即可，判断连通性就可以了。 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue&g...

很容易想到正确的解法，首先，我们可以知道（2 * 3 * 5 * 7 * 11 * 13 * ……）最多19个质数相乘就会达到1e9级别的。于是，我们可以考虑质数，我们可以知道一个数最多就是分成20个质数，所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢？于是就有了米勒罗宾检验素数。此处套个板子…… 然后，我们对于每一个质数，我们去求一个每一个相连子树的最长的树的直径即可，此处可用树形DP，或者跑两次dfs任意，都是O(N)。 #include <iostream> #include <cstdio> #include <cmath> #in...

题意：有N条线段，每天线段有左右端点l、r，并且线段的长度是r-l+1，且线段有价值c，现在我们想要找两条线段，使得两条线段的长度和为X，并且两线段不相交。如果没有这样的答案输出-1，否则输出最小价值。那么，很简单的，我们可以对l进行生序排序，于是直接查r在“l”之前的线段，我们用map去记录一下对应的长度，然后就可以了。 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <al...

经典的字典树问题，我们知道查询任意两点的路径异或值为所以，我们求出从根节点到每个节点的异或值，然后将这些值放到字典树上去进行查询就可以求得每个点的与其余点的最大路径异或权值了。 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <s...

我采取了分别考虑的方式来解该问题，也就是将x和l、r的位置进行考虑了进去。  于是，我定义了如下几个数组，分别表示： pre[x]包括x的前面的所有的货物都运送到x所需的花费suff[x]包括x的后面的所有的货都运送到x所需的花费ans[x]所有点的货物都运送到x所需的花费dis[x]表示x点到1号点的距离psiz[x]包括x的前面的所有的货物的前缀和ssiz[x]包括x的后面的所有的货物的后缀和 x < l时候 这时候，答案其实可以考虑称用l的后缀答案减去r+1的后缀答案，然后还少减了r+1的后缀部分到l上的贡献，然后在加上这部分，就求得了[l, r]所有货物都运到l上时候的花费了，然...

链接：https://ac.nowcoder.com/acm/problem/15665?&headNav=acm来源：牛客网 题目描述小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。 小明只能向上下左右相邻的格子移动，每移动一次花费1秒。 有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵...

链接：https://ac.nowcoder.com/acm/problem/17065来源：牛客网 有N个权值，a[1]……a[N]，现在要求一个子序列，满足对于所有的i<j，有 。 求解这样的子序列的个数。 那么，我假设dp[i]表示以第i位为结尾的符合要求的子序列的个数，那么 于是，答案就是 但是，我们还没有说明如何去判断关系呢！于是有 说明了，等式存在线性传递关系。 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include &l...

求K个不相交字符子串的最大相同前缀长度x。  很容易往后缀数组上靠，但是这还不够，因为很容易就想偏了，这里，我们想处理一个是不重叠，一个是最大的前缀相同，于是，不妨设最长前缀为x，然后二分这个x，这是因为height的关系具有连续性，所以这样就能很清晰的划分出来我们需要进行处理的sa的区间了。  然后我们对于这些后缀的前缀下标，我们存进一个升序堆内，贪心来选，看看能否有K个以上的满足条件的不重叠子串，于是二分的判断条件也就写出来了。  注意的是，判断二分x==0的时候，直接返回true，或者从1开始判断。 最后，欢迎来我的博客食用呀：https://blog.csdn.net/qq_41730...

树形DP首先，中文题，就不再阐述题意了。然后，具体怎么dp呢？首先不考虑树上，如果是一条序列上的话，肯定就是这条序列上的最小值了，现在其实实则变成了多条序列。我们动态规划的主要思想就是在于，是割下面的点的代价要小，还是割目前的边要更好些，所以用dp[u]记录，u结点为子树的根结点的时候，断开它到它的叶子结点的最小代价是多少。然后动态规划的过程就简单了： #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> ...

https://blog.csdn.net/qq_41730082/article/details/104028168

DP + 组合数学  首先，我们很容易的发现，如果数量是大于M的部分，是可以直接用组合数学来求解的，但是呢，前导0的情况，我们是要减去的。 再看，剩下就是相等的部分了，我们可以写列写一个 暴力DP来看。不难发现，每个点的值都是与之前的dp[1~i][j-1]相关联，但是，我们1～i可以通过01背包的方式来做到降维，使得最后的复杂度变成 的。 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #inclu...

先发一下我的CSDN博客哟：https://blog.csdn.net/qq_41730082/article/details/103643159 首先，这道题的思维展开，肯定不能把所有的点都用进来，那么，选择的点，我们可以只考虑起点和终点还有特殊的像M条链接边的点了，所以，点数的上限就是1e5，而不是2e10了，这就是对于点的优化了。  再者，比赛的时候我处理这1e5个点的时候用了两两平方的方式来求LCA，尝试着卡数据随机……但是很显然，这次的数据造的很用心，这样的做法确实被卡掉了，于是就是想办法去优化这个求LCA的过程。  我们可以知道，最后的时候1～K棵树都会分布着一些点，那么的话，我们...