before contest   本人是14年开始参加算法竞赛的老咸鱼，从noip一路打到noi再到大学转战acm，今年再打一年明年毕业退役了。 第二次在牛客出赛前训练，明年有空的话大概也会继续参与。   盲猜有大佬T2上线段树，T3上主席树，T4上树套树。 这样要么写不完，要不然就写的很累。 实际std：T2前缀和，T3树状数组，T4只用到了数组。 如果能够坑到至少一个满脑子数据结构的选手，那我这场就没白出（笑）   本场隔壁的普及组也是我负责的，感兴趣的话大家可以过去看看。   T1牛牛的方程式   签到题，主要考察对于扩展欧几里得公式的理解，但是不要求把扩欧写出来。   30pt   暴...

CDQ分治   预备知识   分治   与传统分治相同，CDQ分治的核心思想也是分而治之。     对于一个数组序列上的问题，分治的思想是总是考虑中的这一部分，而对于这一求解函数则使用递归表示。   式子中的加号并不一定是加法，只表示答案的合并。   这个说法有点过于抽象了。   举个例子，例如：分治求最大子段和。   区间字段和问题是指，给你一个大小为的数组，数组元素的值有正有负，然后请你求出数组中权值和最大的子数组。   在这个问题中表示：“区间中权值和最大的子数组之和”，而"+"并不是指把三者相加求和，而是对三者的答案取max。   仅表示左端点落在,右端点落在这些子...

这个EF题全部撞题就比较尴尬了，这个本人做题少还望大家理解。   如果有知道是哪些原题的，希望能在评论区给出，让大家的AC数都++。   反正就当是和大家闲聊，我说一下这套题目每个题的出题思路吧。   首先有这场比赛是因为之前参加“寒假算法训练营”出题工作的时候被删掉了几个难度过高的题目。然后我又加了几个水题凑成了这场练习赛。   A题就是随便拍脑瓜瞎出出的。   B题的由来是某天看到了一张初中数学试卷计算相似三角形，我就直接拿过来用了。   C题的思路是CF上这么一个题，说有个小船在2D平面的一个位置，它想去另一个位置，然后给你一个字符串“LRUD”表示风向，会循环吹一些风，然后你在控制船的...

A 牛牛的三角形  难度：签到题 大力for,或者一个更优的算法，先sort然后枚举相邻的三项判断是否构成三角形。  B 牛牛的鱼缸  难度：签到题 初中数学题，利用相似三角形求解。 注意分情况讨论以及h和l不要看反了（看反了也能过样例）。  C 牛牛的揠苗助长  难度：中等题 先考虑一个简单的版本，假设水稻不会生长，问最少操作几次使得所有的水稻高度相同？ 这个就是一个经典题了，首先结论是：最优策略一定是将所有水稻都向某一个水稻看齐，也就是至少有一颗水稻是不用动的。 原因如下图：  首先按照水稻的高度大小排序，假设你将所有水稻都调整到的值为x，且x不与任何一颗初始输入的水稻高度相同，那么要么你...

第一眼：bfs傻X题，然后发现它能跳。 然后嘴巴BB了一句，起点bfs，终点bfs，单调栈+单调栈合并的傻X题。   （...几小时后...）  MD这个题怎么这么麻烦。  好吧，这个题确实是没什么可以说的地方，没思路的话可能是不知道“单调队列处理固定划窗极值”这个套路。  单调队列处理固定划窗极值  它是这么个套路啊，说现在有一个长度大小为n的数组，数组中有一些整数，请你求出所有长度大小为k的子区间的极值。 还是给个例子比较好说明，假设n=9,k=3，a[]={5,6,7,8,9,4,1,1,1} 跟着划窗取子区间，取到的第一个子区间是{5,6,7}这个子区间，该子区间的最大值为7。 那么想...

本题解需要掌握dsu on tree和长链剖的相关知识。 具体可以见我的博客 dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9   一开始就读了个假题，读成了。“统计每一层的节点数目，然后输出和为奇数的层共有几层”这个题意，然后样例都过不去一脸懵逼。     题意：给你一棵树，重复做以下动作直到树上所有点的权值都为0 1、对于所有权值大于1的节点，权...

答案等于，Bsize表示连通块尺寸，这个并不是难点，难点在于连通块大小怎么求。  这个题，第一眼：水题啊，直接并查集或者dfs瞎搞搞。 然后惨遭数据范围毒打。（毒瘤） 那...首先dfs先pass，这个怎么剪枝好像也不行，离散化压缩再dfs感觉也写不太动。 但是并查集是个好思路。 首先根据数据范围，只要地图足够大，障碍物的总数目有有限，障碍物就放的相当稀疏，那我可以提前把一些比较大的连通块并起来。  idea1   如图，'.'表示普通的格子，'X'表示障碍物。 我可以按照行进行扫描，然后把所有连在一起的.合并成一个长长的“面条”，这样子再把行间相邻的“面条”给合并起来不就好了？   （......

第一眼：bfs傻X题，然后发现它能跳。 然后嘴巴BB了一句，起点bfs，终点bfs，单调栈+单调栈合并的傻X题。   （...几小时后...）  MD这个题怎么这么麻烦。  好吧，这个题确实是没什么可以说的地方，没思路的话可能是不知道“单调队列处理固定划窗极值”这个套路。  单调队列处理固定划窗极值  它是这么个套路啊，说现在有一个长度大小为n的数组，数组中有一些整数，请你求出所有长度大小为k的子区间的极值。 还是给个例子比较好说明，假设n=9,k=3，a[]={5,6,7,8,9,4,1,1,1} 跟着划窗取子区间，取到的第一个子区间是{5,6,7}这个子区间，该子区间的最大值为7。 那么想...

本题解需要掌握dsu on tree和长链剖的相关知识。 具体可以见我的博客 dsu on tree：https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9   一开始就读了个假题，读成了。“统计每一层的节点数目，然后输出和为奇数的层共有几层”这个题意，然后样例都过不去一脸懵逼。     题意：给你一棵树，重复做以下动作直到树上所有点的权值都为0 1、对于所有权值大于1的节点，权值减少1。当权值为1...

长链剖分可以视作是dsu on tree算法的一个特例，在学习之前，需要掌握树链剖分以及dsu on tree。   dsu on tree:https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98   dsu on tree用于解决：   子树类的静态查询类问题。   基础复杂度为。   长链剖用于解决：   子树类与深度相关可合并的静态查询类问题。   基础复杂度为。   长链剖应用的场景必须是与子树深度相关的，从这点上来讲他只是dsu on tree的特例。   当然，它的复杂度是比dsu on tree要优秀的，不然不就完...

dsu的意思是并查集，但是dsu on tree这个算法和并查集的关系也就剩一个启发式合并了。   学习这个算法的切入点还真不在启发式合并，关于启发式合并的问题实际上是最后再考虑它为什么叫启发式合并。   我们选什么作为切入点呢，选莫队算法，如果你不懂莫队也没关系，这里只是说这两个算法在应用的场景上面有共通点，只不过一个应用于子树，一个应用于数组区间。   莫队      我们从最简单的区间问题“子区间的静态求和问题”开始讨论好了。   假定现在有一个数组a，数组里面有若干个元素，然后你已知这段区间的区间和，假设区间与区间有大面积重合，重合率达到90%。问你如何在已知区间和的情况下计算的区间和...

写在题解前的话   按照惯例，先背锅。   这次比赛没有Hello World或者A+b problem这样的“签到题”。   也没有能直接贴过来的那种，能够AC的话都不错。   爆0的话也不用担心，后面的场都比我这场简单（大概）。   然后锅嘛...   B题spj写锅了，可以判题但是不能统计罚时（WA了算内部错误没有罚时） 题目描述上面有点小锅。   这场比赛我每个题都写了很多不同的程序，会公开给大家看一下（选手可能只会被题目恶心一次，但是出题人可能要被自己出的题恶心死...做个10遍8遍的，还得出数据）。   A、牛牛的DRB迷宫I   这个题是所有题里面最简单的题，是经典的走格子DP（...

树状数组   树状数组常用于维护前缀信息，如前缀和、前缀乘积等等。   最常见的如给你一个长度为n的数组，单点修改，查询区间的和。   首先是想一下为什么不能用前缀和数组强行搞   先看一下前缀和      黄色和蓝色部分合起来表示前缀和覆盖的区间 黄色表示前缀和信息储存的位置      如果要修改a[5]还好…只有s[5]会受到影响，万一要修改a[1]或者a[2]的话就要修改s[1],s[2],s[3],s[4],s[5]，也就是全都要改。   这样的话时间复杂度就上天了。   用前缀和处理带修改的区间求和问题   操作的时间复杂度：   1、对一段区间求和O(1)  2、单点修改O(n) ...

高维前缀和(SOSDP)  高维前缀和，又叫SOSDP，Sum over Subsets dynamic programming，它一般是用来解决子集类的求和问题（虽然也可以解决高维空间的求和问题，但是时空往往不允许）。  高维度下求前缀和时，时间复杂度的瓶颈   先看一下前缀和的式子   一维：   二维：   三维：   ....   我们发现这步容斥操作在高纬度下不能被视为O(1)，它与维度k成幂函数的关系。   高维前缀和的时间复杂度为O(|高维空间容量|*)，在高维空间容量不大，但是维度数很高的时候，瓶颈在于维度数k。   想办法进行优化。   另一种求前缀和的方式   for(in...