头像

CodeWater




离线:11小时前



题目描述

原题

给定 n 个区间 [li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式
第一行包含整数n。

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

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

数据范围
1≤n≤100000,
−109≤li≤ri≤109

输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3


算法:模拟 + 贪心

思路:
1.先把所有区间的左端点进行排序。(这是为了后面遍历的时候,减少一种区间关系:下一个的区间左端点比
当前这个区间的左端点还要小)
2.排完序后就可以对区间进行合并了。合并也很简单,就是比较下一个区间的左端点跟当前这个区间的右端点
进行比较,如果下一个区间的左端点大于当前区间的右端点的话,那就说明这两个区间没有交集,直接把当前
这个区间加入到数组去,如果小于,说明这两个区间有交集,此时选取较大的左端点,更新。
3.遍历结束后,也就完成了区间合并。
(详情见代码注释)

区间左端点排完序之后的区间关系:
acwing803区间合并.png
(来源y总视频)

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;
//每个区间都有左右两个端点,我们用pair类型来表示
typedef pair<int,int> PII;
//存储每个区间的端点,类型是pair
vector<PII> segs;

//把给定的区间合并成没有交集的区间
void merge(vector<PII> &segs){
    //定义个临时存放答案的
    vector<PII> res;
    //先对每个区间的左端点进行排序
    sort(segs.begin(),segs.end());
    //定义个两个临时区间端点,用于比较,初始值定为负无穷
    int start = -2e9 , end = -2e9 ; 
    //遍历每个区间
    for(auto seg : segs){
        //遍历的下一个区间跟当前这个区间没有交集的话
        if(end < seg.first){
            //这里的这个判断是防止把最开始自己定义无穷大的区间给放进去
            if(start != -2e9) res.push_back({start , end});
            //然后更新一下下一个新的区间的左右端点
            start = seg.first , end = seg.second;
        }
        else{//如果有交集的话
        //那我们就需要把当前的这个区间右端点更新为较大的那个,合并掉
            end = max(end , seg.second);
        }
    }
    //最后把最后一个没有放进去的区间给加入到vector中,这个判断主要是防止
    //空区间输入的是
    if(start != -2e9) res.push_back({start,end});
    //最后更新到答案vector中
    segs = res;

}

int main(){
    //输入n
    int n;
    cin>>n;
    for(int i = 0 ; i < n ; i++){
        int l , r;
        cin >> l >> r;
        //把n对区间放到vector中
        segs.push_back({l,r});

    }
    merge(segs);
    //输出合并后的区间个数
    cout<<segs.size()<<endl;
    return 0;
}


活动打卡代码 AcWing 803. 区间合并

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;
//每个区间都有左右两个端点,我们用pair类型来表示
typedef pair<int,int> PII;
//存储每个区间的端点,类型是pair
vector<PII> segs;

//把给定的区间合并成没有交集的区间
void merge(vector<PII> &segs){
    //定义个临时存放答案的
    vector<PII> res;
    //先对每个区间的左端点进行排序
    sort(segs.begin(),segs.end());
    //定义个两个临时区间端点,用于比较,初始值定为负无穷
    int start = -2e9 , end = -2e9 ; 
    //遍历每个区间
    for(auto seg : segs){
        //遍历的下一个区间跟当前这个区间没有交集的话
        if(end < seg.first){
            //这里的这个判断是防止把最开始自己定义无穷大的区间给放进去
            if(start != -2e9) res.push_back({start , end});
            //然后更新一下下一个新的区间的左右端点
            start = seg.first , end = seg.second;
        }
        else{//如果有交集的话
        //那我们就需要把当前的这个区间右端点更新为较大的那个,合并掉
            end = max(end , seg.second);
        }
    }
    //最后把最后一个没有放进去的区间给加入到vector中,这个判断主要是防止
    //空区间输入的是
    if(start != -2e9) res.push_back({start,end});
    //最后更新到答案vector中
    segs = res;

}

int main(){
    //输入n
    int n;
    cin>>n;
    for(int i = 0 ; i < n ; i++){
        int l , r;
        cin >> l >> r;
        //把n对区间放到vector中
        segs.push_back({l,r});

    }
    merge(segs);
    //输出合并后的区间个数
    cout<<segs.size()<<endl;
    return 0;
}



题目描述

原题

假定有一个无限长的数轴,数轴上每个坐标上的数都是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


算法

离散化:
第一步,排序后去重。
第二步,求离散化后值,用二分做。
(思路就是视频讲的,具体都在代码注释里面)

没有unique(去重)函数的,可以参考这个实现:
不重复元素满足这两个性质
acwing802区间和(unique函数).png

//返回的是一个迭代器,双指针算法
/*
第一个指针j是遍历所有的数,第二个指针是指向当前存到了第几个不同的数
*/
vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
    //若不满足上述途中的两个性质, !i是第一个数
        if (!i || a[i] != a[i - 1])
        //把当前这个数付给前面,j指针再往后走
            a[j ++ ] = a[i];
    // a[0] ~ a[j - 1] 所有a中不重复的数

//这样就是从0到j这个位置的就是所有不同的数。
    return a.begin() + j;
}


参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

//pair存储每个操作
typedef pair<int,int> PII;

/*
因为共n个操作,m次询问,而每次询问都是有两个边界坐标,n和m都是在(1,10^5)这个
范围内,所以总共的规模是n + 2m,也就是30万。
10是多开的,防止边界问题
*/
const int N = 300010;
//a 是存储题目给定的数  s是前缀和
int a[N], s[N];
int n , m;
//vector是所有要离散化的值
vector<int> alls;
//add插入操作  query是求操作
vector<PII> add , query;

//求一下x这个值离散化之后的结果
int find(int x){
    //从l——r之间找一个值
    int l = 0 , r = alls.size() - 1;
    while(l < r){
        //mid中点
        int  mid = l + r >> 1;
        //找到大于等于x的最小值
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    //映射到从1开始的自然数,因为这道题会用到前缀和,所用从1开始,减少一些边界情况
    return r + 1;
}

int main(){
    cin>>n>>m;
    for(int i = 0 ; i < n ; i++){
        int x , c ;
        cin>> x >> c;
        //插入操作,在下标x的位置加上c
        add.push_back({x,c});
        //要把下标x进行离散化,那么就需要把这个x加入到待离散化的数组里面去
        alls.push_back(x);
    }
    //输入进行m次操作
    for(int i = 0 ; i < m ; i++){
        int l , r;
        cin>> l >> r;

        query.push_back({l,r});
        //l 和 r坐标是需要离散化的,所以也把他们加入到待离散化的数组里面去
        alls.push_back(l);
        alls.push_back(r);
    }//这个时候就已经把所有需要离散化的下标放进了数组。

    //下一步就需要对alls数组进行去重
    //先排序
    sort(alls.begin(),alls.end());
    //把重复的元素去掉,unique函数把不重复的元素放在前面重复的放在后面,返
    //回不重复元素的最后一个位置
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    //分别处理一下两种操作
    for(auto item : add){
        //首先求一下x这个值离散化之后的结果是多少
        int x = find(item.first);
        //在离散化之后的坐标上加上要加的数
        a[x] += item.second;

    }

    //预处理一下前缀和
    for(int i = 1 ; i <= alls.size() ; i++) s[i] = s[i - 1] + a[i];

    //处理询问
    for(auto  item : query){
        //左边是item.first离散化之后的结果,item.first存的是左区间
        //r同理
        int l = find(item.first) , r = find(item.second);
        //中间所有数的个数的和,用前缀和公式来
        cout<<s[r] - s[l - 1]<<endl;

    }

    return 0;
}


活动打卡代码 AcWing 802. 区间和

没有unique(去重)函数的,可以参考这个实现:
不重复元素满足这两个性质
acwing802区间和(unique函数).png

//返回的是一个迭代器,双指针算法
/*
第一个指针j是遍历所有的数,第二个指针是指向当前存到了第几个不同的数
*/
vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
    //若不满足上述途中的两个性质, !i是第一个数
        if (!i || a[i] != a[i - 1])
        //把当前这个数付给前面,j指针再往后走
            a[j ++ ] = a[i];
    // a[0] ~ a[j - 1] 所有a中不重复的数

//这样就是从0到j这个位置的就是所有不同的数。
    return a.begin() + j;
}

题解代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

//pair存储每个操作
typedef pair<int,int> PII;

const int N = 300010;
//a 是存储题目给定的数  s是前缀和
int a[N], s[N];
int n , m;
//vector是所有要离散化的值
vector<int> alls;
//add插入操作  query是求操作
vector<PII> add , query;

//求一下x这个值离散化之后的结果
int find(int x){
    //从l——r之间找一个值
    int l = 0 , r = alls.size() - 1;
    while(l < r){
        //mid中点
        int  mid = l + r >> 1;
        //找到大于等于x的最小值
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    //映射到从1开始的自然数,因为这道题会用到前缀和,所用从1开始,减少一些边界情况
    return r + 1;
}

int main(){
    cin>>n>>m;
    for(int i = 0 ; i < n ; i++){
        int x , c ;
        cin>> x >> c;
        //插入操作,在下标x的位置加上c
        add.push_back({x,c});
        //要把下标x进行离散化,那么就需要把这个x加入到待离散化的数组里面去
        alls.push_back(x);
    }
    //输入进行m次操作
    for(int i = 0 ; i < m ; i++){
        int l , r;
        cin>> l >> r;

        query.push_back({l,r});
        //l 和 r坐标是需要离散化的,所以也把他们加入到待离散化的数组里面去
        alls.push_back(l);
        alls.push_back(r);
    }//这个时候就已经把所有需要离散化的下标放进了数组。

    //下一步就需要对alls数组进行去重
    //先排序
    sort(alls.begin(),alls.end());
    //把重复的元素去掉,unique函数把不重复的元素放在前面重复的放在后面,返
    //回不重复元素的最后一个位置
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    //分别处理一下两种操作
    for(auto item : add){
        //首先求一下x这个值离散化之后的结果是多少
        int x = find(item.first);
        //在离散化之后的坐标上加上要加的数
        a[x] += item.second;

    }

    //预处理一下前缀和
    for(int i = 1 ; i <= alls.size() ; i++) s[i] = s[i - 1] + a[i];

    //处理询问
    for(auto  item : query){
        //左边是item.first离散化之后的结果,item.first存的是左区间
        //r同理
        int l = find(item.first) , r = find(item.second);
        //中间所有数的个数的和,用前缀和公式来
        cout<<s[r] - s[l - 1]<<endl;

    }

    return 0;
}



题目描述

原题

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

输入格式
第一行包含整数n。

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

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

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

输入样例:

5
1 2 3 4 5

输出样例:

1 1 2 1 2


算法:位运算

lowbit操作。就是看一个数的二进制表示他的右边第一个1是在第几位。比如100101000这个二进制数,
他的lowbit就是1000.这个通常用来看一个二进制数里面有多少个1.因为每次lowbit之后,我们把右边
的1去掉,然后继续lowbit,直到最后都去掉之后就可以累加算出这个二进制数里面有多少个1.

时间复杂度

O(nlogn)

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//lowbit运算
int lowBit(int x){
    return x & -x;
}

int main(){
    int n;
    cin>>n;

    while(n--){  
        int res = 0;
        int x;
        cin>>x;
        //每次减掉最右边的1,答案记录加1,直到为0就结束
        while(x) x -= lowBit(x), res ++;
        cout<<res<<' ';
    }

    return 0;
}




#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//lowbit运算
int lowBit(int x){
    return x & -x;
}

int main(){
    int n;
    cin>>n;

    while(n--){  
        int res = 0;
        int x;
        cin>>x;
        //每次减掉最右边的1,答案记录加1,直到为0就结束
        while(x) x -= lowBit(x), res ++;
        cout<<res<<' ';
    }

    return 0;
}




题目描述

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式
第一行包含两个整数 n,m。

第二行包含 n 个整数,表示 a1,a2,…,an。

第三行包含 m 个整数,表示 b1,b2,…,bm。

输出格式
如果 a 序列是 b 序列的子序列,输出一行 Yes。

否则,输出 No。

数据范围

1≤n≤m≤105,
−109≤ai,bi≤109

输入样例:

3 5
1 3 5
1 2 3 4 5

输出样例:

Yes


算法:双指针

双指针算法。定义两个变量i, j,i指向第一个序列,j指向第二个序列,只有当两个指向的值相等的时候,
i才会继续往后继续进行遍历,而j不管,一直往后遍历。
注意本题的子序列不要求连续。

时间复杂度

O(n)

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include<cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//a第一个序列  b第二个序列
int a[N], b[N];

int main(){
    int n , m;
    scanf("%d%d", &n , &m);
    //输入给定的序列
    for(int i = 0 ; i < n; i++)scanf("%d",&a[i]);
    for(int i = 0 ; i < m ; i++)scanf("%d",&b[i]);
    //定义两个指针变量,i遍历第一个序列,j遍历第二个序列
    int i = 0 ,j = 0;
    //遍历两个虚拟
    while(i < n && j < m){
        //只有当a[i]=b[j]的时候,i才会往后走
        if(a[i] == b[j]) i++;
        //而j不管当前两个值是否相等,j都往后遍历
        j++;
    }
    //当退出循环之后,i已经遍历完了第一个序列,说明已经找到一个子序列
    if(i == n ) printf("Yes");
    else printf("No");
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

双指针

#include <iostream>
#include<cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//a第一个序列  b第二个序列
int a[N], b[N];

int main(){
    int n , m;
    scanf("%d%d", &n , &m);
    //输入给定的序列
    for(int i = 0 ; i < n; i++)scanf("%d",&a[i]);
    for(int i = 0 ; i < m ; i++)scanf("%d",&b[i]);
    //定义两个指针变量,i遍历第一个序列,j遍历第二个序列
    int i = 0 ,j = 0;
    //遍历两个虚拟
    while(i < n && j < m){
        //只有当a[i]=b[j]的时候,i才会往后走
        if(a[i] == b[j]) i++;
        //而j不管当前两个值是否相等,j都往后遍历
        j++;
    }
    //当退出循环之后,i已经遍历完了第一个序列,说明已经找到一个子序列
    if(i == n ) printf("Yes");
    else printf("No");
    return 0;
}



题目描述

原题

给定两个升序排序的有序数组A和B,以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

输入格式
第一行包含三个整数n,m,x,分别表示A的长度,B的长度以及目标值x。

第二行包含n个整数,表示数组A。

第三行包含m个整数,表示数组B。

输出格式
共一行,包含两个整数 i 和 j。

数据范围
数组长度不超过100000。
同一数组内元素各不相同。
1≤数组元素≤109

输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1


算法:双指针

题目保证有唯一解,所以在找到答案的时候就可以直接跳出循环。
这题给的两个序列都是升序的,所以我们定义两个指针变量,一个指向第一个序列的第一个,
一个指向第二个序列的最后一个,判断这两个值的和跟目标值的大小情况。如果,大于,那么j
就往前遍历,如果等于正好就直接输出。不存在小于,因为题目保证有唯一解。

时间复杂度

O(n+m)

参考文献

y总讲解视频

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//a数组:存放第一个序列  b数组存放第二个序列
int a[N],b[N];

int main(){
    //n第一个数组的个数  m第二个数组的个数  x目标值
    int n , m , x;
    scanf("%d%d%d",&n,&m,&x);
    for(int i = 0 ; i < n ; i++)scanf("%d",&a[i]);
    for(int j = 0 ; j < m ; j++ )scanf("%d",&b[j]);
    //双指针。i从第一个序列的第一个开始遍历,j从第二个序列的最后一个
    //进行遍历,当a[i] + b[j]等于目标值x的时候,就直接输出,本题保证
    //有唯一解,所以找到的时候直接跳出循环。如果不是的话,另外在进行考虑
    for(int  i = 0 , j = m - 1 ; i < n ;i++){
        //当两个值大于目标值的时候j指针往前移,因为序列是升序的,所以往前
        //才能找到。
        while(a[i] + b[j] > x) j--;
        if(a[i] + b[j] == x){
            printf("%d %d",i,j);
            break;
        }
    }
    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
//a数组:存放第一个序列  b数组存放第二个序列
int a[N],b[N];

int main(){
    //n第一个数组的个数  m第二个数组的个数  x目标值
    int n , m , x;
    scanf("%d%d%d",&n,&m,&x);
    for(int i = 0 ; i < n ; i++)scanf("%d",&a[i]);
    for(int j = 0 ; j < m ; j++ )scanf("%d",&b[j]);
    //双指针。i从第一个序列的第一个开始遍历,j从第二个序列的最后一个
    //进行遍历,当a[i] + b[j]等于目标值x的时候,就直接输出,本题保证
    //有唯一解,所以找到的时候直接跳出循环。如果不是的话,另外在进行考虑
    for(int  i = 0 , j = m - 1 ; i < n ;i++){
        //当两个值大于目标值的时候j指针往前移,因为序列是升序的,所以往前
        //才能找到。
        while(a[i] + b[j] > x) j--;
        if(a[i] + b[j] == x){
            printf("%d %d",i,j);
            break;
        }
    }
    return 0;
}