头像

empathy117




离线:7小时前


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

#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) {
    int t = 0;
    vector<int> c;
    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;
    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');
    vector<int> C;

    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

    for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
}


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

#include <iostream>
#include <vector>
using namespace std;

vector<int> bplus(vector<int> &a, vector<int> &b) {
    if (a.size() < b.size()) return bplus(b, a);

    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); ++i) {
        t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}
int main() {
    string sa, sb;
    cin >> sa >> sb;
    vector<int> a, b;
    for (int i = sa.size() - 1; i >= 0; --i) a.push_back(sa[i] - '0'); // --i
    for (int i = sb.size() - 1; i >= 0; --i) b.push_back(sb[i] - '0'); // --i
    vector<int> c = bplus(a, b);
    for (int i = c.size() - 1; i >= 0; --i) printf("%d", c[i]); // --i
}


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

#include <iostream>
#include <vector>
using namespace std;

vector<int> bplus(vector<int> &a, vector<int> &b) {
    if (a.size() < b.size()) return bplus(b, a);

    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); ++i) {
        t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}
int main() {
    string sa, sb;
    cin >> sa >> sb;
    vector<int> a, b;
    for (int i = sa.size() - 1; i >= 0; --i) a.push_back(sa[i] - '0'); // --i
    for (int i = sb.size() - 1; i >= 0; --i) b.push_back(sb[i] - '0'); // --i
    vector<int> c = bplus(a, b);
    for (int i = c.size() - 1; i >= 0; --i) printf("%d", c[i]); // --i
}


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

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5+10;
int q[N], tmp[N];

long long ms(int l, int r) {
    if (l >= r) return 0; // 忘了写返回条件
    long long ans = 0;
    int mid = (l + r) >> 1;
    ans += ms(l, mid) + ms(mid + 1, r); // l, mid  mid+1, r
    int i = l, j = mid + 1, k = 0; // i = l, j = mid + 1
    while (i <= mid && j <= r) { // i <= mid, j <= r
        if (q[i] <= q[j]) tmp[k++] = q[i++]; // 别写倒了
        else {
            tmp[k++] = q[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = q[i++]; // tmp = 
    while (j <= r) tmp[k++] = q[j++]; // tmp = 

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

    return ans;
}

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


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

#include <iostream>
using namespace std;

int main() {
    double n;
    cin >> n;
    double l = -10000 , r= 10000;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%lf", l);
}


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

#include <cstdio>
using namespace std;
const int mN = 1e5+10;
int q[mN];
int main() {
    int n, m, k;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", &q[i]);
    while (m--) {
        scanf("%d", &k);
        int l = 0, r = n -1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (q[l] != k) printf("-1 -1\n");
        else {
            printf("%d", l);
            int l = 0, r = n -1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf(" %d\n", l);
        }
    }
}


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

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


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

int nthElement(int l, int r, int k) {
    if (l == r) return(q[l]);

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


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

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxN = 100010;
int q[maxN];

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) {
        while (q[++i] < x);
        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() {
    int n;
    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《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/10374/