今天是他的生日,让我们祝他生日快乐!
这套题是北大爷不知道从哪里找来的, 只知道出题人署名是 HR今天也是卑微爆0, 下次一定(?)认真打简单题&暴力
博客好久没更了, 主要是因为腐太多了? 还是要好好打一打题解的, 不然真的啥都没留下就退役了.
今天的代码估计要咕, 还是先打完博客梳理一下思路吧.
给一个n个点n条边的图, 边权表示所连的两点的权值和. 给出边权, 求点权.
显然这是一棵基环树, 图中的环是一个\(k\)元一次方程组, 可以求解. 环上的点权解出后, 对于每棵树上的点权直接求出.
有关x元一次方程组的求解, 可以用高斯消元, 但在这道题中有更加简单的解法: 考虑到每个方程组只有两个非\({0}\)系数且系数都为\({1}\), 可以用钦定一个点\(x\)作为起点, 从它的一条出边开始遍历环, 将环上的\(k\)条边都表示成含\(x\)的式子. 显然, 当我们回到点\(x\)时,这条边上的方程只有变量\(x\)且系数为\({2}\).
给出一个数组, 要求将其分为两个上升子序列, 求两个子序列的差最小.(无解输出\({-1}\))
考虑到每一个值都必须在某个上升子序列中, 那么对于每个逆序对, 都必在两个不同的上升子序列中. 所以对于每个逆序对, 我们连一条边, 然后跑二分图染色. 若染色不成功, 则数组不合法. 若染色成功, 图中会剩下x个连通块.
证明 每个连通块的值域没有交集: 若值域有交集, 前面一个区间的最大值和后面一个区间的最小值是一个逆序对, 必有连边.
对于每个连通块，会有一个固定的长度差. 得到每个连通块的差值后, 要使总差值最小, 只要DP每个数取\({+}\)或取\({-}\).
给出一个序列, 每个元素\(i\)包含两个值: 种类 \({b_i\in\{0,1\}}\) , 数值 \({c_i<2^{30}}\).
支持两个操作:
修改: 单点修改某个元素的数值.
查询: 相邻两个种类为的元素会被消去(不计入答案), 某一段消去后其左右两边视为相邻. 求一段区间中没被消去的元素的最大数值. (无剩余输出 )
暴力的日子就要用暴力的解法.很显然这题是一个区间查询问题, 那么我们用莫队; 这题有修改, 那么我们用带修莫队; 这题合并不可逆, 那么我们用回滚莫队. 另外还要维护一棵平衡树(multiset)支持插入删除求最大.
综上: 这题可以用带修回滚莫\({N\sqrt{N}\log_2{N}}\)的复杂度获得?分的好成绩. (正常都是因为没打出来而爆0吧?)
我们发现有顺序的\({01}\)抵消很像出入栈顺序, 我们把一段\({01}\)序列视作某棵树的dfs序的一部分, \({0}\)表示向下遍历, \({1}\)表示向上回溯.
注意: 若有"多余"的\({1}\)则新建一个点作为新的根, 将旧的根作为其儿子.
如此建树后, 每棵棵子树内的所有点都没有贡献, 区间查询问题变成了树上两点间的路径最大值查询, 我们用树链剖分即可.
注意: 由于边权有向的, 设\(x<y\)有: 链 \({x}\)->\({LCA(x,y)}\)应取向上边权, 链 \({y}\)->\({LCA(x,y)}\)应取向下边权. 我们开两棵线段树分别处理向上/向下边权即可.
显然对于某段区间, 充分合并后只剩余若干个\({1}\)和若干个\({0}\), 形如\({111100}\).
我们维护一个线段树, 对于每个区间维护\({1}\)的数量和\({0}\)的数量, 再用线段树分别对于\({1}\)和\({0}\)处理出区间最大值.
合并时两个区间中间同时消去\(min(0_{Left},1_{Right})\), 再将剩下区间的线段树合并.
原文：https://www.cnblogs.com/mxxr/p/13519612.html