个人空间 - AcWing

Apeiron

关注数

粉丝数

阅读量

+关注发消息

在线

活动打卡代码 AcWing 803. 区间合并

Apeiron
7天前

                #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PAIR;

void merge(vector<PAIR> &segs) {

    vector<PAIR> res;

    sort(segs.begin(), segs.end());

    int start = segs[0].first, end = segs[0].second;

    for(int i = 1; i < segs.size(); i++) {
        if(segs[i].first > end) {
            res.push_back({ start,end });
            start = segs[i].first;
            end = segs[i].second;
        } else
            end = max(end, segs[i].second);
    }
    res.push_back({ start,end });

    segs = res;

}

int main() {

    ios::sync_with_stdio(false);

    int n, l, r;

    vector<PAIR> segs;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> l >> r;
        segs.push_back({ l,r });
    }

    merge(segs);
    cout << segs.size();

    return 0;
}



            

活动打卡代码 AcWing 802. 区间和

Apeiron
7天前

                #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PAIR;

const int N = 3e5 + 10;
int arr[N], sum[N];
vector<int> index;

vector<PAIR> add, query;

int getIndex(int x) {
    int l = 0, mid, r = index.size() - 1;

    while(l != r) {
        mid = l + r >> 1;
        if(index[mid] < x)
            l = mid + 1;
        else
            r = mid;
    }

    return r + 1;
}

int main() {

    ios::sync_with_stdio(false);

    int n, m, x, c, l, r, temp;

    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        cin >> x >> c;
        add.push_back({ x,c });
        index.push_back(x);
    }

    for(int i = 0; i < m; i++) {
        cin >> l >> r;
        query.push_back({ l,r });
        index.push_back(l);
        index.push_back(r);
    }

    sort(index.begin(), index.end());
    //使用unique函数需要先排序（功能是将数组中【相邻】的重复元素去除）
    index.erase(unique(index.begin(), index.end()), index.end());
    for(int i = 0; i < n; i++) {
        arr[getIndex(add[i].first)] += add[i].second;
    }

    for(int i = 1; i <= index.size(); i++)
        sum[i] = sum[i - 1] + arr[i];

    for(int i = 0; i < m; i++) {
        cout << sum[getIndex(query[i].second)] - sum[getIndex(query[i].first) - 1] << endl;
    }

    return 0;
}

            

活动打卡代码 AcWing 801. 二进制中1的个数

Apeiron
7天前

                #include<iostream>

using namespace std;

int lowbit(int x) {
    return x & -x;
}

int main() {

    ios::sync_with_stdio(false);

    int n, temp, count;

    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> temp;
        count = 0;
        while(temp != 0) {
            temp -= lowbit(temp);
            count++;
        }
        cout << count << " ";
    }

    return 0;
}

            

活动打卡代码 AcWing 2816. 判断子序列

Apeiron
8天前

                #include<iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

bool isSubsequence(int a[], int n, int b[], int m) {
    int i=0, j=0;
    while(i < n&&j < m) {
        if(a[i] == b[j++])
            i++;
    }

    return i == n;
}

int main() {
    ios::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int j = 0; j < m; j++)
        cin >> b[j];

    if(isSubsequence(a, n, b, m))
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

            

活动打卡代码 AcWing 800. 数组元素的目标和

Apeiron
8天前

                #include<iostream>

using namespace std;

const int N = 1e5 + 10;

int A[N], B[N];

int main() {
    ios::sync_with_stdio(false);

    int n, m, x, temp;

    cin >> n >> m >> x;

    for(int i = 0; i < n; i++)
        cin >> A[i];

    for(int j = 0; j < m; j++)
        cin >> B[j];

    int i = 0, j = m - 1;
    while(i < n && j >= 0) {
        temp = A[i] + B[j];
        if(temp == x)
            cout << i << " " << j-- << endl;
        else if(temp < x)
            i++;
        else j--;
    }

    return 0;
}



            

题解 AcWing 799. 最长连续不重复子序列——一种慢指针不用遍历的实现思路

Apeiron
8天前

核心思路

不记录出现频率，而是记录每个数k最后出现的位置index[k]，若index[k]大于等于慢指针start，则令start=index[k]+1，并令index[k]值为快指针i，省略慢指针遍历的步骤
其他思路与y总讲解一致，这里不再赘述

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int index[N];

int main() {
    int n, temp, start = 1;

    int maxLen = 0, curLen = 0;

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> temp;
        if(index[temp] >= start) {
            start = index[temp] + 1;
            index[temp] = i;

            maxLen = max(maxLen, curLen);

            curLen = i - start + 1;
        } else {
            index[temp] = i;
            curLen++;
        }
    }

    maxLen = max(maxLen, curLen);

    cout << maxLen;
    return 0;
}

活动打卡代码 AcWing 799. 最长连续不重复子序列

Apeiron
8天前

                #include<iostream>

using namespace std;

const int N = 1e5 + 10;

int index[N];

int main() {
    int n, temp, start = 1;

    int maxLen = 0, curLen = 0;

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> temp;
        if(index[temp] >= start) {
            start = index[temp] + 1;
            index[temp] = i;

            if(curLen > maxLen)
                maxLen = curLen;

            curLen = i - start + 1;
        } else {
            index[temp] = i;
            curLen++;
        }
    }

    if(curLen > maxLen)
        maxLen = curLen;

    cout << maxLen;
    return 0;
}

            

活动打卡代码 AcWing 798. 差分矩阵

Apeiron
8天前

                #include<iostream>

using namespace std;

const int N = 1010;

int matrix[N][N];

void insert(int x1, int y1, int x2, int y2, int c) {
    matrix[x1][y1] += c;
    matrix[x2 + 1][y1] -= c;
    matrix[x1][y2 + 1] -= c;
    matrix[x2 + 1][y2 + 1] += c;
}

int main() {

    ios::sync_with_stdio(false);

    int n, m, q;
    int x1, y1, x2, y2, c;

    cin >> n >> m >> q;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> c;
            insert(i, j, i, j, c);
        }
    }

    for(int i = 0; i < q; i++) {
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            matrix[i][j] += matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1];
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

            

活动打卡代码 AcWing 797. 差分

Apeiron
8天前

                #include<iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], b[N];

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

int main() {

    ios::sync_with_stdio(false);
    int n, m, l, r, c;

    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        insert(i, i, a[i]);
    }

    for(int i = 0; i < m; i++) {
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    for(int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        cout << b[i] << " ";
    }

    return 0;
}

            

活动打卡代码 AcWing 796. 子矩阵的和

Apeiron
9天前

                #include<iostream>

using namespace std;

const int N = 1010;

int matrix[N][N];

int main() {

    ios::sync_with_stdio(false);

    int n, m, q, temp;
    int x1, x2, y1, y2;
    cin >> n >> m >> q;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            cin >> temp;
            matrix[i][j] = temp + matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1];
        }

    for(int i = 0; i < q; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << matrix[x2][y2] - matrix[x1 - 1][y2] - matrix[x2][y1 - 1] + matrix[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

核心思路

0 评论

0 评论

0 评论

0 评论

0 评论