数据规模 从别的oj网址上找的对于20%的数据， N ≤50, M≤100；对于60%的数据， N ≤3000, M ≤10000；对于100%的数据， N ≤100000, M≤500000。  解题思路 这题我做了两种解法，第一种思路不好想，但是很快，复杂度为O(nlogn)，另一种比较好想（但实际上并不好写），但是复杂度略高，为O(n logn logn)   思路一：括号序列 用到的知识：线段树 括号序列的定义 括号序列是可以理解为把一颗树拍扁，变成一个序列，这样我们就可以用各种数据结构来维护这颗树了具体的方法如下：这是一颗树：我们从根节点开始遍历，每经过一个点，就加入一个"(",每当...

用到的知识点 Manacher+线段树/树状数组Manacher算法是一种能在O(n)复杂度内求出每个点最大回文半径的算法，没学过的点这里  解题思路 暴力解法 我们第一个想到的肯定是暴力解法：枚举每一个字符串，判断是否为题目要求的one-and-half串，然后统计答案时间复杂度：O(n^3) 肯定不行，于是尝试优化 考虑使用Manacher算法进行优化 为什么想到Manacher呢？因为题目与回文串有关，往这方面想说不定就做出来了。我们先跑一遍Manacher，于是得到了所有点的最大回文半径。  重点1 此处我们不需要引入'#' ， 因为根据题目要求，我们所需的回文串一定是两个相连的奇回文...

用到的知识 线段树/树状数组+树链剖分+整体二分没学过的建议先去学了再回来做这道题 解题思路 题目要求的是不经过x的所有路径中最大的路径，那么我们可以考虑使用二分：对于每条v大于mid的路径，将路径上的点+1（路径上的点对应线段树的点，这部分使用树链剖分+线段树/树状数组实现），并统计路径总数，然后查询x点的值，如果x点的值与路径总数相等，即证明所有大于mid的路径都经过x，此时需要减小mid，重复操作，否则，则存在不经过x的路径，增大mid我们发现，这个操作可以同时针对所有询问，于是，使用整体二分复杂度O(m logm logn logn) 为什么是三个log？ logm是对离散化后的答案区...

本题的数据规模 从别的oj网址上找的：数据范围： N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。 吐槽 牛客网的分类简直迷惑，这题竟然归为了堆？而且还是5星？我往堆上靠了半天没想出来，最后换一种思路一下就做出来了 解题思路 一种很容易想到的思路是：先分别对h，v排序，然后枚举min_h，枚举min_v，枚举所有人，这样是O(n^3)，明显不行那么怎么优化呢？我们先看看题目的要求，这题的要求简化一下只有三点：1.a * (h>min_h ) + b * ( v-min_v ) ≤ c2. h>min_h3. v>min_v当我们枚...

前置知识 网络流求最大流的算法最少要会一种，安利一下我以前写的博客：通俗易懂的网络流入门：EK简单高效的Dinic算法稍微复杂但效率很高的HLPP和ISAP算法建议按顺序学习，并至少学完Dinic，因为Dinic不难，并且高效 无源汇的有上下界的可行流 名词解释 无源汇：不区分起点和终点的闭合图有上下界：每条边都有一个流量上界和流量下界可行流：此处仅考虑是否存在可行方案 解法 因为要跑网络流，所以我们引入一个起点ss和一个终点tt，接下来，考虑如何加边：对于原图中每条边{s,t,low,up}（分别表示起点，终点，下界，上界），我们在网络流图中加入一条边{s,t,up-low}(分别表示起点，...

这道题可以作为A*的入门题 什么是A* 这是A* 的定义：A*搜索我的理解是，A*是一种剪枝方式，可以广泛运用于搜索中。A*的思想是定义一个估值函数，表示最理想的情况下还需要多少步才能达到想要的结果（真实情况所需的步数会大于等于估值函数的返回值），如果当前步数(定义为g(x))+估值函数(定义为h(x))已经超出了前面的最理想情况那么就可以直接结束搜索 本题的估值函数 前面说了，估值函数表示最理想的情况，那对于本题来说，我们只需要计算当前的状态与标准状态有几个不一样，那么最理想的情况下就只需要不一样的点的数目-1步，为什么是-1呢？因为最后一次交换会使得两个点变得和标准一样，所以是-1 int...

数据规模 题目里没给出数据规模，我从别的oj网址找的：所有数据满足 2<=n<=5000 1<=m<=200000 1<=E<=1e7, 1<=ei<=E,所有的E和ei都为实数 用到的知识 最短路算法（spfa，dijkstra都可以）+可持久化堆 解题思路 此题可视为k短路题的模板，由于我讲的可能不是很好，这里推荐一个教程：俞鼎力大牛：堆的可持久化和k短路由于该教程已经讲的比较细致了，所以我就简单地概括一下，看不懂的地方可以去看教程 构造最短路径树和边的分类 我们先从n点跑一遍最短路，这样就可以得到n为根的最短路径树，然后，我们就可以将边分为...

解题思路 用到的知识点：st表+堆 思维过程 按照题目的要求，我们要求所有长度为[l,r]的子区间中最大的k个，首先，我们不可能遍历所有的子区间，因为那是O（n^2)的，我们考虑贪心 先考虑k==1时： 当k=1，我们只需要找最大的一个子区间，但是，这也要遍历所有子区间，于是考虑如何用较小的时间找出最大的子区间，由于题目的n为500000，所以一般来说，存在O(n)或者O(nlogn)遍历子区间的方法，而且很可能是O(nlogn) 首先，通过预处理前缀和数组sum，我们可以在O（1）的时间得到一段区间[i,i+k]的和，即sum[i+k]-sum[i-1]然后，我们发现以i为起点的所有子区间中...

题目大意 给n个点m条无向边，每条边有边权，当点1到点i的最短路的最后一条边被封住时（只有最后一条边，其他边还可以用），求点1到点i的最短路，i取2，3，……，n（被封住边只影响此次的结果，不影响其他点的结果）,如果被封住后到达不了i，则输出-1，否则输出被封住边后的最短路 解题思路 思维过程 我们肯定要先跑一遍单源最短路，此时，我们得到了从点1到任意点的最短距离（后文用dist数组表示）设到i的最短路径上除i以外，最后一个点为x，我们考虑另一条经过y的路径，如果i与y有边，那就判断是否更新答案 ,其中val表示i与y的边的边权，那么我们只需要考虑与i相连的除了x以外的所有点即可，但是，直接这...

本题坑点 题目没有给数据规模，我去别的oj网站上查了，是 100%的数据满足N,M<=100000,D<=3 解题思路 “看到x要先于y”这类字的时候，第一反应就是拓扑排序（不知道拓扑排序点这里 ），但是有一个问题，如果用拓扑排序，我们只能得到字典序最小的方案， 不能满足题目要求的使得小A能尽量先吃到质量高的菜肴，那怎么解决这个问题呢？我们在做拓扑排序的过程中，会优先考虑路线的起点编号大小，但是我们的目标却是使得每次选取的路线终点的编号最小，那么我们可以通过反向建边，寻找字典序最大的方案，最后反序输出就可以了 注意事项 重边问题 本题存在重边，所以不能在加边的时候就统计入度，去除重...

解题思路 这题一共三个询问，我们可以先从最简单的第三个询问开始分析 第三个询问 我们可以用线段树（树状数组）来维护所有已经熟的食物，每次询问的时间复杂度为O（logn） 第一个询问 由于我们在做第三问时建立一颗线段树（树状数组），所以我们这里可以直接用线段树来解决这一问：若整个区间的和为0，则没有食物。若有食物，则：用二分来找出有值但最小的点（左右端点相同的区间），该点就是所求的食物编号，每次询问的时间复杂度为O（（logn）^2），然后将该点减一,复杂度O(1)，所以，这步总的复杂度为O（（logn）^2） 第二个询问 我们给每一个食物建一个队列（因为同一种食物煮熟花的时间相同，所以越晚入队...

前言 我看到题解区清一色的离散化+树状数组，所以我就写了一点不一样的，其实逆序对问题用归并排序也是一个很好的解法 题目解释 题目描述中的个子区间指的是n个一个数的子区间，n-1个连续两个数的子区间，n-2个连续3个数的子区间，……  题目的坑点 本题的数据规模很大（n<=1000000(一百万)）,所以，不仅是时间比较紧，答案也超过了longlong（一定要注意，我因为这个浪费了好多时间）,我比较懒，用了int128，也可以自己手写高精度 解题思路 归并排序！！！ 为什么能用归并排序解决逆序对问题？ 归并排序的基本原理我们就不说了，不会的可以去网上搜索，网上有很多。我们知道归并排序在合并...