搜索结果
查询Tags标签： lowbit，共有 23条记录-
树状数组学习笔记
一：树状数组定义 望文生义,树状数组就是用树形结构来模拟数组的一种数据结构。 二：图解（纯手绘，难看勿喷） 编辑 C表示从1-k的和， C[1]=a[1] C[2]=C[1]+a[2] C[3]=a[3] C[4]=C[2]+C[3]+a[4] C[5]=a[5] C[6]=C[5]+a[6] C[7]=a[7] C[8]=C[4]+C[6]+C[7]+a[8] C[9]=a…
2022/9/2 23:25:10 人评论 次浏览 -
算法学习之路 二进制操作
/* 有关二进制的基本操作分为两类： 1：二进制中 1 的个数； 2：二进制中的lowbit操作；（即二进制数中最后一位 1 的位置） */ //二进制输出：（以10为例）int n;cin>>n;for(int k = 3;k >= 0; k--)cout<<(n >> k & 1);return 0; // k 的边界值…
2022/7/31 1:31:22 人评论 次浏览 -
位运算
位运算常用的几种位运算n的二进制表示中第k位数字是什么 n >> k & 1先讲第k位移到最后一位n >> k 看最后一位是几 & 1lowbit 运算：返回x在二进制表示中的最后一位1 x & -x 在c++中 x & -x = x & (~x + 1) 如x的二进制表示是 1010111000 …
2022/7/7 23:22:07 人评论 次浏览 -
数据结构和算法 - 树状数组
树状数组 1. 问题序号 题目—— ——————————————————————————————————————————————————————307. 区域和检索 - 数组可修改493. 翻转对HDU P1166 敌兵布阵给定一个数组\(A\)，长度为\(n\)，数组的下标范围是\([0,n-1…
2022/4/5 1:19:28 人评论 次浏览 -
寒假集训笔记
注意事项(并不完整): (1)i式筛求素数(用bool型数组,大的数int会爆MLE) (2)for(int j = i;j <= n/i;j++) 能除的就不要乘(i*j可能会爆int) (3)快速幂别忘了long long一、memset (40 -> 6亿) 1.int 0x7f一个很大的数(略小于0x7fffffff) 0…
2022/1/26 23:09:59 人评论 次浏览 -
801二进制中1的个数
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。 输入格式 第一行包含整数 n。 第二行包含 n 个整数，表示整个数列。 输出格式 共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。 数据范围 1≤n≤100000,…
2022/1/25 23:35:17 人评论 次浏览 -
面试题 08.12. 八皇后
设计一种算法，打印 N 皇后在 N N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。 注意：本题相对原题做了扩展 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/pro…
2022/1/19 6:09:24 人评论 次浏览 -
面试题 08.12. 八皇后
设计一种算法，打印 N 皇后在 N N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。 注意：本题相对原题做了扩展 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/pro…
2022/1/19 6:09:24 人评论 次浏览 -
【数据结构】零基础树状数组笔记
参考和引用 树状数组学习笔记 树状数组 数据结构详解与模板(可能是最详细的了) 树状数组（简单介绍） 树状数组小结 AcWing 241. 楼兰图腾 的题解 树状数组的作用 树状数组，也叫做二叉索引树，或Fenwick树。 可以高效实现两个操作： 数组前缀和的查询单点更新——某个点增…
2022/1/9 23:08:27 人评论 次浏览 -
【数据结构】零基础树状数组笔记
参考和引用 树状数组学习笔记 树状数组 数据结构详解与模板(可能是最详细的了) 树状数组（简单介绍） 树状数组小结 AcWing 241. 楼兰图腾 的题解 树状数组的作用 树状数组，也叫做二叉索引树，或Fenwick树。 可以高效实现两个操作： 数组前缀和的查询单点更新——某个点增…
2022/1/9 23:08:27 人评论 次浏览 -
cf959 E. Mahmoud and Ehab and the xor-MST（找规律，数学）
题意： n个顶点的完全图，编号为0~n-1，任意两点间的边权为两个点的编号的异或，求最小生成树的边权总和。（仍是普通加和，不是异或和） 思路： 为讨论方便，把输入的n减一。 先写个prim找规律，发现除了0外，每个点 \(i\) 都向 \(i \oplus lowbit(i)\) 连一条边。总和就…
2021/12/23 6:37:29 人评论 次浏览 -
cf959 E. Mahmoud and Ehab and the xor-MST（找规律，数学）
题意： n个顶点的完全图，编号为0~n-1，任意两点间的边权为两个点的编号的异或，求最小生成树的边权总和。（仍是普通加和，不是异或和） 思路： 为讨论方便，把输入的n减一。 先写个prim找规律，发现除了0外，每个点 \(i\) 都向 \(i \oplus lowbit(i)\) 连一条边。总和就…
2021/12/23 6:37:29 人评论 次浏览 -
初学 二维树状数组
二维树状数组可以高效解决二维动态矩形计数问题。 我先带你回顾一下一维树状数组是怎样的：\[c_n=\sum\limits^n_{i=n-lowbit(n)+1}a_i \]设 \(\{d^{(n)}\}\) 为 \[\begin{cases}d_1=n\\ d_i=d_{i-1}-lowbit(d_{i-1}) & i>1 \\ d_i>0 & i\in\mathbb{N}^+\e…
2021/11/10 23:16:40 人评论 次浏览 -
初学 二维树状数组
二维树状数组可以高效解决二维动态矩形计数问题。 我先带你回顾一下一维树状数组是怎样的：\[c_n=\sum\limits^n_{i=n-lowbit(n)+1}a_i \]设 \(\{d^{(n)}\}\) 为 \[\begin{cases}d_1=n\\ d_i=d_{i-1}-lowbit(d_{i-1}) & i>1 \\ d_i>0 & i\in\mathbb{N}^+\e…
2021/11/10 23:16:40 人评论 次浏览 -
程序竞赛——位运算常用操作
位运算 & 与 | 或 ~ 非 ^ 异或 >> 右移 << 左移 常用操作： (1) 求x的第k位数字 x >> k & 1 (2) lowbit(x) = x & -x，返回x的最后一位1 求整数的二进制数表示中的第k位是几？n = 15 =(1111)2 :从0位开始的（右到左）先把第k位移到最后一位…
2021/10/24 17:12:07 人评论 次浏览
