什么是GUIDE GUIDE(GAIT Universal IDE)是由北航GAIT研究组开发的、专门为NOI选手设计的轻型集成开发环境。GUIDE具有跨平台、操作简单、支持C/C++/Pascal三种语言和单文件编译调试等优点。经过近一年的试用和修改之后，GUIDE 1.0.1版目前正式发布。 ——www.noi.cn 换句话来说，GUIDE是一个NOI官方指定的，在NOI Linux系统上预装的一款pascal/c/c++ IDE(集成开发环境)。 GUIDE有什么优点 我们GUIDE有一点好，就是出了什么bu…
题面 [Luogu P4768] [NOI2018]归程 Solution 这题可能要用到Kruskal重构树的相关知识，如果有需求的同学可以看这里 首先，根据我们之前在运输计划那道题的经验，我们会发现我们开车能经过的边一定在以海拔为关键字的最大生成树上。 根据Kruskal重构树的性质：Kruskal重构树是一个堆，我们可以考虑这样做： 我们先把Kruskal重构树按每条路的海拔从大到小建出来，那么从某个点出发能开车到达的点一定是这个点的某个祖先的子树内的所有的点，这个很好理解，因为Kruskal重构树是一个堆，…
题面： 传送门：洛谷 Solution 看到这题，我们肯定会有一个大胆想法。 那就是直接用堆模拟这个过程。 对于q，我们只需要在堆中多维护一个T,记录每个点插入的时间，在新的元素插入时直接计算所比较的点的当前长度就可以完成插入了。 时间复杂度$O(M*log(M))$ 这样的做法只能获得65-70分，因为后面的数据非常大。 所以说，我们要另寻他路。 首先，我们经过看题解手玩可以发现一个很显然但是很重要的结论： 在$q=0$的时候，一条线段所分裂出来的两条线段肯定要比它更小的线段分裂出来的对应的两条线段更大。 证明十…
题面 传送门：洛谷 Solution 如果题目只要求求出第一问，那这题显然就是大水题。 但是加上第二问的话.......那这题就成为大（du）火（liu）题了。 对于第一问：求一整个区间的最大线段总数，我们可以很轻松的切掉。 怎么处理第二问呢？ 我们可以考虑这样做： 对于一条线段，如果它属于答案的一部分，那么它一定会有以下性质： 区间③的最大线段数 = 区间①的最大线段数 + 区间②的最大线段数 + 1（当前线段） （区间最大线段数指用传统贪心方法求出的一段区间的可能的最多的线段的数量） 那怎么求一段区间的最大线段…
题面 传送门：洛谷 Solution 这是一道很有意思的在背包里面做容斥的题目。 首先，我们可以很轻松地想到暴力做背包的做法。 就是对于每一次询问，我们都做一次背包。 复杂度$O(totslog(di))$ (使用二进制背包优化) 显然会T得起飞。 接下来，我们可以换一种角度来思考这个问题。 首先，我们可以假设没有每个物品的数量的限制，那么这样就会变成一个很简单的完全背包问题。 至于完全背包怎么写，我们在这里就不做过多讨论，如有需要，看看代码就能理解了。 完全背包做完后，我们可以得到一个$f[i]$表示填满i的背包…
最近评论
发布于 2 个月前（03月16日）
发布于 5 个月前（11月30日）
发布于 5 个月前（11月30日）
发布于 6 个月前（11月04日）
发布于 1 年前（05月01日）