头像

rainchen

ETO-Earth Trisolaris Organization地球三体组织、SCP基金会




离线:6小时前


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

rainchen
7小时前
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,ans,f[N],t[32*N][2],idx;
int get(int x,int k){
    return (x>>(31-k))&1;
}
void ins(int x){
    int p=0;
    for(int i=1; i<=31; i++){
        int u=get(x,i);
        if(!t[p][u]) t[p][u]=++idx;
        p=t[p][u];
    }
}
int que(int x){
    int p=0,res=0;
    for(int i=1; i<=31; i++){
        int u=get(x,i);
        if(t[p][!u]){
            p=t[p][!u];
            res=res*2+!u;
        }
        else{
            p=t[p][u];
            res=res*2+u;
        }
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>f[i];
        ins(f[i]);
        int x=que(f[i]);
        ans=max(ans,x^f[i]);
    }
    cout<<ans;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 125. 耍杂技的牛

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> &a,pair<int,int> &b){
    return a.second-b.first<b.second-a.first; }
int main(){
    int n,f[50005]={},ans=0;
    pair<int,int> ws[50005];
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>ws[i].first>>ws[i].second;
    sort(ws,ws+n,cmp);
    for(int i=0; i<n; i++) f[i]=f[max(i-1,0)]+ws[i].first;
    ans=-ws[0].second;
    for(int i=0; i<n-1; i++) ans=max(ans,f[i]-ws[i+1].second);
    cout<<ans;
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int N=1000005,P=131;
typedef unsigned long long ull;
int n,m;
string son,s;
ull h[N],p[N]={1},hson;
ull gota(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    cin>>n>>son>>m>>s;
    for(int i=1; i<=n; i++){
        hson=hson*P+son[i-1];
    }
    for(int i=1; i<=m; i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i-1];
    }
    for(int i=1; i<=m; i++){
        if(i+son.size()-1<=m&&gota(i,i+son.size()-1)==hson)
            cout<<i-1<<' ';
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int N=100005,P=131;
typedef unsigned long long ull;
int n,m;
string s;
ull h[N],p[N]={1};
ull gota(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    cin>>n>>m>>s;
    for(int i=1; i<=n; i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i-1];
    }
    while(m--){
        int la,lb,ra,rb;
        cin>>la>>ra>>lb>>rb;
        if(gota(la,ra)==gota(lb,rb)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

#include<bits/stdc++.h>
using namespace std;
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x){
    int k=(x%N+N)%N;
    while(h[k]!=null&&h[k]!=x){
        k++;
        if(k==N) k=0;
    }
    return k;
}
int main(){
    int n;
    cin>>n;
    memset(h,0x3f,sizeof h);
    while(n--){
        string op;
        int x;
        cin>>op>>x;
        int k=find(x);
        if(op=="I") h[k]=x;
        else{
            if(h[k]!=null) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 839. 模拟堆

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int h[N],hp[N],ph[N],hsize;
void hswap(int a,int b){
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
void up(int k){
    while(k>1&&h[k/2]>h[k]){
        hswap(k/2,k);
        k/=2;
    }
}
void down(int k){
    int u=k;
    if(k*2<=hsize&&h[k*2]<h[u]) u=k*2;
    if(k*2+1<=hsize&&h[k*2+1]<h[u]) u=k*2+1;
    if(u!=k){
        hswap(u,k);
        down(u);
    }
}
int main(){
    int n,m=0;
    cin>>n;
    for(int i=1; i<=n; i++){
        int k,x;
        string op;
        cin>>op;
        if(op=="I"){
            cin>>x;
            hsize++,m++;
            ph[m]=hsize,hp[hsize]=m;
            h[hsize]=x;
            up(hsize);
        }
        else if(op=="PM") cout<<h[1]<<endl;
        else if(op=="DM"){
            hswap(1,hsize);
            hsize--;
            down(1);
        }
        else if(op=="D"){
            cin>>k;
            k=ph[k];
            hswap(k,hsize);
            hsize--;
            down(k); up(k);
        }
        else{
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            down(k); up(k);
        }
    }
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 838. 堆排序

rainchen
14天前
#include<bits/stdc++.h>
using namespace std;
long long t[100005];
int tsize;
void up(int k){
    while(k>1&&t[k/2]>t[k]){
        swap(t[k/2],t[k]);
        k/=2;
    }
}
void down(int k){
    int u=k;
    if(k*2<=tsize&&t[k*2]<t[u]) u=k*2;
    if(k*2+1<=tsize&&t[k*2+1]<t[u]) u=k*2+1;
    if(u!=k){
        swap(t[u],t[k]);
        down(u);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>t[i];
    tsize=n;
    for(int i=n/2; i; i--) down(i);
    for(int i=1; i<=m; i++){
        cout<<t[1]<<' ';
        t[1]=t[tsize];
        tsize--;
        down(1);
    }
    return 0;
}


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

rainchen
14天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
int son[100005][27],cnt[100005],idx;
char str[100005];
void ins(char str[]){
    int p=0;
    for(int i=0; str[i]; i++){
        int u=str[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}
int que(char str[]){
    int p=0;
    for(int i=0; str[i]; i++){
        int u=str[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    return  cnt[p];
}
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        char c;
        cin>>c>>str;
        if(c=='I') ins(str);
        else cout<<que(str)<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



rainchen
15天前

RT



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

rainchen
21天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
int n,k,q[1000005],a[1000005],hh,tt;
int main(){
    cin>>n>>k;
    hh=0,tt=-1;
    for(int i=0; i<n; i++){
        cin>>a[i];
        if(hh<=tt&&i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<' ';
    }
    cout<<endl;

    hh=0,tt=-1;
    for(int i=0; i<n; i++){
        if(hh<=tt&&i-k+1>q[hh]) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i>=k-1) cout<<a[q[hh]]<<' ';
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~