分析 首先这道题在出题人没有专门卡的情况下是一道超级简单题。。。当以1为根时，转移如下 那么我们考虑换根DP每次只需要除以转移到的儿子在当前节点的贡献即可即乘逆元即可转移成功 本题是有DP[x]=Mod-1的数据的而没有逆元所以我们需要换一种方法换根因为我们要排除当前儿子节点的贡献只算上两侧节点所以我们考虑维护前缀积和后缀积即可详情见代码 代码 //CF543D #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <ve...

分析 首先亮瞎我狗眼的便是这个阔怕的数据范围 所以，这意味着我们直接暴力是没有问题的所以我们直接枚举开始点BFS+优先队列处理最短路然后枚举另一个点判断两人之间的最小移动障碍物个数是否Limit即可时间复杂度： 代码 //P4162 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <cmath> #define LL long long #define Cl(X,...

前言 写这篇题解主要是复习一下可能会写的比较省略 算法 虚树+倍增+动态规划 引入 看到这道题我们立马可以想到一个DP方程我们设DP[i]表示使与其子树中的所有关键点分开的最小代价对于一个节点以及他的儿子 若是关键点，那么DP[u]+=W(u,v) 若不是关键点，那么DP[u]+=min{DP[v],W(u,v)} 但我们发现这是一个的暴力！但我们认真观察数据范围，发现 所以我们非常希望能够把时间复杂度的有关因素转移到 上去这时候我们就需要引入虚树的概念了 简介 对于虚树，主要是处理当问题中无用信息非常多时，简化问题的一种思想对于样例的第2个询问我们发现，有用的其实就只有这几个点即：我们在...

分析 我们考虑弱化版本：对于求一定范围内与互质的数个数那么就是 所以答案就是枚举所有的质因子，进行简单容斥即可所以我们需要知道容斥系数这里我们就可以利用莫比乌斯函数的另一种用途了：作为质因子的容斥系数因为莫比乌斯函数满足 所以我们直接线性筛所有的莫比乌斯函数再二分答案判断即可时间复杂度： 代码 //CF920G #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL long l...

吐槽 看完题之后的心理反应:这这?不是一个数学小蓝皮上母函数的模板题吗想了一会儿,发现还是WTCL 分析 一道简单的容斥DP题我们发现我们先考虑一下弱化版本如果每个硬币都不受限那么我们就可以直接暴力背包求得所有方案书 所以我们现在来考虑一下本题发现,我们可以容斥解决先把答案设为DP[Cost]然后减去有一个超过限制时的方案数加上两个超过限制的方案数 当然,前提是可以超过限制时间复杂度: 代码 //P1450 #include <algorithm> #include <iostream> #include <cstring> #include <cs...

分析 看到这道题断定就是一个简单的圆排列问题但由于我们不知道有几对情侣会在一起那么我们求一个补问题枚举坐在一起的情侣的对数再进行简单容斥即可容易推出公式: 由于本题需要的是的时间复杂度所以我们需要对于每个组合数求得Fac[]表示前缀积Inv[]表示前缀积的逆元那么 即可解决这个问题 代码 //Newcoder 19857 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define LL l...

分析 简单分析可知将置换关系转换为DAG那么，我们关心的只是这个这个DAG中哪些环并且最终的答案为我们将每个环大小质因数分解 那么我们最终的答案为 因为质数非常的少这里我们想到了唯一分解定理可知，对于多个幂（）的和如果不相等，那么他们的积一定不相等所以我们可以考虑直接枚举质数以及质数的选取个数那么DP[j]+=DP[j-Prime[i]]背包直接转移即可 代码 //P4161 #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include...

分析 看完题，首先这绝对是一个DP题我们设 Height[]表示高度 Cost[]表示花费 DP[]表示以当前点为截至点的花费最小值 Pre[]表示花费的前缀和 算法一 那么DP方程： 那么我们就得到了一个的转移方程式 算法二 我们发现，对于每次的修改，需要的只是最后一次从转移到的最小值那么我们考虑由这个性质来维护当我们把位置上的值改为时若要转移到位置由转移式： 那么我们设 A[i]=-2*Height[i] B[i]=Height[i]*Height[i]-Pre[i]+DP[i] Loc=y 我们发现这一次转移的最小值就是的最小值所以，我们预处理出A[]和B[]即可，将A[]看作斜...

分析 由于本题要求联合权值之间的Dist为2他们之间刚好夹着一个点为了处理方便，我们肯定是直接枚举中间夹着的点那么，我们来考虑需要求的两个东西Max（最大联合权值）和Ans（联合权值之和） Max：对于一个点来说，以他为中心点的联合权值最大值一定是与他相连的最大值和次大值之积所以对于最大值我们就解决了 Ans：那么对于和，我们考虑每个点为中心的所有点的贡献设每个点权值为那么总贡献为 所以可得对于每个点贡献为 所以我们可以预处理出每个点的,即可 综合上边两个处理，即可快速得到答案时间复杂度： 分析 //P1351 #include <algorithm> #include ...

分析 由异或的性质 我们设表示号节点到根节点路径权值的异或和所以对于一条树上简单路径其异或和那么我们就可以转化题意：给定个值，求 所以我们可以直接二进制拆分，建立01Trie树贪心走异或最大值即可 代码 //×Òì»ò·¾¶ #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define LL long long #define INF 0x3f3f3f3f #define Cl(X,Y) me...

分析 当我们看到区间的多次查询时，首先想到的可能就是离线了我们尝试将查询的区间右端点排序那么我们在向右移动指针时如果前边出现了这个值那么就可以将Pre[i]更改为i-Pre[i]因为我们现在还没有扩展到右边的点所以我们可以直接区间查询的最小值线段树即可因为我们需要将数值作为下标，所以需要离散化一次 当然，此题还有ST表+二分做的，可以参考这位巨佬或者这位巨佬 蒟蒻有一个神奇的思想--三维偏序，但感觉空间开不下。。。故咕 代码 //CF522D #include <algorithm> #include <iostream> #include <cstring&...

分析 由于我们需要求出最后序列最小值最大所以我们直接可以想到二分答案经验告诉我们，我们需要先考虑比较特殊的数列位置从最左边开始考虑若果当前不成立，那么我们将他加到成立为止并是以当前位置为起点的向后加1所以我们需要的是区间修改，单点查询可以的树状数组当然更可以的差分可以证明这种贪心是绝对最优的需要注意的就是数组不要越界了 代码 //CF460C #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #...

分析 本题主要就是一个转化当我们看到数据范围，就可以大胆猜测较高复杂度的算法因为维护最大值比较麻烦我们考虑用二分答案限制最大值然后就可以顺理成章的想出将的路径长度标为1跑一个最短路如果最后的Dist[T]那么这就是一个可行的解以此二分即可求得答案 代码 //P1948 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <cmath> #define LL lon...

分析 本题给出的道路和航线其实就是单向道路和双向道路所以我们直接正常建边就可了由于题目保证了不存在环，那么就绝对没有负环情况但因为有负边，所以我们需要用SPFA所以我们直接套板子即可当然，这里我们使用SPFA的优化（slf优化 或者 lll优化）（机房大佬说想要不一样就要Tarjan缩点+Dijkstra） 代码 //LOJ 10081 #include <iostream> #include <cstdio> #include <algorithm> #include <deque> #include <cmath> #includ...