钱逸凡

分类

题解(12)

/ 注册

全部文章（共5篇）

捉迷藏__题解

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

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

2020-11-21

5 796

超级钢琴__题解

解题思路用到的知识点：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

火锅盛宴___题解

解题思路这题一共三个询问，我们可以先从最简单的第三个询问开始分析第三个询问我们可以用线段树（树状数组）来维护所有已经熟的食物，每次询问的时间复杂度为O（logn）第一个询问由于我们在做第三问时建立一颗线段树（树状数组），所以我们这里可以直接用线段树来解决这一问：若整个区间的和为0，则没有食...

树状数组线段树二分堆

2020-10-29

0 577