头像

zhaoly




离线:2天前


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

zhaoly
27天前
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef pair<int ,int >PII;
vector <int> alls;
vector <PII> add,query; 
int a[N],s[N];
int find(int x)
{
    int l=0,r=alls.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(alls[mid]>=x)r=mid;
        else l=mid+1;
    }
    return r+1;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x,c;
        scanf("%d%d",&x,&c);
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=0;i<add.size();i++)
    {
        int x=find(add[i].first);
        a[x]+=add[i].second;
    }
    for(int i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];
    for(int i=0;i<query.size();i++)
    {
        int l=find(query[i].first);
        int r=find(query[i].second);
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

zhaoly
27天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int P=131;
typedef unsigned long long ULL;
char str[N];
ULL h[N],p[N];
void get(int l,int r,int l1,int r1)
{
    if(h[r]-h[l-1]*p[r-l+1]==h[r1]-h[l1-1]*p[r1-l1+1])
        printf("Yes\n");
    else 
        printf("No\n"); 
}
int main()
{   
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    h[0]=0,p[0]=1;
    for(int i=1;i<=N;i++)
    {
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P; 
    }
    while(m--)
    {
        int l,r,l1,r1;
        scanf("%d%d%d%d",&l,&r,&l1,&r1);
        get(l,r,l1,r1);
    }
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

zhaoly
27天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int head[N];
int idx,e[N],ne[N];
void insert(int x)
{
    int k=(x % N + N) % N;
    e[idx]=x;
    ne[idx]=head[k];
    head[k]=idx++;
}
int query(int x)
{
    int k=(x % N + N) % N;
    for(int i=head[k];i!=-1;i=ne[i])
        if(e[i]==x)return 1;
    return 0; 
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(head,-1,sizeof head);
    while(n--)
    {
        char c[2];
        int x;
        scanf("%s%d",c,&x);
        if(c[0]=='I')
        {
            insert(x);
        }
        else if(c[0]=='Q')
        {
            int f=query(x);
            if(f)printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}



zhaoly
29天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int x;
void solve(int x)
{
    int c=0;
    while(x>0)
    {
        x-=x&(-x);
        c++ ;
    }
    printf("%d ",c);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        solve(x);
    }

    return 0;
} 


活动打卡代码 AcWing 797. 差分

zhaoly
29天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a[N],s[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=a[i]-a[i-1];
    }
    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        s[l]+=c;
        s[r+1]-=c;
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+s[i];
        printf("%d ",a[i]);
    }
    return 0;
} 


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

zhaoly
29天前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,a[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]=a[i-1]+a[i];
    }

    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",a[r]-a[l-1]);
    }
    return 0;
} 


活动打卡代码 AcWing 789. 数的范围

zhaoly
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,q,k;
int a[N];
int main() {
    scanf("%d%d",&n,&q);
    for(int i=0; i<n; i++)scanf("%d",&a[i]);
    for(int i=0; i<q; i++) {
        scanf("%d",&k);
        int l=0,r=n-1,mid;
        while(l<r) { //k小了往前找
            mid=l+r>>1;
            if(a[mid]>=k)r=mid;
            else l=mid+1;
        }
        if(k!=a[l])cout<<"-1 -1"<<endl;
        else {
            cout<<l<<' ';
            int l=0,r=n-1,mid;
            while(l<r) { //k大了往后找
                mid=(l+r+1)/2;
                if(a[mid]<=k) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }

    return 0;
}



zhaoly
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N=100010; 
int p[N],Size[N];
int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        Size[i]=1;
    } 
    int a,b;
    string op;
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
            {
                Size[find(b)]+=Size[find(a)];
                p[find(a)]=find(b);
            }
        }else if(op=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b))printf("Yes\n");
            else printf("No\n"); 
        }
        else if(op=="Q2")
        {
            cin>>a;
            printf("%d\n",Size[find(a)]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 836. 合并集合

zhaoly
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int p[N];//表示节点i所在的父亲节点是p[i] 

int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}

int query(int a,int b)
{
    if(find(a)==find(b))return 1;
    else return 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)p[i]=i;
    int a,b;
    char op[2];
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')
        {
            if(find(a)!=find(b))p[find(a)]=find(b); 
        }
        else if(op[0]=='Q')
        {
            if(query(a,b)) printf("Yes\n");
            else printf("No\n");
        }    
    }
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

zhaoly
1个月前
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int q[N];//存储的是下标 
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-k+1 )hh++;//保证队首元素的下标在队列中,队首元素出队 
        while(hh<=tt && a[q[tt]]>=a[i])tt--;
        //for(int j=hh;j<=tt;j++)cout<<a[q[j]]<<' ';
        //cout<<endl;
        q[++tt]=i;
        if(i>k-1)printf("%d ",a[q[hh]]);
    }
    printf("\n");
    tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-k+1)hh++;
        while(hh<=tt && a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i>k-1)printf("%d ",a[q[hh]]);
    }
    return 0;
}