头像

jiashihong


访客:3059

离线:7小时前


活动打卡代码 AcWing 826. 单链表

jiashihong
2个月前
#include<iostream>

using namespace std;

const int N=1e6+10;
int e[N],ne[N];
int head,idx;

void init()
{
    head=-1;
    idx=0;
}
void add_at_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
void remove_k(int k)
{
    ne[k]=ne[ne[k]];
}
void insert_at_k(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}

int main()
{
    int m;
    cin>>m;
    init();
    char ch;
    int x,k;
    while(m--)
    {
        cin>>ch;
        if(ch=='H')
        {
            cin>>x;
            add_at_head(x);
        }
        else if(ch=='D')
        {
            cin>>k;
            if(k==0) head=ne[head];
            else remove_k(k-1);
        }
        else
        {
            cin>>k>>x;
            insert_at_k(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
    {
        cout<<e[i]<<" ";
        //head=ne[head];
    }

    return 0;
}



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

jiashihong
2个月前
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<pair<int,int>> v(n);
    for(int i=0;i<n;i++) cin>>v[i].first>>v[i].second;

    sort(v.begin(),v.end());

    if(v.size()<=1) cout<<v.size()<<endl;
    else
    {
        int cnt=0;
        for(int i=1;i<v.size();i++)
        {
            if(v[i].first>v[i-1].second)
            {
                cnt++;
            }
            else
            {
                v[i].first=v[i-1].first;
                v[i].second=max(v[i-1].second,v[i].second);
            }
        }
        cnt++;
        cout<<cnt<<endl;
    }

    return 0;
}


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

jiashihong
2个月前
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int N=3e6+10;
int n,m;
int a[N],s[N];
vector<int> all(n);
vector<pair<int,int>> add;
vector<pair<int,int>> q;

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

    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        all.push_back(x);
    }
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        q.push_back({l,r});
        all.push_back(l);
        all.push_back(r);
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());

    for(int i=0;i<n;i++)
    {
        int x=find(add[i].first);
        a[x]+=add[i].second;
    }
    for(int i=1;i<=all.size();i++) s[i]=s[i-1]+a[i];    //记住是从1开始!!!!!

    for(int i=0;i<q.size();i++)
    {
        int l=find(q[i].first),r=find(q[i].second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}



jiashihong
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 cnt=0;
        /*
        while(x)
        {
            x-=lowbit(x);
            cnt++;
        }
        */
        while(x)
        {
            cnt+=x&1;
            x>>=1;
        }
        cout<<cnt<<" ";
    }
}



jiashihong
2个月前
#include<iostream>
using namespace std;

const int N=100010;
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,j>=0;)
    {
        if(a[i]+b[j]>x) j--;
        else if(a[i]+b[j]<x) i++;
        else
        {
            cout<<i<<" "<<j<<endl;
            break;
        }
    }


    return 0;
}




jiashihong
2个月前
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];

    unordered_map<int,int> h;
    int res=0;
    for(int i=0,j=0;i<n;i++)
    {
        h[v[i]]++;
        while(j<=i&&h[v[i]]>1) h[v[j++]]--;
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

jiashihong
2个月前
#include<iostream>

using namespace std;

const int N=1010;
int a[N][N],b[N][N];
int n,m,q,x1,y1,x2,y2,c;

void insert(int x1,int y1,int x2,int y2,int c)    //关键!!!!!!!
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

jiashihong
2个月前
#include<iostream>

using namespace std;

const int N=100010;
int a[N],b[N];
int n,m,l,r,c;

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) insert(i,i,a[i]);
    while(m--)
    {
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++) b[i]+=b[i-1];
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";
    cout<<endl;
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

jiashihong
2个月前
#include<iostream>

using namespace std;

const int N=1010;
int a[N][N],s[N][N];
int n,m,q,x1,x2,y1,y2;
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    while(q--)
    {
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;

    }

    return 0;
}


活动打卡代码 AcWing 795. 前缀和

jiashihong
2个月前
#include<iostream>

using namespace std;

const int N=100010;
int a[N],s[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

    int l,r;
    while(m--)
    {
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }


    return 0;
}