标签：xor min max 复杂度 枚举 3.15 异或 做题 pht

3.15pht做题笔记

C

考虑先枚举学生 \(j\) , 再枚举问题 \(x\) ，接着枚举该问题回答相同的同学 \(i\)

根据鸽巢原理，每个同学有效枚举的次数肯定不会超过 \(O(nk)\) , 所以总复杂度是 \(O(n^2k)\)

D

先想确定 \(k\) 之后怎么做，从 \(1\) 到 \(n\) 枚举 \(a_1\) 的位置，每次只会交换两组中的某一个元素，用一个数据结构维护最大最小值，此时复杂度为 \(O(nlogn)\) ，加上枚举 \(k\) 之后复杂度变成 \(O(200nlogn)\) ，无法通过。

但一波分析之后发现，\(k\) 其实只会取到 \(n\) 的素因子，证明：

\[\because S_{max}+3y\le4S_{max} 且 S_{min}+3x\ge 4S_{min}\\ \therefore \frac{S_{max}}{S_{min}}\le \frac{S_{max}+3y}{S_{min}+3x} \]

所以只用枚举素因子就好了，复杂度 \(O(7nlogn)\)

F

\(2\) 操作可以看作，把每个元素的下标 \(xor\) 上 \(2^k-1\)，\(3\) 操作可以看作，把每个元素下 \(xor\) 上 \(2^k\)

那求和的过程中考虑线段树的过程，向左边递归的区间，在异或之后，会跑到右边，右边的会跑到左边，改一下对应区间即可

G

考虑 \(xor-segment-tree\) ，交换操作相当于给每个下标异或上 \(2^k\)

我们可以用大概类似于线段树预处理的方法，预处理出异或上每一个数的答案

向上合并的时候，对于左半边，直接正常合并\((L,V,R)\)即可

而对于右半边，其实就相当于交换左右两边，之后再合并

H

还是考虑 \(xor-segment-tree\)，可以维护出线段树上每个节点的哈希值

这样就可以做到 \(O(logn)\) 的找出异或 \(x\) 和 \(y\) 的第一位不同的数，这样就可以比较大小

依次枚举即可

I

先考虑暴力 \(dp\) ，记 \(dp{l,r,0/1,x}\) 表示对于区间 \([l,r]\) ，现在是左/右，边上还剩下 \(x\) 个石头是否能赢

然后发现答案对于 \(x\) 是单调的，于是可以 \(dp_{l,r,0/1}\) 表示对于区间 \([l,r]\) ，左/右必胜，至少需要有多少个石子

那转移可以通过比较，左边赢右边和右边赢左边需要的步数，来转移

J

先转换一下题意，相当于枚举 \(i,j\) ，把 \(a_i\oplus a_j\)插入 \(i,j\) 两个位置的线性基，只要有一个能插入，就能使答案翻倍

这样就有一个 \(O(n^260)\) 的算法

我们发现插入 \(a_i\oplus a_j\) ，就相当于先插入 \(a_i\) 再判断 \(a_j\) 能否插入，于是我们可以先求出 \(a\) 的线性基，然后枚举 \(j\) ，接着只用枚举 \(a\) 线性基内的元素就可以整出全部的情况，这样的复杂度为 \(O(1800n)\)

标签：xor,min,max,复杂度,枚举,3.15,异或,做题,pht
From： https://www.cnblogs.com/hubingshan/p/18076365