杂题选做(贰)"/>
十月杂题选做(贰)
用异或前缀和转化问题为,询问区间内两点异或为 k k k 的点对数,用桶记录出现次数,上莫队即可
在位上做高维前缀和,每次查询取反后的子集中是否存在数即可
考虑线性 d p dp dp ,按格转移状态,将行列、余数、选择个数全部压入状态中,四维数组转移即可,行与行的转移特判一下
考虑用 s g sg sg 函数处理,由于一定走最短路,所以考虑从终点开始跑 d i j k s t r a dijkstra dijkstra,用哈希表储存后续状态即可
线性 d p dp dp 练习题,正好卡空间卡不过去,要用滚动数组优化掉一维
带权并查集维护一下连通性和每个连通块的直径,合并的时候画个图处理一下就行了
根据奇怪的数据范围,发现 i − a [ i ] ∈ ( 1 , n ) i-a[i]\in(1,n) i−a[i]∈(1,n),尝试连边转化为图论问题,建出基环树,手完一下发现一个环的和必定是 0 0 0,拓扑排序找环即可
合法路径只有三种情况,全 0 0 0,全 1 1 1,先一段 0 0 0 再一段 1 1 1
考虑开两个并查集维护 0 0 0 和 1 1 1 的联通情况,前两种情况就是块内路径数
对于第三种情况,考虑枚举从 0 0 0 变 1 1 1 的中转点,搞一搞就好了
固定了起点为 1 1 1,终点为 n n n,建模跑有源上下界最小流即可
区间 d p dp dp 练习题,常见的 f / g f/g f/g 函数 d p dp dp,存当前状态的不同属性
更多推荐
十月杂题选做(贰)
发布评论