头像

zero666




离线:2小时前


活动打卡代码 AcWing 827. 双链表

zero666
4小时前
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
int m;
void init()
{
    r[0]=1,l[1]=0,idx=2;
}
void add(int k,int x)//k的右边差一个数x 
{
    e[idx]=x,l[idx]=k,r[idx]=r[k],l[r[k]]=idx,r[k]=idx++;
}
void remove(int k)
{
    l[r[k]]=l[k];
    r[l[k]]=r[k];
}
int main(void)
{
    cin>>m;
    init();
    while(m--)
    {
        string op; cin>>op;
        if(op=="L")  
        {
            int x; cin>>x;
            add(0,x);
        }
        if(op=="R")
        {
            int x; cin>>x;
            add(l[1],x);
        }
        if(op=="D")
        {
            int x; cin>>x;
            remove(x+1);
        }
        if(op=="IL")
        {
            int k,x; cin>>k>>x;
            add(l[k+1],x);
        }
        if(op=="IR")
        {
            int k,x; cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
    return 0;
}



zero666
9小时前
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N],s[N];
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main(void)
{
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i,s[i]=1;
    while(m--)
    {
        string op; cin>>op;
        if(op=="C")
        {
            int a,b; cin>>a>>b;
            if(find(a)==find(b)) continue;
            s[find(b)]+=s[find(a)];
            p[find(a)]=find(b);
        }
        if(op=="Q1")
        {
            int a,b; cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        if(op=="Q2")
        {
            int a; cin>>a;
            cout<<s[find(a)]<<endl;
        }
    }
    return 0;
}


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

zero666
9小时前
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int p[N];
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main(void)
{
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        string op; int a,b;
        cin>>op>>a>>b;
        if(op=="M") p[find(a)]=find(b);
        else
        if(find(a)==find(b)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


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

zero666
9小时前
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N];
int find(int x)//返回x的祖宗结点 + 路径压缩 
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main(void)
{
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        string op; int a,b;
        cin>>op>>a>>b;
        if(op=="M") p[find(a)]=find(b);
        else 
        if(find(a)==find(b)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

zero666
9小时前
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int q[N],hh=0,tt=-1;
int x,m;
int main(void)
{
    cin>>m;
    while(m--)
    {
        string op; cin>>op;
        if(op=="push") cin>>x,q[++tt]=x;
        if(op=="pop") hh++;
        if(op=="empty")
        {
            if(hh<=tt) cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        if(op=="query") cout<<q[hh]<<endl;
    }
}


活动打卡代码 AcWing 828. 模拟栈

zero666
9小时前
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int s[N],tt;
int main(void)
{
    int m; cin>>m;
    while(m--)
    {
        string op; cin>>op;
        if(op=="push")
        {
            int x; cin>>x;
            s[++tt]=x;
        }
        if(op=="pop")
        {
            tt--; 
        }
        if(op=="empty")
        {
            if(tt==0) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        if(op=="query") cout<<s[tt]<<endl;
    }
    return 0;
}


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

zero666
10小时前
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int head,e[N],ne[N],idx;
int n;
void init()
{
    head=-1;
    idx=1;
}
void to_add(int k,int x)
{
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void add(int x)
{
    e[idx]=x,ne[idx]=head,head=idx++;
}
void remove(int k) 
{
    ne[k]=ne[ne[k]];
} 
int main(void)
{
    cin>>n;
    init();
    while(n--)
    {
        string op; cin>>op; 
        if(op=="H") 
        {
            int x; cin>>x;
            add(x);
        }
        if(op=="D")
        {
            int k; cin>>k;
            if(k) remove(k);
            else head=ne[head];
        }
        if(op=="I")
        {
            int k,x; cin>>k>>x;
            to_add(k,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
    {
        cout<<e[i]<<" ";
    }
    return 0;
}


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

zero666
10小时前
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
const int N = 300010;
int a[N], s[N];
int n, m;

vector<int> alls;//坐标
vector<PII> add, query;//  add保存的原来的,query保存的是查找的区间的下标

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;
}
vector<int>:: iterator unique(vector<int> &a)
{
    int j = 0;
    for(int i = 0; i < a.size(); i ++)
        if(!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    return a.begin() + j;
}

int main()
{

    cin >> n >> m;

    for(int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});//保存真实的坐标和数值

        alls.push_back(x);//保存映射的坐标
    }

    for(int i = 0; i < m; i ++ )
    {
        int l, r;
        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)
    {
        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)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}



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

zero666
10小时前
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main(void)
{
    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,j;
    for(i=0,j=0;i<m;i++)
    {
        if(a[j]==b[i]) j++;
    }
    if(j==n) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}



zero666
11小时前
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n,m,x;
int main(void)
{
    cin>>n>>m>>x;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int j=0;j<m;j++) cin>>b[j];

    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;
    }
    return 0;
}