subtitle
开始阅读 Github
  我的梦想
不是每个人都应该像我这样去建造一座水晶大教堂，但是每个人都应该拥有自己的梦想，设计自己的梦想，追求自己的梦想，实现自己的梦想。梦想是生命的灵魂，是心灵的灯塔，是引导人走向成功的信仰。有了崇高的梦想，只要矢志不渝地追求，梦想就会成为现实，奋斗就会变成壮举，生命就会创造奇迹。——罗伯·舒乐
SPOJ2666-QTREE4 SPOJ2666-QTREE4
这题是可以点分治或LCT作的。。但这里讲边分治的做法。。 和点分治类似，边分治利用一条树上路径要吗经过一条边，要么不经过。而不经过的路径必然会在一次分治中变为经过的。 我们找到一条中心边，边左边和边右边分别建一个大根堆。左边的堆中存储边的左
2019-09-22 OI
边分治
SPOJ1825-FTOUR2 SPOJ1825-FTOUR2
我们知道，树上两个点的LCA要么是当前根节点，要么不是。。所以两个点间的最短路径要么经过当前根节点，要么在一棵当前根节点的子树中。。 考虑点分治，于是在原来同一子树中的两个点必然在一次分治中变为路径经过当前根节点的两个点。 点分治标准开头(
2019-09-22 OI
点分治
POJ1741-Tree POJ1741-Tree
我们知道，树上两个点的LCA要么是当前根节点，要么不是。。所以两个点间的最短路径要么经过当前根节点，要么在一棵当前根节点的子树中。。 考虑点分治，于是在原来同一子树中的两个点必然在一次分治中变为路径经过当前根节点的两个点。 处理路径经过当
2019-09-22 OI
点分治
COCI2014/2015#3-KAMIONI COCI2014/2015#3-KAMIONI
难得的没人做的水紫题。。 我的做法： 首先我们应该将每一辆车的转折点按照发生时间来排序。将所有不重复的查询都保存在拐点少的那个的名下。然后枚举每一个拐点就可以了。 这里是官方题解： 预处理每一个辆车的每一个转折点，以及方向，并且按照时间
2019-09-22 OI
贪心
GXOI/GZOI2019-lvxingzhe GXOI/GZOI2019-lvxingzhe
暴力：对于每个特殊点为起始点计算Dijkstra或spfa。。 然而这样有很多重复操作，很多路径会被重复走。 改善：考虑把特殊点分组，分组只计算两组间的最短路，组内不计算。显然，分为两组最优（如果分为多组的话其实和没有分组一样会走重复路径）
2019-09-22 OI
图论
GXOI/GZOI2019-旧词 GXOI/GZOI2019-旧词
相关链接（雾：[LNOI2014]LCA实际上这题就是加了一个幂。。原题爆破比赛 原题:当$k=1$时暴力：求LCA再求深度。。然后观察一下求LCA的方法。。最暴力的方法就是把根节点到节点$i$的路径上的点都打上标记，然后由节点$y$往上
2019-09-22 OI
树链剖分
CF55E-Very-Simple-Problem CF55E-Very-Simple-Problem
讲道理的话，题目中有simple一词的题目都不会简单。。 这道题如果我们直接计算包含的个数，本蒟蒻只能想到$O(n^3)$的解法，然后就咕咕了。。于是我们可以从反面考虑——数不包含该点的三角形。然后我们发现，如果一个三角形不包含该点，则这个
2019-09-22 OI
计算几何
CF75E-Ship's-Shortest-Path CF75E-Ship's-Shortest-Path
计算几何方法存点、算边来建图，然后跑一边最短路就行了。这题水到Floyd都能过。。。 我们先连接起始点(s)和终点(t)。如果st不与多边形相交或与多边形的一条边重合，则直接输出st的长度。否则，建一个由s、t、st与多边形的两个交点、多边
2019-09-22 OI
计算几何 最短路
CF46G-Emperor's-Problem CF46G-Emperor's-Problem
CodeForces的标签中说这题是计算几何题，，，而官方题解里说这是贪心题，，，然而我认为这就是一道暴力题。。 设有两个点$(x_1,y_1)$和$(x_2,y_2)$，则这条边的长$l=\sqrt{(x_1-x_2)^2+(y_1-y
2019-09-22 OI
贪心 计算几何 暴力
CF87E-Mogohu-Rea-Idol CF87E-Mogohu-Rea-Idol
题解是真的简单。。。就是对三个凸包求$Minkowski sum$，然后判断点是否在凸多边形内即可。。。 这题竟然还保证一个多边形内三点不共线。。。于是判断一个点是否在一个多边形边上变得更简单。。。一开始竟然没有看到这个条件，在那里进行检查
2019-09-22 OI
计算几何
CF82E-Corridor CF82E-Corridor
这屑题可能是计算几何题中的难得的良心题了。。。这题其实就是灯照进去每个窗的面积总和减去灯光相交、重叠部分的面积。 灯照进去每个窗的面积总和 我们很容易发现这题灯照进去每个窗的面积其实就是一个梯形的面积，这个梯形的高就是12345678
2019-09-22 OI
计算几何
CF78E-Evacuation CF78E-Evacuation
分析数据 我们可以将一个科学家可以在t分钟之内从(x0,y0)移动到(x1,y1)作为(x0,y0)在t时刻联通。 建图 现在我们有一个网格图了，我们可以再将其转化一下。我们构造有一个源点，一个汇点，中间有两个层，每层$n^2
2019-09-22 OI
网络流
1 / 2