头像

未闻花语




离线:6小时前


最近来访(2)
用户头像
LHHHHHH
用户头像
21KINGDMG


未闻花语
6小时前

题目描述

blablabla

样例

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

typedef pair<int,int> p;
vector<p> a,t;  //a为原数组,t为中间数组 

void merge(vector<p> &a){
    int st=-2e9, ed=-2e9;
    for(auto u:a){
        if(ed<u.first){   //第一种可能没有交集 直接放入中间数组 
            if(st!=-2e9)   t.push_back({st,ed});
            st=u.first, ed=u.second;   //再让区间去往下一个判断 
        }
        else ed=max(ed,u.second);  //再是第二种可能 
    }
    if(st!=-2e9)   t.push_back({st,ed});//由于本身代码并非从一开始,所以要将最后一个放入(同时判断并非空数组) 
    a=t;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int l,r;
        cin>>l>>r;
        a.push_back({l,r});
    }
    sort(a.begin(),a.end());//先排序(若下一区间头大于上一区间尾 则下区间必与前区间无交集) 
    merge(a);
    cout<<a.size()<<endl;
} 


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

未闻花语
6小时前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> p;
vector<p> a,t;

void merge(vector<p> &a){
    int st=-2e9, ed=-2e9;
    for(auto u:a){
        if(ed<u.first){
            if(st!=-2e9)  t.push_back({st,ed});
            st=u.first,  ed=u.second;
        }
        else ed=max(ed,u.second);
    }
    if(st!=-2e9)  t.push_back({st,ed});
    a=t;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int l,r;
        cin>>l>>r;
        a.push_back({l,r});
    }
    sort(a.begin(),a.end());
    merge(a);
    cout<<a.size()<<endl;
} 


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

未闻花语
7小时前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N=3e5+10;
int a[N],s[N];

typedef pair<int,int> p;
vector<p> add,query;
vector<int> t;

int find(int x){
    int l=0, r=t.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(t[mid]>=x)   r=mid;
        else  l=mid+1;
    }
    return r+1;
}

int main(){
    int n,m;
    cin>>n>>m;
    while(n--){
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        t.push_back(x);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});
        t.push_back(l), t.push_back(r);
    }
    sort(t.begin(),t.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    for(auto u:add){
        int x=find(u.first);
        a[x]+=u.second;
    }
    for(int i=1;i<=t.size();i++)  s[i]=s[i-1]+a[i];
    for(auto u:query){
        int l=find(u.first),  r=find(u.second);
        cout<<s[r]-s[l-1]<<endl;
    }
}



未闻花语
8小时前

题目描述

blablabla

样例

blablabla
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N];

int lowbit(int x){
    return x&-x;    //返回该数在二进制下的最后一位1及其后
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        int t=0;
        while(a[i])
        a[i]-=lowbit(a[i]), t++;
        cout<<t<<" ";
    }
}



未闻花语
8小时前
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N];

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

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        int t=0;
        while(a[i])
        a[i]-=lowbit(a[i]), t++;
        cout<<t<<" ";
    }
}



未闻花语
8小时前

题目描述

blablabla

样例

blablabla
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],b[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)  cin>>a[i];
    for(int i=0;i<m;i++)  cin>>b[i];
    int i=0,j=0;
    while(i<n && m-j>=n-i){
        if(a[i]==b[j])  i++;     //短与长匹配 长本身自增(j++)  匹配成功 短再自增(i才后移) 
        j++;
    }
    if(i==n)   cout<<"Yes"<<endl;
    else  cout<<"No"<<endl;
}

双指针我觉得更应思考的是,两个指针该从哪里出发



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

未闻花语
8小时前
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],b[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)  cin>>a[i];
    for(int i=0;i<m;i++)  cin>>b[i];
    int i=0,j=0;
    while(i<n && m-j>=n-i){
        if(a[i]==b[j])  i++;
        j++;
    }
    if(i==n)   cout<<"Yes"<<endl;
    else  cout<<"No"<<endl;
}



未闻花语
9小时前

题目描述

blablabla

样例

blablabla
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],b[N];

int main(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)   cin>>a[i];
    for(int i=0;i<m;i++)   cin>>b[i];
    for(int i=0,j=m-1;i<n;i++){
        while(a[i]+b[j]>x&&j>0)   j--; //利用升序 最小+最大 
        if(a[i]+b[j]==x)
        cout<<i<<" "<<j<<endl;
    }
}

双指针要么两头出发,要么一头出发。根据题意更好选择
i=0,j=0 j<m&&A[i]+B[j]<x 和 i=0,j=m-1 A[i]+B[j]!=x 是不行的
都会有在j=m/j=0 的时候 条件刚好不满足。 把代码写入 看数据个例 即可知道




未闻花语
9小时前
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],b[N];

int main(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)   cin>>a[i];
    for(int i=0;i<m;i++)   cin>>b[i];
    for(int i=0,j=m-1;i<n;i++){
        while(a[i]+b[j]>x&&j>0)   j--;
        if(a[i]+b[j]==x)
        cout<<i<<" "<<j<<endl;
    }
}



未闻花语
9小时前

题目描述

blablabla

样例

blablabla
#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],s[N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)   cin>>a[i];
    int res=0;
    for(int i=0,j=0;i<n;i++){
        s[a[i]]++;           //表示a[i]的个数
        while(s[a[i]]>1)    //表明重复,j后移 
        s[a[j++]]--;        //直到让j指向在a[i]重复的位置 
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
}
for(int i=0,j=0;i<n;i++){
    s[a[i]]++;
    if(s[a[i]]>1&&j<i){
        j++;
    }   严重错误
去除a[i]前的次数很有必要,若为 1 2 1 2...... 
  此种类型不可直接j=i,2 1 2同样是不重复
    在除去重复次数后,才能实现目的