头像

yzc971022


访客:1337

离线:1个月前


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

yzc971022
3个月前
//这里填你的代码^^
#include<iostream>
#include<cstring>
using namespace std;
const int N=200003,null=0x3f3f3f3f;   //null的实际大小为一个大于10^9的一个数,用于判断h数组是否被填入数;
int h[N];


int find(int x){        //find函数用于找到x填入h数组中的位置
    int t=(x%N+N)%N;
    while(h[t] != null && h[t] != x){
        t++;
        if(t==N) t=0;   //如果t走到头了,就返回重新走一遍

    }
    return t;


}



int main(){
    memset(h,0x3f,sizeof h);    //memset是按字节填入的,int类型共有4个字节,故每个位置填入4个0x3f,表示刚开始每个位置都
                                                                //没有数字填入
    int n;
    scanf("%d",&n);

    while(n--){
        char op[2];
        int x;
        //cin >> op >> x;
        scanf("%s%d",&op,&x);
        if(op[0]=='I') h[find(x)]=x;
        else{
            if(h[find(x)]==null) puts("No");
            else puts("Yes");
        }


    }




}


//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 785. 快速排序

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
using namespace std;

int n;
const int N=1e6+10;
int q[N];


void quick_sort(int q[],int l, int r){

    if(l>=r) return;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j){
        do(i++); while(q[i]<x);
        do(j--); while(q[j]>x);
        if(i<j) swap(q[i],q[j]);

    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);

}






int main(){

    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",q[i]);

}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 797. 差分

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
using namespace std;

const int N=101000;
int a[N],b[N];

void insert(int l,int r,int c){
    b[l]=b[l]+c;
    b[r+1]=b[r+1]-c;
}


int main(){
    int n,m;
    cin >> n>> m;
    for(int i=1;i<=n;i++) cin >> a[i];   //a[i]其实只是用来记录数字的
    for(int i=1;i<=n;i++) insert(i,i,a[i]);  //这个操作用于先构造出差分数组
    while(m--){
        int l,r,c;
        cin >> l >> r >> c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++) b[i]=b[i]+b[i-1];
    for(int i=1;i<=n;i++) cout << b[i] <<' ';


}





//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
using namespace std;

const int N=1010;
int s[N][N],a[N][N]; //这里用两个数组来存,一个表示原数组,一个表示前缀和


int main(){
    int n,m,q;   //n表示行,m表示列,q表示查询次数
    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]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1] << endl;


    }

}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
using namespace std;

const int N=1e5+10;

int a[N],s[N];


int main(){

    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >>a[i];
    s[0]=0;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

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

    }

}

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 792. 高精度减法

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
#include<vector>
using namespace std;

bool cmp(vector<int>&A,vector<int>&B){
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--){
        if(A[i]!=B[i]) 
            return A[i]>B[i];
    }
    return true;
}



vector<int> sub(vector<int> & A,vector<int> & B){
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++){
        t=A[i]-t;
        if(i<B.size()) t=t-B[i];
        C.push_back((t+10)%10);   //这里的(t+10)%10相当于直接把t>=0和t<0的情况全说清楚了
        if(t<0) t=1;
        else t=0;

    }
    while(C.size()>1 && C.back()== 0) C.pop_back();  //去除前导0
    return C;

}


int main(){

    string a,b;
    vector<int>A,B,C;
    cin >> a >> b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    if(cmp(A,B)) C=sub(A,B);
    else{
        C=sub(B,A);
        cout<<'-';
    }
    //cout << C[2] << endl;
    for(int i=C.size()-1;i>=0;i--) cout << C[i];


}







//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 791. 高精度加法

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
#include<vector>
using namespace std;


vector<int> add(vector<int> &A, vector<int> &B){
    //第一个传入的变量长度要保证比第二个传入的变量长度要长;

    if(A.size()<B.size()) return add(B,A);
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++){
        t=t+A[i];
        if(i<B.size()) t=t+B[i];
        C.push_back(t%10);
        t=t/10;
    }
    if(t) C.push_back(t);
    return C;
}









int main(){
    string a,b;
    vector<int> A,B;
    cin >> a >> b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--) cout << C[i];


}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 790. 数的三次方根

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
using namespace std;

int const N=1e6+10;

int main(){

    double x;
    scanf("%lf",&x);
    int flag=0;
    if(x>=0){
        double l=0,r=x;
        while((r-l)>1e-8){
            double mid=(l+r)/2;
            if(mid>=x/(mid*mid)) r=mid;
            else l=mid;
        }
        printf("%lf",l);
    }
    else{
        double l=x,r=0;
        while((r-l)>1e-8){
            double mid=(l+r)/2;
            if(mid*mid*mid>=x) r=mid;
            else l=mid;
        }
        printf("%.6lf",l);

    }






}

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

yzc971022
5个月前
//这里填你的代码^^
#include<iostream>
using namespace std;

const int N=1e6+10;

int q[N],z[N];

int main(){
    int m,n;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    for(int i=0;i<m;i++){
        int l=0,r=n-1;
        int x;
        scanf("%d",&x);
        while(l<r){
            int mid=l+r>>1;
            if(q[mid]>=x) r=mid;
            else l=mid+1;
        }
        if(q[l]!=x) printf("-1 -1\n");
        else{

            int l1=0,r1=n-1;
            while(l1<r1){
                int mid1=l1+r1+1>>1;
                if(q[mid1]<=x) l1=mid1;
                else r1=mid1-1;
            }
            printf("%d %d\n",l,l1);
        }
    }

    return 0;


}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 787. 归并排序

yzc971022
5个月前
//这里填你的代码^^
#include <iostream>
using namespace std;

const int N=1e6+10;

int n;
int a[N],tmp[N];

void merge_sort(int q[],int l,int r){
    if(l>=r) return;

    int mid=l+r>>1;
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);  //先进行二分

    int k=0,i=l,j=mid+1;    //k是用于tmp数组的指针,i是用于左边排好序的数组的指针,j是用于右边排好序的指针。
    while(i<=mid && j<=r){
        /*if(q[i]<=q[j]){
            tmp[k]=q[i];
            k=k+1;
            i=i+1;
        }
        else{
            tmp[k]=q[j];
            k=k+1;
            j=j+1;
        }
        */
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while(i<=mid) tmp[k++]=q[i++]; //从上面的while语句到这句,说明j<=r已经不满足,即j已经走到右边数组的头了,故只要把左边数组剩下的部分全部拿到q里去即可。
    while(j<=r) tmp[k++]=q[j++]; //从上面的while语句到这句,说明i<=mid已经不满足,即i已经走到左边数组的头了,故只要把右边数组剩下的部分全部拿到q里去即可。
    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j]; //把当前正在排序的数组q(长度是i~r)里的每个元素用排好序的tmp重新赋值
}






int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    merge_sort(a,0,n-1);

    for(int i=0;i<n;i++) printf("%d ",a[i]);

    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~