头像

wuzgnm


访客:2119

离线:17小时前


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

wuzgnm
10天前

一共有n个数,编号是1~n,最开始每个数各自在一个集合中。

现在要进行m个操作,操作共有两种:

“M a b”,将编号为a和b的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
“Q a b”,询问编号为a和b的两个数是否在同一个集合中;
输入格式
第一行输入整数n和m。

接下来m行,每行包含一个操作指令,指令为“M a b”或“Q a b”中的一种。

输出格式
对于每个询问指令”Q a b”,都要输出一个结果,如果a和b在同一集合内,则输出“Yes”,否则输出“No”。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例:

Yes
No
Yes

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,p[N],a,b;
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++)p[i]=i;
    while(m--){
        char ch;
        cin>>ch>>a>>b;
        if(ch=='M')p[find(a)]=find(b);
        else {
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

自写样例:
8 11
M 1 8
M 4 6
Q 4 5
M 4 5
Q 1 3
M 1 7
Q 5 8
M 1 3
Q 4 4
M 3 6
Q 1 8
M 3 6
Q 1 8
M 2 6
Q 3 7



活动打卡代码 AcWing 143. 最大异或对

wuzgnm
10天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a,son[30*N][2],n,idx,res;
void insert(int x){
    int p=0;
    for(int i=30; i>=0; i--){
        int u=x>>i&1;
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int x){
    int p=0,res=0;
    for(int i=30; i>=0; i--){
        int u=x>>i&1;
        if(son[p][!u]){
            res+=1<<i;
            p=son[p][!u];
        }
        else p=son[p][u];
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        scanf("%d",&a);
        insert(a);
        res=max(res,query(a));
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

wuzgnm
10天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a,son[30*N][2],n,idx,res;
void insert(int x){
    int p=0;
    for(int i=30; i>=0; i--){
        int u=x>>i&1;
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int x){
    int p=0,res=0;
    for(int i=30; i>=0; i--){
        int u=x>>i&1;
        if(son[p][!u]){
            res+=1<<i;
            p=son[p][!u];
        }
        else p=son[p][u];
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        scanf("%d",&a);
        insert(a);
        res=max(res,query(a));
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 835. Trie字符串统计

wuzgnm
14天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e4*2+10;
int idx,cnt[N],son[N][26],n;
char ch;
void insert(string str){
    int p=0;
    for(int i=0; i<str.size(); i++){
        int u=str[i]-'a';
        if(!son[p][u])son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int query(string str){
    int p=0;
    for(int i=0; i<str.size(); i++){
        int u=str[i]-'a';
        if(!son[p][u])return 0;
        p=son[p][u];
    }
    return cnt[p];
}
int main(){
    cin>>n;
    while(n--){
        string str;
        cin>>ch>>str;
        if(ch=='I')
            insert(str);
        if(ch=='Q')
            cout<<query(str)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

wuzgnm
16天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,ne[N];
char p[N],s[M];
int main(){
    cin>>n>>p+1>>m>>s+1;
    for(int i=2,j=0;i<=n; i++){
        while(j&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m; i++){
        while(j&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==n){
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}


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

wuzgnm
18天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int q[N],a[N],hh,tt=-1,n,k;
int main(){
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    for(int i=1; i<=n; i++){
        while(q[hh]>=a[i]&&hh<=tt)hh++;
        if(hh<=tt)cout<<q[hh]<<' ';
        else cout<<"-1 ";
        q[++tt]=a[i];
    }
    puts("");
    for(int i=1; i<=n; i++){
        while(q[hh]<=a[i]&&hh<=tt)hh++;
        if(hh<=tt)cout<<q[hh]<<' ';
        else cout<<"-1 ";
        q[++tt]=a[i];
    }
    puts("");
    return 0;
}


活动打卡代码 AcWing 830. 单调栈

wuzgnm
18天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int stk[N],x,tt,n;
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>x;
        while(stk[tt]>=x&&tt)tt--;
        if(tt)cout<<stk[tt]<<" ";
        else cout<<"-1 ";
        stk[++tt]=x;
    }
    return 0;
}


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

wuzgnm
18天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l[N],r[N],e[N],idx,n,x,k;
string s;
void init(){
    l[-1]=0;
    r[0]=-1;
    idx=1;
}
void insert(int k,int x){
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}
void Remove(int k){
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
int main(){
    init();
    cin>>n;
    while(n--){
        cin>>s;
        if(s=="L"){
            cin>>x;
            insert(0,x);
        }
        if(s=="R"){
            cin>>x;
            insert(l[-1],x);
        }
        if(s=="D"){
            cin>>k;
            Remove(k);
        }
        if(s=="IL"){
            cin>>k>>x;
            insert(l[k],x);
        }
        if(s=="IR"){
            cin>>k>>x;
            insert(k,x);
        }
    }
    for(int i=r[0]; ~i; i=r[i])cout<<e[i]<<' ';
    return 0;
}


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

wuzgnm
23天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,stk[N],hh,tt=-1;
int main(){
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        if(s=="push"){
            int x;
            cin>>x;
            stk[++tt]=x;
        }
        if(s=="pop")hh++;
        if(s=="query")cout<<stk[hh]<<endl;
        if(s=="empty")cout<<(hh<=tt?"NO":"YES")<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 875. 快速幂

wuzgnm
24天前
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull a,b,q,n;
ull mod(ull a,ull n,ull q){
    if(n==0)return 1;
    ull c=mod(a,n>>1,q);
    if(n%2==1)return c*c%q*a%q;
    return c*c%q;
}
int main(){
    cin>>n;
    while(n--){
        cin>>a>>b>>q;
        cout<<mod(a,b,q)<<endl;
    }
    return 0;
}