十月杂题选做（贰）

杂题选做（贰）"/>

十月杂题选做（贰）

用异或前缀和转化问题为，询问区间内两点异或为 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，存当前状态的不同属性