acwing算法基础课I

本文主要是介绍acwing算法基础课I，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

acwing 算法基础课I 基础算法.

排序: 快排, 归并排序, 主要思想.

模板能够默写出来

重复写3-5次

排序

快速排序: 分治

确定分界点取左边界 q[l] q[(l+r)/2] q[r]
根据x的值重新调整区间 . 左边小于等于分界点, 右边大于等于分界点
递归处理左右两遍

void qsort(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) {
        while(q[++i] < x);  // 这样就舒服多了吧.
        while(q[--j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    qsort(q, l, j);
    qsort(q, j + 1, r); //注意最后递归的边界问题.
}

归并排序:

分治...

void msort(int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    msort(l, mid), msort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (a[i] < a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    while (i <= mid) tmp[k++] = a[i++]; //这种放后面写清晰点.
    while (j <= r) tmp[k++] = a[j++];
    for (i = l, j = 0;i <= r;i++, j++) a[i] = tmp[j];
}

逆序对的数量

void msort(int l, int r) {
    if (l >= r) return;
    int k = 0;
    int mi = l + (r - l) / 2;
    msort(l, mi), msort(mi + 1, r);
    int i = l, j = mi + 1;
    while (i <= mi && j <= r) {
        if (a[i] <= a[j])tmp[k++] = a[i++];
        else tmp[k++] = a[j++], res += mi - i + 1; //只需要这里加上就行
    }
    while (i <= mi) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    rep(i, 0, k) a[i + l] = tmp[i];
}
int main() {
    int n = read();
    rep(i, 0, n) a[i] = read();
    msort(0, n - 1);
    da(a, n);
    printf("%llu", res);
    return 0;
}

二分

整数二分

acwing解法

右半边满足 : 比如 x <= a[mi]
1. r = mid, l = mid - 1
2. mi = l + r >> 1
左半边满足: 比如 x <= a[mi]
1. l = mid, r = mid +1

// 二分就是最左和最右的问题, 只有两个地方不一样.
//左边界
int lo = 0, hi = n - 1;
while (lo <= hi) { //注意一定是<=
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < target) lo = mid + 1;
    else if (target < a[mid]) hi = mid - 1;
    else if (a[mid] == target) hi = mid - 1; // 1.
}
return lo; // 2.
//右边界
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < target) lo = mid + 1;
    else if (target < a[mid]) hi = mid - 1;
    else if (a[mid] == target) lo = mid + 1; // 1.
}
return hi; // 2.

35. Search Insert Position

这个题是寻找符合c++ 规范的那个位置

int searchInsert(vector<int>& nums, int a) {
    // 这个题应该是找右边的最左边j.
    int l = 0, r = nums.size(); // 注意这里是可以取到 nums.size()的, 所以直接这样.
                        //不过这样居然不会出现问题...
    while(l < r){
        int mi = l + r >> 1; 
        if(nums[mi] >= a) r = mi;
        else l = mi + 1;
    }
    return l; 
}

275. H-Index II

这种右边边界插入的和定义相同的题, 直接让 r = n 才能过

int hIndex(vector<int>& a) {
    int n = a.size();
    int l = 0, r = n;
    while(l < r){
        int mi = l + r >> 1; 
        if(a[mi] >= n - mi) r = mi;
        else l = mi + 1;
    } 
    return n - l;
}

162. Find Peak Element

一个倒过来 V 的数组寻找最高点. 利用两边的性质就好.

int findPeakElement(vector<int>& a) {
    int n = a.size();
    int l = 0, r = n - 1;
    while(l < r){
        int mi = (l + r) >> 1;  
        if(mi + 1< n && a[mi] > a[mi + 1]) r = mi;
        else l = mi + 1;
    }
    return l;
}

高精度

大整数的存储. 逆序的.

加法

vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> res;
    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];
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(t);
    return res;
}

减法 ★★★

减法的判断要麻烦一些.

string s, ss;
vector<int> a, b;
vector<int> sub(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int t = 0;
    rep(i, 0, a.size()) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t + 10) % 10);
        t = t < 0 ? 1 : 0;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back(); //去除前导0
    return c;
}
int main() {
    cin >> s >> ss;
    per(i, s.size(), 0) a.push_back(s[i] - '0');
    per(i, ss.size(), 0) b.push_back(ss[i] - '0');
    bool gre = false;
    if (a.size() < b.size()) gre = true;
    else if (a.size() == b.size()) {
        per(i, a.size(), 0) if (a[i] != b[i]) { gre = a[i] < b[i];break; }
    }
    if (gre) swap(a, b), printf("-");
    auto c = sub(a, b);
    per(i, c.size(), 0) printf("%d", c[i]);
    return 0;
}

乘法 ★

vector<int> mul(vector<int>& A, int b) {
    if (b == 0) return { 0 };
    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;
    }
    return C;
}

除法 ★

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

前缀和 & 差分

前缀和

Q: 下标从 0 还是 1 开始? 从 1 开始.

求[l,r]的话, 直接求 \(S_r-S_{l-1}\)

int main() {
    int n = read(), q = read(), l, r;
    rep(i, 1, n + 1) a[i] = read();
    rep(i, 1, n + 1) s[i] += a[i] + s[i - 1];
    while (q--) {
        l = read(), r = read();
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

矩阵前缀和

Q: 从 1 还是 0 开始: 1 开始.

int a[N3][N3], s[N3][N3];
int main() {
    int n = read(), m = read(), q = read();
    rep(i, 1, n + 1) rep(j, 1, m + 1) a[i][j] = read();
    rep(i, 1, n + 1) rep(j, 1, m + 1) {
        s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //前缀和
    }
    da2(s, n + 1, m + 1);
    while (q--) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << endl; // 求子数组的和.
    }
    return 0;
}

差分 ★★

一个数组实现差分

// 如何通过单个数组做出来这个差分? 
int s[N6];
void  insert(int l, int r, int c) {
    s[l] += c;
    s[r + 1] -= c;
}
int main() {
    int n = read(), q = read();
    rep(i, 1, n + 1) { insert(i, i, read()); }
    da(s, n + 1);
    while (q--) {
        int l = read(), r = read(), c = read();
        insert(l, r, c);
        da(s, n + 1);
    }
    rep(i, 1, n + 1) s[i] += s[i - 1], O(s[i]);

    return 0;
}

差分矩阵 ★★

差分矩阵如何构造和实现.

int s[N3][N3];
void  insert(int x1, int y1, int x2, int y2, int c) {
    s[x1][y1] += c;
    s[x2 + 1][y1] -= c;
    s[x1][y2 + 1] -= c;
    s[x2 + 1][y2 + 1] += c;
}
int main() {
    int n = read(), m = read(), q = read();
    rep(i, 1, n + 1)rep(j, 1, m + 1) insert(i, j, i, j, read());
    while (q--) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read(), c = read();
        insert(x1, y1, x2, y2, c);
    }
    rep(i, 1, n + 1) {
        rep(j, 1, m + 1)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1], O(s[i][j]);
        puts("");
    }

    return 0;
}

双指针

通用模板

for(int i = 0, j = 0; i < n; i++){
    while(j < i && check(i, j)) j++; //进行判断 缩短区间的长度.
    //题目的逻辑
}

核心思想是将两重循环优化到O(n)去.

双指针输出每个字符

//双指针输出每个字符; 
// 其实和前面有点不一样了, 因为循环中改变i了
int main() {
    char str[1000];
    cin.getline(str, 1000);
    int n = strlen(str);
    for (int i = 0; i < n;i++) {
        int j = i;
        while (j < n && str[j] != ' ') j++;
        rep(k, i, j) cout << str[k];
        cout << endl;
        i = j; // i 等于当前的空格, 便于下一次++以后跳过这个空格
    }
    return 0;
}

799. 最长连续不重复子序列

int a[N5], b[N5];
int main() {
    int n = read();
    rep(i, 0, n) {
        a[i] = read();
    }
    int res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        b[a[i]]++;
        while (j < i && b[a[i]] > 1) b[a[j++]]--; //进行判断 缩短区间的长度.
        res = max(res, i - j + 1);
    }
    O(res);
    return 0;
}

位运算常用操作:

返回第n位数字: a >> n & 1;

返回最后一位 lowbit(n) = n & -n ;

补码的来源:
-x = 0 - x = 000000 - x =1000000 - x = ~x + 1

// 二进制中1的个数.
int main() {
    int n = read();
    rep(i, 0, n) {
        int a = read();
        int cnt = 0;
        while (a)  cnt++, a -= a & -a;
        O(cnt);
    }
    return 0;
}

整数离散化

区间和 ★★★

Q: 无限长数轴, 其中 n 个位置数是C, 询问 [l, r] 之间所有数的和

如果有\(10^5\)个数字, 但是值在\(10^9\)之间. 需要进行映射.

可能有重复元素, 进行去重
如何找下标, 二分.
前缀和可以用 0 开始的 ★★★

vector<PII> q, p;
vector<int> ord, s;
int find(int x) {
    int l = 0, r = ord.size() - 1;
    while (l < r) {
        int mi = l + r >> 1;
        if (ord[mi] >= x) r = mi;
        else l = mi + 1;
    }
    return l;
}
int main() {
    int n = read(), m = read();
    rep(i, 0, n) {
        int a = read(), b = read();
        ord.push_back(a), q.push_back({ a,b });
    }
    rep(i, 0, m) {
        int a = read(), b = read();
        ord.push_back(a), ord.push_back(b);
        p.push_back({ a,b });
    }
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    s.resize(ord.size());
    for (auto [k, v] : q) {
        k = find(k);
        s[k] += v;
    }
    for (int i = 1;i < s.size();i++) s[i] += s[i - 1];
    for (auto [k, v] : p) {
        int l = find(k), r = find(v);
        printf("%d\n", l == 0 ? s[r] : s[r] - s[l - 1]);
    }
    return 0;
}

区间合并

Q: 给定有 n 个区间, 合并有交集的区间.

vector<PII> a;
int main() {
    int n = read();
    rep(i, 0, n) a.push_back({ read(),read() });
    sort(a.begin(), a.end());
    int end = -2e9;  // 写成 2e-9 WA了一次...
    int res = 0;
    for (auto [l, r] : a) {
        if (l > end) res++;
        end = max(r, end);
    }
    O(res);
    return 0;
}

每日一题的...

AcWing 1826. 农田缩减

排序后进行判断是否是边界就行了, 不过这样需要4个数组了.

int x[N5], y[N5], a[N5], b[N5];
int main() {
    int n = read();
    rep(i, 0, n) {
        a[i] = x[i] = read();
        b[i] = y[i] = read();
    }
    sort(a, a + n);sort(b, b + n);
    int res = 2e9;
    rep(i, 0, n) {
        int x1, x2, y1, y2;
        x1 = x[i] == a[0] ? a[1] : a[0];
        x2 = x[i] == a[n - 1] ? a[n - 2] : a[n - 1];
        y1 = y[i] == b[0] ? b[1] : b[0];
        y2 = y[i] == b[n - 1] ? b[n - 2] : b[n - 1];
        res = min(res, (x2 - x1) * (y2 - y1));
    }
    O(res);
    return 0;
}

这篇关于acwing算法基础课I的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！