位运算 离散化 区间和算法

这篇具有很好参考价值的文章主要介绍了位运算 离散化 区间和算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、位运算

1.1 思路

首先知道一个概念:一个正整数的负数等于其按位取反后+1
-x = ~x + 1
举个例子:3
给一个数 和一个区间 通过位运算 判断是否属于该区间,百炼成钢,算法,c++,数据结构
而我们通过(x & ~x + 1)或(x & -x)就可以得到二进制数最后一位1的大小。
举个例子:
给一个数 和一个区间 通过位运算 判断是否属于该区间,百炼成钢,算法,c++,数据结构

1.1 例题:二进制中1的个数

题目链接

题目描述

给定一个长度为 n 的数列,请你求出数列中每个数的二进制表示中 1 的个数。

输入格式

第一行包含整数 n。
第二行包含 n 个整数,表示整个数列。

输出格式

共一行,包含 n 个整数,其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。

数据范围

1≤n≤100000,
0≤数列中元素的值≤109

输入样例:

5
1 2 3 4 5

输出样例:

1 1 2 1 2

#include<iostream>

using namespace std;

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        int sum = 0;
        while(x)
        {
            x -= lowbit(x);
            sum++;
        }
        cout << sum << " ";
    }
    return 0;
}

二、离散化

2.1 概念

联想之前讲过的计数排序八大排序,你都掌握了吗?,当两个坐标差距非常大的时候,就不好处理了。而离散化就是把这些下标全部聚集在一起。直接看例题:

2.2 例题:区间和

题目链接

题目描述

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。

输入格式

第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。

输出格式

共 m 行,每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000

输入样例:

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例:

8
0
5

思路分析:
下标过于多且可能非常分散,而且是无序且可能重复,那么我们可以把需要用到的下标统计起来,例如(8, 11, 5, 1, 8),然后把他们排序+去重,就得到(1, 5, 8, 11),这样本来需要11个位置存储,现在只需要4个位置就能存住。因为是有序的,所以如果我们要找到下标,就可以用二分查找。
补充一个去重函数:
unique

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last);

他会自动去重且把重复的元素排到最后面并且把后边重复下标的第一个位置返回回来。

给一个数 和一个区间 通过位运算 判断是否属于该区间,百炼成钢,算法,c++,数据结构

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 3e5 + 10;

int a[N], s[N];// a存数据,s存前缀和
vector<int> Index;// 下标
typedef pair<int, int> PII;
vector<PII> add, sum;
// add记录要加的下标及数据
// sum存要加的区间

//通过find找到下标
int find(int x)
{
    int l = 0, r = Index.size() - 1;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(Index[mid] >= x)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return r + 1;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int x, c;
        scanf("%d %d", &x, &c);
        add.push_back({x, c});
        Index.push_back(x);
    }
    for(int i = 0; i < m; i++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        sum.push_back({l, r});
        // 需要的下标也要加上
        Index.push_back(l);
        Index.push_back(r);
    }
    // 排序+去重Index
    sort(Index.begin(), Index.end());
    Index.erase(unique(Index.begin(), Index.end()), Index.end());
    for(int i = 0; i < n; i++)
    {
        a[find(add[i].first)] += add[i].second;
    }
    // 求前缀和
    for(int i = 1; i <= Index.size(); i++)
    {
        s[i] = a[i] + s[i - 1];
    }
    for(int i = 0; i < m; i++)
    {
        int l = find(sum[i].first), r = find(sum[i].second);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

三、合并区间

3.1 概念

给一个数 和一个区间 通过位运算 判断是否属于该区间,百炼成钢,算法,c++,数据结构
如图,上面三个区间可以合并成两个区间。

3.2 例题:合并区间

题目链接

题目描述

给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。
接下来 n 行,每行包含两个整数 l 和 r。

输出格式

共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围

1≤n≤100000,
−109≤li≤ri≤109

思路分析
我们先把所有区间存起来,再排序,这样每个区间的起始位置就是有序的。那么两个区间的位置关系只有两种情况:
1️⃣ 左区间的end >= 右区间的start,此时就要合并。
2️⃣ 左区间的end < 右区间的start,此时前面的就为一个空间

那么现在我们就可以设置一个start和end来维护当前区间,当是第一种情况时,调整end,start不变。第二种情况start和end都要去维护下一个区间。
要注意的是最后一个区间我们并没有算上,所以结果要+1文章来源地址https://www.toymoban.com/news/detail-807702.html

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
vector<PII> idx;

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        idx.push_back({l, r});
    }
    sort(idx.begin(), idx.end());
    int start = -1e9 - 10, end = -1e9 - 10;
    int sum = 0;
    for(int i = 0; i < idx.size(); i++)
    {
        if(end != -1e9 - 10 && idx[i].first > end)
        {
            ++sum;
            start = idx[i].first;
            end = idx[i].second;
        }
        else
        {
            end = max(end, idx[i].second);
        }
    }
    ++sum;// 加上最后一段区间
    cout << sum << endl;
    return 0;
}

到了这里,关于位运算 离散化 区间和算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java判断一个时间是否在当前时间区间!

            前言:我现有个定时任务 每天上午10下午4点查一次表有没有录入新数据进来 有时候录半天就没录入了 所以还得知道他是不是新数据 得知道 这条数据的时间在没在当前时间左右范围内  在的话就还在正常录入 。 目录 1.所需条件 2.将这三个进行转换类型  3.做条

    2023年04月26日
    浏览(69)
  • js实现一个函数,判断一个数是否是完全平方数

    方法一: 方法二: 该函数接受一个参数 num ,并通过二分查找的方法判断该数是否是完全平方数。如果是完全平方数,则返回 true ,否则返回 false 。

    2024年03月12日
    浏览(52)
  • C++判断一个数是否为回文数的算法

    C++判断一个数是否为回文数的算法 回文数是指正序(从左向右)和倒序(从右向左)读都相同的整数。在C++中,我们可以使用算法来判断一个数是否为回文数。下面是一个详细的解释和相应的源代码。 算法思路: 将给定的整数转换成字符串。 使用双指针法来检查字符串的左

    2024年02月06日
    浏览(53)
  • 【C语言】一个简单的C语言例子,判断一个数是否为2的幂

    目录 步骤和解释: 示例程序: 代码解释: 十进制转化成二进制: 代码解释: 首先我们需要知道的是2的幂次方在二进制中都是只有一个1的: 所以现在我们可以判断,如果二进制中只有一个1,其他位都是0,则这个数就是2的幂次方; 接着,我们使用这个数-1进行与计算,因

    2024年02月14日
    浏览(56)
  • 【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 | 位运算 | 前缀和

    DAY16共3题: 奇♂妙拆分(简单数学) 区区区间间间(单调栈) 小AA的数列(位运算dp) 🎈 作者:Eriktse 🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀 🎈 阅读原

    2023年04月20日
    浏览(49)
  • LeetCode[327]区间和的个数

    难度:Hard 题目: 给你一个整数数组  nums  以及两个整数  lower  和  upper  。求数组中,值位于范围  [lower, upper]  (包含  lower  和  upper )之内的  区间和的个数  。 区间和   S(i, j)  表示在  nums  中,位置从  i  到  j  的元素之和,包含  i  和  j  ( i  ≤  j )。 示

    2024年02月15日
    浏览(38)
  • 二叉树算法思想和原理:介绍通过递归算法计算二叉树结点个数的基本思路及C#、C++代码示例

    二叉树是一种非常常见的数据结构,它由结点组成,每个结点最多有两个子结点,分别称为左子结点和右子结点。在二叉树中,每个结点都有一个数据域和一个指针域,指针域分别指向左子结点和右子结点。二叉树有很多种不同的类型,如满二叉树、完全二叉树、平衡二叉树

    2024年01月21日
    浏览(41)
  • 算法通关村第十五关——从40亿个数中产生一个不存在的数的处理方法

    题目要求 :给定一个输入文件,包含40亿个非负整数,请设计一个算法,产生一个不存在该文件中的整数,假设你有1GB的内存来完成这项任务。**** 解题中心思想 :存储的不是这40亿个数据本身,而是其对应的位置。 本题不用写代码,能把方法过程说清楚就可以。 方法 :

    2024年02月09日
    浏览(42)
  • 算法:给你一个整数数组 nums 和一个整数k,请你统计并返回该数组中和为 k 的子数组的个数

    Java面试题目录 算法:给你一个整数数组 nums 和一个整数k,请你统计并返回该数组中和为 k 的子数组的个数 使用前缀和来实现。在保存累加和的数组preSum中,找坐标大的元素与坐标小的元素差值正好为k的个数。 leecode地址:. - 力扣(LeetCode) 直接在力扣找了个写好的答案。

    2024年01月24日
    浏览(50)
  • C++数论————质数筛法(单独判断一个数,判断N个数) 埃氏筛法

    质数想必大家都不陌生 从小学到大 质数的概念: 一个数如果除了1和本身之外没有其他的因子,那么这个数被称为质数 今天要讲两个知识点: 在C++中如何判断一个数是否为质数 在C++中如何判断1-N之间哪些数为整数 在C++中如何判断一个数是否为质数 这个知识点较为简单 充分

    2023年04月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包