钱逸凡

题解

/ 注册

全部文章 / 题解（共12篇）

捉迷藏__题解

数据规模从别的oj网址上找的对于20%的数据， N ≤50, M≤100；对于60%的数据， N ≤3000, M ≤10000；对于100%的数据， N ≤100000, M≤500000。解题思路这题我做了两种解法，第一种思路不好想，但是很快，复杂度为O(nlogn)，另一种比较好想（但...

线段树点分树堆括号序列点分治

2020-11-21

5 796

Palindrome__题解

用到的知识点 Manacher+线段树/树状数组Manacher算法是一种能在O(n)复杂度内求出每个点最大回文半径的算法，没学过的点这里解题思路暴力解法我们第一个想到的肯定是暴力解法：枚举每一个字符串，判断是否为题目要求的one-and-half串，然后统计答案时间复杂度：O(n^3) 肯...

树状数组线段树字符串 Manacher 回文串

2020-11-17

0 716

网络__题解

用到的知识线段树/树状数组+树链剖分+整体二分没学过的建议先去学了再回来做这道题解题思路题目要求的是不经过x的所有路径中最大的路径，那么我们可以考虑使用二分：对于每条v大于mid的路径，将路径上的点+1（路径上的点对应线段树的点，这部分使用树链剖分+线段树/树状数组实现），并统计路径总数，然后...

树状数组线段树整体二分树链剖分

2020-11-15

0 575

组队__题解

本题的数据规模从别的oj网址上找的：数据范围： N <= 5000 ,height和speed不大于10000。A、B、C在长整型以内。吐槽牛客网的分类简直迷惑，这题竟然归为了堆？而且还是5星？我往堆上靠了半天没想出来，最后换一种思路一下就做出来了解题思路一种很容易想到的思路是：先分...

差分

2020-11-10

0 687

有上下界的网络流问题

前置知识网络流求最大流的算法最少要会一种，安利一下我以前写的博客：通俗易懂的网络流入门：EK简单高效的Dinic算法稍微复杂但效率很高的HLPP和ISAP算法建议按顺序学习，并至少学完Dinic，因为Dinic不难，并且高效无源汇的有上下界的可行流名词解释无源汇：不区分起点和终点的闭合图有上...

有上下界的网络流网络流

2020-11-08

0 664

骑士精神__题解

这道题可以作为A*的入门题什么是A* 这是A* 的定义：A*搜索我的理解是，A*是一种剪枝方式，可以广泛运用于搜索中。A*的思想是定义一个估值函数，表示最理想的情况下还需要多少步才能达到想要的结果（真实情况所需的步数会大于等于估值函数的返回值），如果当前步数(定义为g(x))+估值函数(定义为h(...

A*

2020-11-07

0 653

魔法猪学院___题解

数据规模题目里没给出数据规模，我从别的oj网址找的：所有数据满足 2<=n<=5000 1<=m<=200000 1<=E<=1e7, 1<=ei<=E,所有的E和ei都为实数用到的知识最短路算法（spfa，dijkstra都可以）+可持久化堆 ...

最短路可持久化堆

2020-11-05

0 745

超级钢琴__题解

解题思路用到的知识点：st表+堆思维过程按照题目的要求，我们要求所有长度为[l,r]的子区间中最大的k个，首先，我们不可能遍历所有的子区间，因为那是O（n^2)的，我们考虑贪心先考虑k==1时：当k=1，我们只需要找最大的一个子区间，但是，这也要遍历所有子区间，于是考虑如何用较小的时间找出...

st表堆贪心

2020-11-04

0 640

Safe Travel__题解

题目大意给n个点m条无向边，每条边有边权，当点1到点i的最短路的最后一条边被封住时（只有最后一条边，其他边还可以用），求点1到点i的最短路，i取2，3，……，n（被封住边只影响此次的结果，不影响其他点的结果）,如果被封住后到达不了i，则输出-1，否则输出被封住边后的最短路解题思路思维过程我们...

最短路堆贪心并查集

2020-11-02

0 604

菜肴制作___题解

本题坑点题目没有给数据规模，我去别的oj网站上查了，是 100%的数据满足N,M<=100000,D<=3 解题思路 “看到x要先于y”这类字的时候，第一反应就是拓扑排序（不知道拓扑排序点这里），但是有一个问题，如果用拓扑排序，我们只能得到字典序最小的方案，不能满足题目要求的使得小...

拓扑排序堆贪心

2020-10-30

2 637