保研机试训练Day-01

#include<iostream>
using namespace std;

const int N=1e6+10;
int n;
int q[N];
void quick_sort(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]);
    }
    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]);
    }
    return 0;
}

#include<iostream>
using namespace std;
const int N=1e6+10;
int n,q[N],tmp[N];
void merge_sort(int q[],int l,int r){
    if(l>=r) return;
    int mid = (l+r)/2;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]){
            tmp[k++]=q[i++];
        }
        else tmp[k++]=q[j++];
    }
    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];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}

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

const int N = 1e6 + 10;

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

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

const int N = 1e6+10;

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;
	for(int i=0,t=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;
	cin >> a >> b;
	vector<int> 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)){
		vector<int> C = sub(A,B);
		for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
	}
	else{
		printf("-");
		vector<int> C = sub(B,A);
		for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector <int> mul(vector <int> A,int b){
    vector <int> C;
    int t=0;
    for(int i = 0 ; i < A.size() ; i++){
        t += A[i] * b;
        C.push_back(t%10);
        t/=10;
    }
    while(t){
        C.push_back(t%10);
        t/=10;
    }
    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');
    auto C = mul(A,b);
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
  
    return 0;
}

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

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

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