头像

范特西西




离线:6小时前


最近来访(17)
用户头像
LHHDHR
用户头像
嗨呀不是我
用户头像
小哈皮
用户头像
nmj
用户头像
KANO_菓
用户头像
无人圣地
用户头像
zjyyc07

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

范特西西
6小时前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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;
    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1;i >= 0; i --)A.push_back(a[i] - '0');

    int r;
    vector<int> C = div(A,b,r);

    for (int i = C.size() - 1; i >= 0; i --)printf("%d", C[i]);
    cout << endl << r;

    return 0;
}


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

范特西西
7小时前
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++)
    {
        if (i < A.size())t += A[i] * b;
        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;
    vector<int> A;

    cin >> a >> b;
    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;
}


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

范特西西
17小时前
#include <iostream>
#include <vector>

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;

    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');

    if(cmp(A, B) == true)
    {
        vector<int> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i --)printf("%d",C[i]);
    }
    else
    {
        vector<int> C = sub(B, A);

        printf("-");

        for (int i = C.size() - 1; i >= 0; i --)printf("%d",C[i]);
    }

    return 0;
}


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

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

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');

    vector<int> C = add(A,B);

    for (int i = C.size() - 1; i >= 0; i --)printf("%d",C[i]);

    return 0;
}


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

希望有朝一日我可以和罗少五五开

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

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

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = 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 ++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];

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

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

    cout << merge_sort(q, 0, n - 1) << endl;

    return 0;
}


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

归并排序

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[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;

    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 (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;
}


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

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n,k;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r)return ;
    int x = q[l + r >> 1], 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 %d",&n, &k);
    for (int i = 0; i < n; i ++)scanf("%d",&q[i]);

    quick_sort(q, 0, n - 1);

    printf("%d", q[k - 1]);

    return 0;
}


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

快排算法板子

#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 >> 1], 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;
}


活动打卡代码 AcWing 823. 排列

究极函数递归

#include <iostream>

using namespace std;

const int N = 10;
int n;
int q[N];
bool st[N];

void f(int u)
{
    if(u == n)
    {
        for (int i = 0; i < n; i ++)
        {
            cout << q[i] << " ";
        }

        cout  << endl;
        return;
    }
    else
    {
        for (int i = 1;i <= n; i ++)
        {
            if(!st[i])
            {
                q[u] = i;
                st[i] = true;
                f(u + 1);
                st[i] = false;
            }
        }
        return;
    }
}
int main ()
{
    cin >> n;
    f(0);

    return 0;
}


活动打卡代码 AcWing 822. 走方格

十一月九日第五题函数递归

#include <iostream>

using namespace std;

int ans;
int n,m;
void f(int x,int y)
{
    if(x == n && y == m)
    {
        ans ++;
        return;
    }
    if(x < n) f(x + 1,y);
    if(y < m) f(x, y + 1);
}
int main ()
{
    cin >> n >> m;
    f(0,0);
    cout  << ans << endl;

    return 0;
}