①最远曼哈顿距离 :  1.1:二维最远曼哈顿距离模板： ABC 178E 传送门:https://atcoder.jp/contests/abc178/tasks/abc178_e 两点间的曼哈顿距离为: 那它的结果可能有四种。取最大值即是它的结果: 稍微整理:将相同的点放在一个括号中得到： 不难发现:如果我们分别对 x + y 和 x - y 做集合，那么答案是: 推广到N个点之间的最大曼哈顿距离也是一样。 问题2:如果要求某一个点到其他点的曼哈顿距离：四种情况： 把它当作 然后再在集合中找对应的最值和它做运算即可  1.2:N维最远曼哈顿距离模板：POJ2926 对于1,2,3...

传送门：https://ac.nowcoder.com/acm/contest/7329/E 题目大意:给你一个长度为1e6的排列,让你统计 区间[L,R]是一个值域为[L,R]的排列 的 区间个数. 昨天比赛的时候看了一下题目以为是析合树，就没写了emm，其实正解思路很简单。。 题目思路: 1.对于每一个点 x，我们求出以它为右端点 的 【合法左端点 L 的区间范围 】使得2.再求出以x为左端点的 【合法右端点R的区间范围】 使得 上述算法实现方式(可选): 单调栈 + 二分 / ST表 + 二分 (后者注意常数问题) 现在考虑两个点对.当 时， 点对产生贡献。 现在问题转化为：在...

核心:在于状态转移方程的状态只有0和1。可以将转移优化成位运算。 一.NC32C简单瞎搞题 传送门:https://ac.nowcoder.com/acm/contest/132/C?&headNav=www 题目思路： ,类似于:分组背包，每组必选的dp。那么朴素复杂度为： 发现dp其实上是一个bool数组，我们将其代替成bitset.然后对于一个确定的xi. 它对背包容量的转移就是位运算的左移.再开一个滚动数组直接dp即可。 二.AGC020-C --子集和数组的中位数 传送门：https://atcoder.jp/cont...

题目大意：  给你一个 长度为 N (N <= 300) 的 01字符串,再给一个正整数M.每次操作可以将一个位置取反，或者将一个长度为M的倍数的前缀取反。问最少需要多少次操作，才能使字符串成为一个循环节为M的循环串. 题目思路:(未验证代码正确性)     发现制约关系: 循环节的长度与其在原串中的个数.尝试分类讨论. 1. 当 m < sqrt(n)时,  循环节长度不超过 sqrt(n) = 17. 所以可以 2^17 枚举循环节的内容.     已知循环节的内容S. 由于我们需要支持前缀取反的操作.对于原串的每一个循环节,都提供两种决策: 1.将其变成S  ,代价为c0. ...

算法大意：给你一张无向图，问你里面的三元环(a , b , c)的个数. 算法思路：复杂度的证明很像根号分治 做法： 记录度数，度数大的指向度数小的。度数相同的话编号大的指向编号小的。就原图变成一个DAG了。 无环 是显然的。 然后对于每个点X，将出边记录下来,打标记。再对于X的出边的点，枚举出边，看是否是 X的出边的点。是的话就计数。 复杂度: 原理:     考虑任意一个三元环,经过转换之后它一定长这样(想想为什么?),所以所有环都会被记录一次且仅一次。 证明：  复杂度来源于两个部分： 一。枚举出边 二.枚举出边的出边. 一部分复...

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6071 题目大意：给你一个 含四个点的带权环。问你从 2点 走到 2点 的 权值>= k 的最短路. (边权 <= 30000 , k <= 1e18) 题目思路: 这题的思维难点在于:如何表征出所有可能的路径情况. 类似同余最短路的思想: k如此大,但是边权很小,我们考虑将边权放入状态中.. 问题一:如何确定剩余系X.   由于我们一定要回到2点.所以不妨选择一条 [与2相连的边w * 2] 作为剩余系. 问题二:合理性? 首先一点: 此过程中访问节点的顺序不重要.重要的是 每条边...

P3403跳楼机 传送门：https://www.luogu.com.cn/problem/P3403 题目大意：一个线段为[0,h - 1].你从0开始，每次可以朝任意方向走 x , y , z步。(前提是在线段内)。 问你有多少个整数点是可以到达的。(x , y , z <= 1e5 , h <= 1e15). 题目思路: 首先，由于h过大，不能直接dp递推。所以自然考虑 在 mod x 剩余系下 求解问题。 那么不管 y , z 走多少次。最终都会落在 mod x 的剩余系中。那问题规模就变小了。  显然，可能 mod x 的剩余系中 有些值永远取不到。但值一旦第一次被取到...

传送门:https://vjudge.net/problem/CodeForces-808G 题目大意:给你字符串S,T。字符串S中有问号，可以随意填a ~ z 中任意一个字母。问你如何填使得T在S中出现的次数最多(可以重复匹配)。求这个次数。(S , T <= 1e5, |S| * |T| <= 1e7) 题目思路:   看到|S| * |T| <= 1e7,自然可以想到将这两维放入dp中。即  考虑一个重要的问题：当i,j失配的时候，j如何移动? 注意到题目中说了可以重复匹配，那么j = next[j]。但是 S[i] 不一定就等于 T[next[j]].所以需要暴力跳...

传送门:https://vjudge.net/problem/CodeForces-526D 题目大意：对于字符串的每一个前缀，询问是否能够看成 k + 1 个 A 和 k个B交替形成的字符串。 题目思路: KMP 找循环节 + 数学推导 着实被这个题解法秀到了. 首先想要答案存在，将 S = A + B。这个S肯定是这个前缀的一段循环节。 我们知道最小循环节为:  我们知道： 由于n是定值，那么 就是求是否存在一个正整数 q : 所以接下来就判断区间中是否包含正整数，可以将左端点的值L向上取值，右端点的值R向下取值，判断 L...

传送门:https://vjudge.net/contest/391081#problem/A 题目大意: 给你一个字符串，让你统计其中 两个等长且奇长的互相重叠组合而成的回文子串的个数. 题目思路:类似于HDU5371.都是Manacher+数据结构维护 解法一：树状数组 我们通过Manacher得到p数组。问题可以转化为: 可以看出这是区间求和问题。又因为可以离线所以考虑排序。 1.我们对 j + len[j] - 1 降序排序，然后有序循环 i 从 n -> 1. 2.将所有 j + len[j] - 1 >= i 的j一次贡献插入树状数组，然后对[i - len[i] ...

传送门:http://codeforces.com/problemset/problem/159/D 题目大意:给你一个回文串，问你有多少对不相交的回文串对数. 题目思路： 解法一:dp预处理 + 后缀和预处理.  首先我们利用dp预处理dp[i][j]代表区间[i][j]是不是一个回文串. 然后利用dp值计算每个后缀[x,n]中有多少个回文子串，记作aft[]. 然后再枚举前缀以y为结尾的回文串有多少个. O(n)扫描前后缀分割点,计数相乘即可。 AC代码:http://codeforces.com/contest/159/submission/91638194 解法二:Manacher ...

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6769 题目大意：给你一棵树，每条边有两种权值a,b.让你从里面选出k条a,n - k - 1条b.使得整棵树的直径最小. 题目思路: 让我们最小化直径。直径又是树的最大路径。那么就是最小化最大值。自然可以想到二分答案。 其实也是:要保证整棵树的直径最小。如果直接dp的话，你无法保证经过每个点的最长路径都是最小的。 我们的目标是要一个整体最小化，但是dp无法做到.不过如果已知一个直径长度A。那么我们dp要做的就从 [最小化答案] 变成了 [寻找可行解].直径这个变量就从 [目标函数] 变成了 [限制条...

传送门:https://blog.csdn.net/weixin_44778155/article/details/104725178 题目大意：给你一棵带边权的树，放k个机器人在s点。让你安排这k个机器人遍历完整颗树，使得价值最小。(n <= 1e5 , k <= 10) 题目思路: 容易发现这是一个树上背包。 令 解释：为什么有 "在i子树中停止"这句话。是因为机器人可以随意移动。它可以先进入一颗子树，再出来。剩下的基本就是套树形背包了 那么 注意:dp(i,0)的含义就是没有机器人在这棵树停止，那么这条边就经过两次.(来一次,去一次)

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6540 题目大意：给一棵含有n个点的树，里面含有m个关键点。问你有多少种选关键点的方案使得选出的点中两两之间的距离 <= dist. (1 <= n , m , dist <= 5000) 题目思路: 重点考虑转移的时候如何表征出两点之间的距离: 对于一颗子树，其实我们只需要知道它所选的最深关键点的深度，就可以进行dp的转移了。所以将深度放入状态中就可以直接判断子树之间是否能够转移了.所以自然我们想出以下转移方程: 之后，对于一个新增的子树,它可以向主树转移一种深度。接下来就是套树...