换教室 Description 对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中,有2n节课程安排在n个时间段上。在第i(1≤i≤n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室ci上课,而另一节课程在教室di进行。在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教 2018-10-20 #OI #NOIP原题 #DP
货车运输 A国有n座城市,编号从 1到n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。 对于这道题,容易想到的是一个朴素的算法。即用跑最短路的思路来跑出最小值最大的一条路,只需对spfa进行稍许修改即可。 12if(min(d[x],son.w)>d[son.v]) d[s 2018-10-20 #OI #图论 #kruskal #LCA
背包问题 背包问题 对背包问题状态转移方程的一个证明。 12345for (int i=1;i<=n;i++){ for (int j=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+1); } } 使用数学归纳法。 首先考虑只有一个物品的情况。这种情况很简单,选一定比不选好。 其次,假设我们已经得到 2018-10-20 #OI #DP #背包问题
棋盘DP T1:最大正方形 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。 先考虑暴力,枚举起点和边长,可以O(n^5)的解决这个问题。 稍作优化(这个优化第一次看见好像还是在初赛) 采用f[i][j]表示第i行前j个元素的前缀和。这样计算一个矩阵的元素和的复杂度可以降至O(n)。总复杂度可以降至O(n^4)。 再稍微优化优化 直接计算二维矩阵前缀和,预处理的复杂度为O(n2 2018-10-20 #OI #DP
LCA LCA即最近公共祖先,这里只介绍倍增这一种求法。复杂度为O((n+q)logn)。 算法基于倍增的思想。即当前节点的第2n祖先等于当前节点的2(n-1)祖先的2(n-1)祖先。用这个思想可以在logn复杂度内处理一个节点的所有2i祖先。且可以证明的是,处理深度更大的节点的时候,深度小的节点的信息已经处理完毕。 在预处理倍增f数组的时候,还可以做: 求dfs序。 求深度。 丢到根距离,用于进一步求 2018-10-19 #OI #图论 #树
kruskal重构树 kruskal重构树的性质 kruskal是在kruskal进行的过程中,把最小生成树的边权变为点权的算法。这样,重构出的树的结点数为 n + (n-1) = 2n -1.个,并且这棵树具有以下性质: 这是一个二叉堆。 原树两点间边权的最大(最小)值为两点LCA的权值。 重构树中原树的节点全部为叶子节点,其余节点都是新建的点。 kruskal重构树的构造 与kruskal类似。先对边进行排序, 2018-10-19 #OI #图论 #树
树上差分 树上差分有两种形式,关于点的差分和边的差分。 先来考虑边的差分: 边的差分是用于解决边的覆盖问题的一种很优雅的方式。 具体方式为读入一条路径。对路径的起点,终点+1,对起点和终点的LCA-2. 统计一条边被覆盖的次数时只需统计这条边连的点中深度较大的那个点和它的子树的差分和即可。 另一种是关于点的差分: 点的差分可以用于解决路径覆盖点的次数的问题。 具体方式为读入一条路径,将起点和终点+1,将l 2018-10-18 #OI #图论 #树
跳石头 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 NN 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。 为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 MM 块岩石(不能移走起点 2018-10-18 #OI #整数二分
运输计划 公元20442044 年,人类进入了宇宙纪元。 L 国有 nn 个星球,还有 n-1n−1 条双向航道,每条航道建立在两个星球之间,这 n-1n−1 条航道连通了 LL 国的所有星球。 小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 u_iui 号星球沿最快的宇航路径飞行到 v_ivi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 jj,任意 2018-10-18 #OI #图论 #树 #NOIP原题 #LCA #整数二分 #树上差分
exgcd exgcd&逆元 简介 用于求方程形如 ax + by = gcd(a,b) 的一个特解(亦可用此解推出所有解)。 算法 递归求解,其实本质是用方程 bx + (a mod b)y = gcd(b,a mod b) 的解递推出方程 ay0 + bx0 = gcd(a,b) 的解。具体递推关系为 x0 = y, y0 = x - a/b*y 递归的边界条件为当a mod b递归至0,则必有g 2018-10-18 #OI #数论