头像

Cc天使树cC




离线:21天前


活动打卡代码 AcWing 794. 高精度除法

#include <bits/stdc++.h>
using namespace std;

vector<int> div(vector<int> &A, int b, int &r){
    int t=0;
    vector<int> C;
    for (int i=A.size()-1;i>=0;i--){
        C.push_back((t*10+A[i])/b);
        t=(t*10+A[i])%b;
    }
    r=t;
    reverse(C.begin(),C.end());
    while (C.size()>1 && C.back()==0) C.pop_back();
    return C;
}


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


活动打卡代码 AcWing 793. 高精度乘法

#include <bits/stdc++.h>

using namespace std;

vector<int> multiply(vector<int>&A,int b){
    int t=0;
    vector<int> C;
    for (int i=0;i<A.size()||t;i++){
        if (i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t=t/10;
    }
    if (t) C.push_back(t);
    while (C.size()>1 && C.back()==0) C.pop_back();
    return C;
}



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


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

#include <bits/stdc++.h>
using namespace std;

bool compare(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-=B[i];
        C.push_back((t+10)%10);
        if (t<0) t=1;
        else t=0;
    }
    while (C.size()>1 && C.back()==0) C.pop_back();
    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');
    vector<int> C;
    if (compare(A,B)) {C= sub(A,B);}
    else {C=sub(B,A);}
    if (compare(A,B)==false) cout<<"-";
    for (int i=C.size()-1;i>=0;i--) cout<<C[i];
    return 0;
}


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

#include <bits/stdc++.h>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t =0;
    for (int i=0;i< max(A.size(),B.size());i++){
        if (i<A.size()) t+=A[i];
        if (i<B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if (t) C.push_back(1);
    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];
    return 0;
}


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

#include <bits/stdc++.h>

using namespace std;

int main(){
    double n;
    cin >>n;
    double l=0,r=abs(n)+1;
    const double eps=1e-7;
    while (r-l > eps){
        double mid = (l+r)/2;
        if (mid * mid * mid >= abs(n)) r=mid;
        else l=mid;
    }
    if (n>=0) printf("%.6lf\n",l);
    else printf("%.6lf\n",-l);
    return 0;

}


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

不需要写另外的function了

#include <bits/stdc++.h>

using namespace std;


int a[100000];


int main(){
    int n,q;
    cin >>n>>q;
    for (int i=0;i<n;i++) cin>>a[i];
    while (q--){
        int k;
        cin >> k;
        int l=0, r=n-1;
        while (l<r){
            int mid = l+r >>1;
            if (a[mid] >= k) r=mid;
            else l=mid+1;
        }
        if (a[l]!=k) cout <<"-1 -1"<<endl;
        else{
            cout <<l<<' ';
            int l=0,r=n-1;
            while (l<r){
                int mid =l + r +1 >>1;
                if (a[mid]<=k) l=mid;
                else r=mid-1;
            }
            cout <<l<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

#include <bits/stdc++.h>
using namespace std;

const int N=100000;
int q[N];
int tmp[N];

long long mergesort(int q[],int l,int r){
    if (l>=r) return 0;
    int k=0;
    int mid = (l +r) >>1;
    int i=l;int j=mid+1;
    long long count;
    count =mergesort(q,l,mid)+mergesort(q,mid+1,r);
    while (i<=mid && j<=r){
        if (q[i]<=q[j]) tmp[k++]=q[i++];
        else {
            tmp[k++]=q[j++];
            count += mid -i +1;
        }
    }
    while (i<=mid) tmp[k++]=q[i++];
    while (j<=r) tmp[k++]=q[j++];
    for (int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

    return count;
}

int main(){
    int n;
    cin >>n;
    for (int i=0;i<n;i++) scanf("%d",&q[i]);
    cout << mergesort(q,0,n-1);
    return 0;
}


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

#include <bits/stdc++.h>

using namespace std;

const int N=100010;
int q[N];
int temp[N];

void mergesort(int q[],int l,int r){
    if (l>=r) return;
    int mid= l+r >> 1;
    mergesort(q,l,mid);
    mergesort(q,mid+1,r);
    int k=0; 
    int i=l,j=mid+1;
    while (i<=mid && j<=r){
        if (q[i]<=q[j]) temp[k++]=q[i++];
        else temp[k++]=q[j++];
    }
    while (i<=mid) temp[k++]=q[i++];
    while (j<=r) temp[k++]=q[j++];

    for (int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
}



int main(){
    int n;
    cin >>n;
    for (int i=0;i<n;i++) scanf("%d",&q[i]);
    mergesort(q,0,n-1);
    for (int i=0;i<n;i++) printf("%d ",q[i]);
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

#include <bits/stdc++.h>

using namespace std;

const int N = 100000;
int q[N];

void quicksort(int q[], int l, int r){
    if (l>=r) return;
    int x=q[(l+r)/2], i=l-1,j=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]);
    }
    quicksort(q,l,j);
    quicksort(q,j+1,r);
}

int main(){
    int n;
    scanf("%d",&n);
    int k;
    scanf("%d",&k);
    for (int i=0;i<n;i++) scanf("%d",&q[i]);
    quicksort(q,0,n-1);
    cout << q[k-1];
    return 0;
}


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

新的区间是 l-i 还是l-j 会影响取值x,因为会有边界问题 记住现在这个模板就行

#include <bits/stdc++.h>

using namespace std;

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


void quicksort(int q[],int l,int r){
    if (l>=r) return;
    int x=q[(l+r)/2];
    int i=l-1;
    int j=r+1;
    while (i<j){
        do i++; while (q[i]<x);  //while(q[++i]<x); 更简洁
        do j--; while (q[j]>x);
        if (i<j) swap(q[i],q[j]);
    }
    quicksort(q,l,j);
    quicksort(q,j+1,r);
}

int main(){
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%d", &q[i]);
    quicksort(q,0,n-1);
    for (int i=0;i<n;i++) printf("%d ",q[i]);
    return 0;
}