头像

wangyj

北京市海淀区花园村第二小学


访客:392

离线:13小时前


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

wangyj
6天前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,a[300005],s[300005];
vector<int>alls;
vector<pair<int,int> >add,query;
int find(int x)
{
    int l=0,r=alls.size()-1,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(alls[mid]>=x)r=mid;
        else l=mid+1;
    }
    return r+1;
}
vector<int>::iterator unique(vector<int>&a)
{
    int j=0,i;
    for (i=0;i<a.size();i++)
        if(!i||a[i]!=a[i-1])a[j++]=a[i];
    return a.begin()+j;
}
int main()
{
    int i,l,r,x,c;
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(i=0;i<m;i++){
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls), alls.end());
    for(auto item:add){
        x=find(item.first);
        a[x]+=item.second;
    }
    for(i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];
    for(auto item:query){
        l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}



wangyj
6天前

803. 区间合并

题目描述

给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行,每行包含两个整数 l 和 r。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−10^9≤li≤ri≤10^9

样例

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

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
vector[HTML_REMOVED] > sect,newsec;
main()
{
int n,i,l,r,l1,r1;
scanf(“%d”,&n);
for(i=0;i[HTML_REMOVED] > ::iterator iter;
for(iter=sect.begin();iter!=sect.end();iter){
if(r1<(*iter).first){
// newsec.push_back({l1,r1}); // if use { } g
complier will warning
newsec.push_back(make_pair(l1,r1));
l1=(iter).first;
r1=(
iter).second;
}
else{
if(r1<(iter).second)r1=(iter).second;
}
}
newsec.push_back(make_pair(l1,r1));
printf(“%d\n”,newsec.size());
return 0;
}
```



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

wangyj
6天前

803. 区间合并

给定 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

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> > sect,newsec;
main()
{
    int n,i,l,r,l1,r1;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d",&l,&r);
        sect.push_back(make_pair(l,r));
    }
    sort(sect.begin(),sect.end());
    l1=(*sect.begin()).first;
    r1=(*sect.begin()).second;
    vector<pair<int,int> > ::iterator iter;
    for(iter=sect.begin();iter!=sect.end();iter++){
        if(r1<(*iter).first){
//          newsec.push_back({l1,r1});      // if use { } g++ complier will warning 
            newsec.push_back(make_pair(l1,r1));
            l1=(*iter).first;
            r1=(*iter).second;
        }
        else{
            if(r1<(*iter).second)r1=(*iter).second;
        }
    }
    newsec.push_back(make_pair(l1,r1));
    printf("%d\n",newsec.size());
    return 0;
}



wangyj
8天前
  1. 数组元素的目标和
    给定两个升序排序的有序数组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
#include<cstdio>
using namespace std;
int a[100005],b[100005];
int main()
{
    int n,m,x,i,j;
    scanf("%d%d%d",&n,&m,&x);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    for(i=0;i<m;i++)scanf("%d",&b[i]);
    for(i=0,j=m-1;i<n;i++){
        while(j>=0&&a[i]+b[j]>x)j--;
        if(a[i]+b[j]==x){
            printf("%d %d\n",i,j);
            return 0;
        }
    }
}

今天有点晚,所以比较简洁,大家可以看一下




wangyj
8天前
  1. 数组元素的目标和
    给定两个升序排序的有序数组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
#include<cstdio>
using namespace std;
int a[100005],b[100005];
int main()
{
    int n,m,x,i,j;
    scanf("%d%d%d",&n,&m,&x);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    for(i=0;i<m;i++)scanf("%d",&b[i]);
    for(i=0,j=m-1;i<n;i++){
        while(j>=0&&a[i]+b[j]>x)j--;
        if(a[i]+b[j]==x){
            printf("%d %d\n",i,j);
            return 0;
        }
    }
}

今天有点晚,所以比较简洁,大家可以看一下




wangyj
12天前

801. 二进制中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<cstdio>
using namespace std;
int lowbits(int m)
{
    return -m&m;
}
int main()
{
    int n,m,sum;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        sum=0;
        while(m){
            m-=lowbits(m);
            sum++;
        }
        printf("%d ",sum);
    }
    printf("\n");
    return 0;
}

作者注:本程序是根据闫老师的代码总结后自己写的,不是抄的,望各位老师们多多指教,谢谢




wangyj
12天前

801. 二进制中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<cstdio>
using namespace std;
int lowbits(int m)
{
    return -m&m;
}
int main()
{
    int n,m,sum;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        sum=0;
        while(m){
            m-=lowbits(m);
            sum++;
        }
        printf("%d ",sum);
    }
    printf("\n");
    return 0;
}

作者注:本程序是根据闫老师的代码总结后自己写的,不是抄的,望各位老师们多多指教,谢谢




wangyj
12天前

799. 最长连续不重复子序列

题目描述:

给定一个长度为n的整数序列,请找出最长的不包含重复数字的连续区间,输出它的长度。

输入格式

第一行包含整数n。
第二行包含n个整数(均在0~100000范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复数字的连续子序列的长度。

数据范围

1≤n≤100000

样例:

输入样例:

5
1 2 2 3 5

输出样例:

3

程序:

#include<iostream>
using namespace std;
int a[100005],s[100005];
int main()
{
    int n,sum=0,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    for(i=0,j=0;i<n;i++){
        s[a[i]]++;
        while(j<=i&&s[a[i]]>1){s[a[j]]--,j++;}
        sum=max(sum,i-j+1);
    }
    printf("%d\n",sum);
    return 0;
}

大家点个赞哟~




wangyj
12天前

799. 最长连续不重复子序列

题目描述:

给定一个长度为n的整数序列,请找出最长的不包含重复数字的连续区间,输出它的长度。

输入格式

第一行包含整数n。
第二行包含n个整数(均在0~100000范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复数字的连续子序列的长度。

数据范围

1≤n≤100000

样例:

输入样例:

5
1 2 2 3 5

输出样例:

3

程序:

#include<iostream>
using namespace std;
int a[100005],s[100005];
int main()
{
    int n,sum=0,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    for(i=0,j=0;i<n;i++){
        s[a[i]]++;
        while(j<=i&&s[a[i]]>1){s[a[j]]--,j++;}
        sum=max(sum,i-j+1);
    }
    printf("%d\n",sum);
    return 0;
}

大家点个赞哟~



活动打卡代码 AcWing 786. 第k个数

wangyj
13天前

786. 第k个数

题目描述:

给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列的第k小的数是多少。

输入格式

第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。

输出格式

输出一个整数,表示数列的第k小数。

数据范围

1≤n≤100000,
1≤k≤n

样例:

输入样例:

5 3
2 4 1 5 3

输出样例:

3

程序:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000005],i,j,n,x,m;
void quick_sort(int a[],int down,int up)
{
    if(down>=up)return;
    i=down-1,j=up+1,x=a[(down+up)/2];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    quick_sort(a,down,j);
    quick_sort(a,j+1,up);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    quick_sort(a,0,n-1);
    printf("%d\n",a[m-1]);
    return 0;
}

作者注:本程序是先排序,后直接输出的。与闫老师讲的方法不太一样,但是写着比较简单。也可以作为参考。