感觉很妙,所以来水题解了~ 问给你一个升序序列,问是不是可以还原一个bstbstbst,使得相邻的两个节点gcdgcdgcd不为111.n<=700n<=700n<=700. 因为是颗二叉树,很容易想到区间dpdpdp,然后假设区间[l,k][l,k][l,k]满足了,这个区间的父亲节点要么是l−1l-1l−1,要么是k+1k+1k+1.可以假设它的父亲节点是l−2/k+2l-2/k+2l−2/k+2,可以发现无法构造这颗树.这就是一个很好的性质,这样我们就可以进行区间dpdpdp了. 一个显然的结论假如区间[l,k][l,k][l,k]和[k+1,r][k+1,r][k+1...

一些我不会做的题,加上没有正常题解...就会变得very hard. 其实并没有多难. 这个先容斥一下,然后lca分三种情况讨论就好了. 贴个智商代码: using namespace std; typedef long long ll; typedef unsigned long long ull; const int mod=1e9+7; const int N=2e5+5; const int M=21; int p[N],sz[N]; ll ans[N]; bool vis[N];//是不是在这个链上啊. vector<int>G[N]; void dfs(int ...

陷入思维误区的一个题目. 首先肯定知道的是一定是最高位全为111,而且长度为偶数是最优,且前面的位异或和为000. 那么我在解这个题的时候,因为使用了局部最优,从而忽视了某些情况,导致一直wawawa而且无法理解别人的代码. 其实这个不能使用dpdpdp.而应该使用贪心. 怎么贪,记录当前位的1的数量,和异或前缀和,显然的是我们必须使得异或前缀和都为0才能使得我们的条件成立,那么我们就记录每个异或值出现的位子就好了,判断是不是要更新,无非就是判断是不是这段是不是出现了0,出现了0就随着更新就好了,然后判断下这位1的数量是不是满足全为1且是偶数. code： #include <bits/...

这题也好难诶!!!好叭可能只是对于我.因为dp方程不是我写的,网上也没注释.. 首先满足子区间异或和相等且当形式为 A 0 A 0 A 0..这种形式的异或前缀和才行. so?这题就做完了,我们进行dp即可. 令dp为现在出现位子i值为A的区间的种数,很明显,当前出现假如为A,那么它可以和前面的一起转移,就是把j+1~i这段的异或值是0,跟j一起合并成一个区间进行转移.因为上一个区间已经转移了所有区间,所以其实就是在上一个区间转移即可. 还有就是不利用前面的段进行转移,而是利用i-1到i这个区间的0进行转移,可以看成是拆分成[j+1,0][j+1,0][j+1,0],[0+1,i][0+1,i...

好难的题目啊！ 写个博客记录一下. 首先显然满足要求的一定是相邻行取反或者列取反的矩阵.画下图可推出来. 然后,分别考虑行列肯定是2^n,和2^m,可以看成确定一排后面的都确定了,也可以看成每一排都有两种选法. 然后考虑修改...和去重 重复即是两种情况都满足的,其实只有两种取法,即是黑白染色,确定一个点就可以确定是哪种选法.然后去判断修改是不是影响到我的去重了,假如影响到了我就不减. 然后就做完了...但是好绕啊)))网上的题解我也理解了很久,我自己的题解肯定自己理解的比较快叭~~~~~ 好难喔~ #include <bits/stdc++.h> using namespace ...

本来一开始就写完了... 可惜读错题了,我读的题更复杂一点点... 所以越写到后面脑子越晕... 直接导致后面调傻了,在原代码上. 我读的题里面他是每一轮都可以出它集合里面的东西.而不是固定一种. 两者处理方法是一样的,但是前者更为复杂? 好了... 考虑第iii个人怎么才能赢,那么就是第iii个人赢了,前i−2i-2i−2轮的胜利者,然后赢了后面所有人对吧? 然后赢了后面所有人怎么考虑,那么可以用个后缀和,统计后面每种状态的个数,显然只有7种状态,然后把他们按照乘法原理就可以算出来了. 假设我后面状态为111(7)的有4种,我当前为100(4),那么概率不就是suf4,7suf_{4,7}s...

因为是一个有向无环图,一个生物灭绝的条件是它的食物都灭绝. 那么我们考虑按topotopotopo序重构这张图,因为一定是一个森林/树,我们考虑增加一个超级源点uuu.然后且当它的祖先节点灭绝它就会灭绝,考虑把它**到它所有食物的lcalcalca下面,然后灭绝它的毁灭值就是子树大小−1子树大小-1子树大小−1啦. 树的lcalcalca的倍增和rmqrmqrmq的倍增是有一定的区别的,rmqrmqrmq包含自己,而树不包含自己节点. code:code:code: #include <bits/stdc++.h> using namespace std; typedef long...

前言 以前学的算法等于白学(点分治除外)>>,今天ac500后将系统学习以及记录主席树. 主席树 它是一个类似前缀的数据结构,通过每次在原有的树上更新需要更新的区间信息,从而达到区间查询的目的,可以把它看成一个差分效果?它一般把权值当成下标可以查询区间第k大,以及区间不同种类数等功能.它还可以区间修改~~~

关于带权中位数自己的理解. 不妨把权值全部变成数,那么就转化成了中位数问题,显然只有包含中位数才能达到最优,所以可以进行二分,考虑假如前面的和不超过后面的,显然这个值不含有中位数,一定不是最优解,那么就是大于等于它的第一个位子是最优解.

感觉自己在降智... 一开始写c想二分,二分半天也没二分出什么...最后是枚举. 想e的时候一直想偏序,我不知道正解是啥,最后写完我的想法刚好没时间了..当然还没调qwq 介绍下自己的想法,将方格的横坐标看成是时间,然后在维护时间的一个优先队列,假如现在的时间要大于优先队列对头的时间,那么对头就要去除,然后对于横坐标进行差分,只要从1开始到i的前缀和值是正数说明这个点被遍历过.细节就是一种颜色大于1的才有贡献,贡献是横纵坐标取min...肯定没这么复杂.待会看下正解. code: #include <bits/stdc++.h> using namespace std; typed...

首先考虑贡献如何算? 比如1 2 3 4 5 2 3 4,很显然的一个算就是把2 3 4去掉,然后只求1 2 3 4 5的贡献. 考虑i以及相邻的一段的贡献,很显然i的贡献就是相邻一段的长度,比如说1 2 3,1的贡献是1,2的贡献是2,3的贡献是3. 知道贡献怎么算了,下面就分为几步解决这个问题. 第一步:离线 将查询离线,在线不是很好解决这个问题,离线的好处就是我能更新到哪就询问到哪.类似于存版本之类的.具体就是对于每个rrr查询[l,r][l,r][l,r]的贡献. 第二步:算贡献 如何算贡献,考虑把现在的下标放到线段树上做下标,那么假如说我连续的一段长度为444,现在的位子在pospo...

首先讲ai排序(从小到大)后,后缀一定是不减的. 证明:在没有割草之前这个一定是成立的,假设我有割草,割的高度是b,那么前面的一定小于b,后面=b,然后后面还是比前面长的更快. 由此就产生了一个线段树二分的做法. 上一次被割草的时间day+1,区间内草的增加速度之和spd,区间内左端点的速度nmspd,区间之和sum,区间的两个延迟标记b和d,来延迟更新区间信息.最后还要维护一下左端点的信息nm方便二分查询后缀和. 然后就是做线段树的区间修改和区间查询的功能了. code: #include <bits/stdc++.h> using namespace std; typedef...

单调栈一般就是栈内的更新细节...无数次折磨了 首先发现这个图是个dag(有向无环图),假如对值比它大的最近的左右两个点连边的话,然后对dag做个简单的线性dp就好了. 细节就是一段相同的时候,因为数据保证递增,在前面的时候肯定选取最前面的最优,在后面的时候肯定选最后面最优,然后一定要在栈内更新,比如3 3 2 1 3 3你在栈外更新肯定是错的,也可能是我调k脑抽了. code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; const int mod=1...

大部分代码贪心解法是错误的,原题是CF1442D,可以在cf上测试一下. 首先不考虑贪心,这是个分组背包O(N2K)O(N^2K)O(N2K),考虑贪心暴力仍然是O(N2K)O(N^2K)O(N2K). 贪心题解讲的很清楚了,那么我们如何能够做到更优的时间复杂度解决这个问题呢. 可以是分治,在每次递归到某个叶子节点的时候提前把n-1个序列全取了就ok啦.这就看你如何写分治了. 定义solve(l,r)为更新了[1,l-1],[r+1,n]的dp值,现在解决[l,r]区段. code: #include <bits/stdc++.h> using namespace std; typ...