mhy写此题写了良久啊然后T啊T,T啊T.然后我去翻了一下seter的博客.结合他的东西yy出一种比较优越的做法. 如果我是出数据的,我会出两种数据,菊花图和链. 如果是菊花图,直接朴素ovoovo如果是链,可以以每个叶子节点为根建一次可持久化线段树. 如果是链上长出了一团菊花… how to 结合? 不停地删叶子.如果删到某层时叶子足够少了,那就建可持久化线段树去. 对于询问,有若干种情况. 标记每个根里离得很近的点. 如果两个中有一个被标记过,那么直接以这个根求另一个的答案,然后朴素查找近的这个点到根的答案. 如果两个点都没有被删 ,那一定有至少一个根可以使得这条链的两个端点有祖先关系.这样的话直接用可持久化线段树求解. 好像完了?然后wa了ovoovo 还有一种情况是某个点被删了,但是删之后它是接在树枝上的! 于是它离根很远,还不一定有能搞出祖先关系的解. 于是先爬行到没被删的地方,看两个端点是否在同一棵被删的叶子树上. 如果是就朴素了. 如果不是的话,先求没被删的这一段,再朴素被删的一段. 终于完辣. 从来没写过这种代码.感觉自己萌萌哒.

这题我的做法不太一样.所以mark一下.首先我把题里的n和m看反了,所以下面的m和n都与原题里的m和n相反. 首先考虑一行的方案.在不考虑顺序(即只考虑题中要求􏰍􏱫􏴈􏴉􏰕􏱫􏰍􏱫􏴈􏴉􏰕􏱫􏲙每个颜色个数这个条件一定时)的方案数. n是50,刚好可以正整数拆分,把n拆成不超过k个正整数时,可行的方案数为n! / c1! / c2! / … / s1! / s2! / …这个样子.其中cx表示正整数拆分中的第x个数(后面补0可以不管),s1表示第一种相同的cx的个数. 其实就是说怎么把k个颜色分配到我拆分出的这些整数里. 然后对于一种这样的方案的排列数也比较好求. 然后就是求m行的情况.我的思考方法是先按上面固定顺序,再乘m!.其实这样有问题虽然我没出事.也有可以补救的方法. 上面拆出来的一种拆分,设它有t个不同的颜色分配方案,一种方案有c种排列.这里用一个类似于背包的转移,f[i] = f[j] + 一坨东西. 这坨东西就是把(i - j)个方案按顺序排列的答案.(都叫方案啊好晕ovo)当然这里排列的话会用到判断t是否大于等于(i - j),但是t被模过ovoovo.我偷了个懒假设t如果被模过不会正好小到影响统计.果然也没有. 其实也可以不去除,而是乘组合数吧.不过写起来好麻烦. 咦写了这么多了.然而感觉还是没说清楚啊.ovoovo结合代码理解吧.

mhy开了道找规律oovovo 打表找规律良久.最后还是没有O(1)的规律.倒是发现有点像分形,有个log级别的递推式. 怎么来的啊好神奇啊ovoovo

最近都在做梦的感觉啊.这道题倒是mhy的博客一语点醒梦中人. 只会加正数,所以每个数只有至多一次会从负变非负. 链剖是肯定的.然后记录一下当前最大的负数是谁.如果大于等于0就改掉.所以还是O(n*log2n). 所以我还是太弱了.于是读入优化大法抢了一个rank1.

比较郁闷的题ovo拍了老久.最后还是找Po神要来了数据. 首先这个矩阵的基就是一个拟阵,所以可以贪心. 然后发现就是要O(n^2)判断是否线性无关. 其他人的做法是强行顺序.我觉得没辣么麻烦啊.先把原来消出来的东西备份一下.如果发现不行再备份回来就好了啊ovoovo 那么直接高消会有非常严重的精度问题(似乎是). 于是我想直接用整数搞.然后发现会有变成负数的问题和越界的问题,强行re+wa.非常不开心. 于是直接取模yeah.然后由于用了辗转相除之类的东西所以常数巨大.而且bzoj上开了O2比本机没开O2竟然慢了6倍.ovoovo

bc fst爽翻.然后这题差二十分钟没调出来不然我就是rank1.还是应该直接敲而不是去和队友商量. 静态做的话直接按位树分就好了.然后资瓷修改的时候也是一样.只是把之前求的信息在树分后的dfs序上用线段树记下来.也就是要随时知道某个分治层里的某个子树上有多少个0或者1. 然后就是讨论某个修改对当前答案的贡献.要注意分治根的值,以及有贡献的是哪些位置.中间打错了外层的dfs序范围,导致调试了很久.明明想清楚了但是打错了,不应该的. 只有完了之后交了然后怒虐标程好开心啊.

还比较有意思的一题. 考虑如果Alice选了某一个位置,那么Bob的策略一定是选使得Alice的和最小的一段.也就是对于所有位置,求包含它的所有区间中和最小的一个,再求个max. 这个东西先要展开一倍,然后可以比较方便地用单调队列搞定.

其实是一道没多大意思思的码农题TT然而这是我的第800题所以要mark一下. gcd序列可以用插分序列+第一个数来支持区间加.二维那就二维差分喽. 然后发现第一个数似乎没有办法维护啊.不能做了?! 询问的方式比较奇怪,有一个中心.那就建4个方向吧.这样似乎可做了yeah. 所以我还是太naive了啊. 是时候屯一波题了.

立杰的dp套dp.之前在hwadee培训的时候讲过的题啊. 考虑求lcs时候的f数组的一列,发现相邻两个数要么差1要么不差.于是15就是拿来状压这个东西的. 然后很愉快地写了一个然后很愉快地tle了.妈妈,剧本里没这一节啊. 仔细思考了一下发现每次在计数dp转移的时候去找lcs dp非常慢.而且只要给定状态和转移,目标是确定的.跑1000次浪费了.于是改成预处理转移.就好了.

业界毒瘤ioi开的坑.然后被强行看了一下于教授的代码.然后觉得也不太难嘛. 看了一下条件.只和同行或者同列有关?那就拿map套动态建树的线段树好了辣. 然后距离是欧式距离?那就把完全平方式展开,发现只需要在线段树里记录一下个数,和,平方和,搞定了辣! 然后alloc的时候–写成了++,查错良久,囧.