解法
这道题其实就是考察 KMP 算法中 Next 数组的使用。题意转换过来大致就是:
给定两个 01 串,构造一个长度跟第一个串相同且 1 的个数相同的串,且保证第二个串的出现次数最多,出现可以重叠。
这道题其实就是考察 KMP 算法中 Next 数组的使用。题意转换过来大致就是:
给定两个 01 串,构造一个长度跟第一个串相同且 1 的个数相同的串,且保证第二个串的出现次数最多,出现可以重叠。
这道题可以算是 CDQ 分治的一道基础题了。
首先,CDQ 分治的主要方式就是通过分治的方式将一段区间内操作和询问部分固定,变成静态子问题来解决(前提是每一个询问的答案都受过去的操作影响,且这些操作对问题的影响是独立的,也就是说回答询问为过去独立操作的叠加,答案不受顺序的影响)。
在本题中,我们先把初始点变成加点操作,这样就可以统一化了。每个询问的计算式:
这道题很有意思啊。如果暴力枚举,答案式子:
\[ans = \sum_{x}^n \sum_{y}^m {up_{x,y} \choose k} {left_{x,y} \choose k} {right_{x,y} \choose k} {down_{x,y} \choose k}\]
其中\(up, left, right, down\)代表上下左右的常青树棵树。如何降低复杂度?
首先,我们可以考虑进行离散化:上下左右只要有为\(0\)的情况是不可能对答案有贡献的。然后,发现空隙中上下的部分:
“傻逼题。”——XG_Zepto
这道题还是挺好做的,先把所有前缀异或和放入 Trie 树中,然后\(O(n)\)枚举右端点\(r\),在 Trie 树中查找与前缀异或和\([1-r]\)异或的最大值并放入堆中(放入堆时标记好排名为\(1\))。之后在堆中取出,并不停的放入排名逐渐变大的异或和查询值,收集前\(k\)个即可。
给定一个平面\((n,m)\),处理如下操作:
给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\),处理\(q\)个询问:在数组的字段\([l,r]\)内是否存在排列的环形偏移。
考虑正向扫描,处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置,并同时更新自己所在的位置供下一次循环进行使用: