CFR562

CFR562 div1

好题:CF1168D Anagram Paths

被睿智的第二题搞了半天,荣耀成为三题垫底……看到时限巨大还只有0/1,然后写了个bitset,结果常数过大(如果只有一两次应该还是能过的?)

CF1168A Increasing by Modulo

题意:给出长度为n的序列和模数m,问最少要操作多少次能使序列不递减,每次操作选择一个子序列模意义下加一

请先思考后再展开

明显可以二分,然后贪心就好了,code

CF1168B Good Triple

题意:给出一个长为$n \le 3e5$的01串,问有多少段区间满足里面$\exists l \le i-ln<i+ln \le r,str[i-ln]-str[i]=str[i+ln]$,时限4s

请先思考后再展开

过不去的bitset做法

上面做法的问题在于具体地求出了每个极小的三元组,但注意到回答询问并不需要这么具体,如果从右往左移动左端点并维护右端点的话,那么只需要考虑这个左端点能产生的贡献就行了,注意到如果能比现在右端点小不会很远,我能举出的比较大的例子是100110011,只需要移动4下,别人的code

题解的思路是,长度>9的区间都合法

CF1168C And Reachability

题意:给出n个数,有向边$(x \to y)存在当且仅当 a_x\&a_y>0且x<y$,q次询问能否从x走到y,$n,q \le 3e5$

请先思考后再展开

还以为题解是一个log,不知为啥没有写上标,我的做法是$O(nlog^2a_i)$

因为边都是向后的,考虑从后往前移动左端点并考虑其新贡献,注意到只需要知道可达性并不需要向所有点连边,考虑每个1的位并找后面有这个1的位置连即可

那么维护20个序列,每次往1的位置插数,维护$to(bit,pos,tobit)$表示从bit到tobit,在pos出发,能到达的编号最小的点,那么这个序列后面的点都能到达,这个的处理稍加思考发现$bit上1的to(bit,pos,tobit)=min_{bit2上1}\ to(bit2,这个序列原末尾,tobit)$

code

CF1168D Anagram Paths

题意:给出一棵n个点根为1的二叉树 ,每条树边上有有小写字母或?,q次修改树边上的字符后询问整棵树的$\sum_{c=’a’}^{‘z’} f(c)*ind(c),ind(‘a’)=1,ind(‘c’)=3,f(c)=在这棵树保持优秀的前提下,字符c最多能在优秀串上出现的次数$,优秀指根到所有叶子节点的串是同构(能通过重排字符相互表达)的,且称这个串为优秀串,如果无法优秀输出fou,$n,q \le 150000$

请先思考后再展开

一棵树优秀的充要条件是所有叶子的深度都为mxdep,且

$\forall x,\sum_{c=’a’}^{‘z’} g(x,c) \le mxdep-dep_x,其中g(x,c)表示从x出发在子树内的所有链,c出现的最大次数$

仔细观察这个限制,你发现我们根本不需要管?(开始以为要决策,但不知道为啥能贪,就mb了非常非常久),直接忽略掉不会对合法性有任何影响,所以做一个统计性的dp就好了,合法性可以用个cnt记录与上面限制冲突的点的个数

但是要怎么处理修改?DDP即可,这题非常有趣的一点在于深度相同这个条件还有利用空间

注意到一个孩子的时候是不需要判任何东西的,于是很自然的想法就是将父亲只有自己这一个孩子的点向上压缩,那这样的复杂度是多少呢?注意到我们更新的复杂度为深度,统计每个深度有多少点(合并起来的也算),那么一定满足每层都严格大于上一层,于是深度为根号

难得写了不少注释的code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/edd2542f.html
转载请注明出处,谢谢!