niiish32x 's blog

原题链接https://leetcode.cn/problems/maximum-xor-after-operations/非常巧妙的一道题 123456789101112131415161718192021/** * 首先这个任意的非负x 不需要是在数组内出现的 就是一个任意数 * nums[i] and (nums[i] xor x) * 则 x 可以选一个 x 的二进制为 1 的位置 而 nums[i] 为0 x的二进制位置为0 nums[i]为0 的数 (即起到保留x所有的1的效果) * 则可将 nums[i] xor x 化简为 x * 从而得到 原式 = nums[i] and x = x * 最终答案求 MaxSum(nums[0..n]) xor x * 最终求的结果中1 越多则其值就越大 即在异或运算的过程中 尽可能多的 留1 * 即 只要 nums[0..n] 中 一位 有1 不管是奇数还是偶数 都可以 使用x进行调整从而将1 保留 (偶数 则 x 在这位取1 否则取0) * 从而演变为 nums[0..n] 的 或运算 (因为或运算只要有 ...

基本上任何情况都可以使用这种方法存N = 1e5 的时候就一定要这么存了N = 1e3 左右可以偷懒一下 使用邻接矩阵来存、 模板: 12345678910111213141516171819202122232425262728const int N = 1e5 + 10;int h[N]; //存储表头int e[N], ne[N], idx; //邻接表的基本参值//将b插入a后void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx, idx++;}//然后要注意初始化和遍历的问题/** 总的来说就是把 头节点 h[] 全部初始化为-1 用什么方法都行 C++的话 用memset会快一些 其他语言直接遍历一遍就行了*/memset(h,-1,sizeof h);/** 遍历*/// u 为初始遍历的点for(int i=h[u] ; i!=-1 ;i = ne[i]){ // 取出链表中存在的值 通常为节点值 int j = e[i] ...

组合数基础定理 基本公式 : C(n,r) = n! / r!(n-r)! (从n中选r个的方案) 123456789def C(n,m): """ 从n个球中 选取m个球的方案数 """ res = 1 for i in range(m): res = res * (n - i) res = res // (i + 1) return res 递推公式 : C(m,n) = C(m-1,n) + C(m-1,n-1)如果只在求答案的时候用的话 就用第一条就可以了但如果需要大量计算组合数 则需要对组合数进行预处理 因为求组合数事实上是在求阶乘 还是比较慢这个时候需要用到 递推公式 组合数预处理(递推法)这种情况N = 1000 左右 123456789// c[a][b] 表示从a个苹果中选b个的方案数for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) // 从i ...