头像

ToInfinity

Acwing University




离线:13分钟前



1.png

2.png

3.png

4.png

//
// Created by Genes on 2020/12/3.
//
// 最长连续不重复子序列
// 双指针

#include <algorithm>
#include <iostream>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], cnt[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int res = 0;
//    for (int i = 0; i < n; i++) {
//        for (int j = i; j < n; j++) {
//            if (check(i, j)) {
//                res = max(res, j - i + 1);
//            }
//        }
//    }
    for (int i = 0, j = 0; i < n; i++) {
        cnt[a[i]]++;
        while (cnt[a[i]] > 1) {
            cnt[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    return 0;
}



1.png

2.png

//
// Created by Genes on 2020/12/3.
//
// 最高的牛

#include <algorithm>
#include <iostream>
#include <set>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 1e4 + 10;

set<pair<int, int>> existed;
int n, p, h, m;
int c[N], d[N];

int main() {
    ios;
    cin >> n >> p >> h >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (a > b) {
            swap(a, b);
        }
        if (!existed.count({a, b})) {
            existed.insert({a, b});
            d[a + 1]--, d[b]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        c[i] = c[i - 1] + d[i];
        cout << h + c[i] << endl;
    }
    return 0;
}



活动打卡代码 AcWing 101. 最高的牛

//
// Created by Genes on 2020/12/3.
//
// 最高的牛

#include <algorithm>
#include <iostream>
#include <set>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 1e4 + 10;

set<pair<int, int>> existed;
int n, p, h, m;
int c[N], d[N];

int main() {
    ios;
    cin >> n >> p >> h >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (a > b) {
            swap(a, b);
        }
        if (!existed.count({a, b})) {
            existed.insert({a, b});
            d[a + 1]--, d[b]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        c[i] = c[i - 1] + d[i];
        cout << h + c[i] << endl;
    }
    return 0;
}



活动打卡代码 AcWing 100. IncDec序列

//
// Created by Genes on 2020/12/2.
//
//增减序列 IncDec Sequence
#include <iostream>
#include<algorithm>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int n;
ll a[N], b[N];

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

int main() {
    ios;
    cin >> n;
    ll p = 0, q = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    b[1] = a[1];
    b[2] -= a[1];
    for (int i = 2; i <= n; i++) { // b2~bn
        insert(i, i, a[i]);// 可以直接构造, c=a[i]-a[i-1]
        if (b[i] > 0) {
            p += b[i];
        } else {
            q -= b[i];
        }
    }
    cout << max(p, q) << endl << abs(p - q) + 1 << endl;
    return 0;
}


活动打卡代码 AcWing 100. 增减序列

//
// Created by Genes on 2020/12/2.
//
//增减序列 IncDec Sequence
#include <iostream>
#include<algorithm>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int n;
ll a[N], b[N];

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

int main() {
    ios;
    cin >> n;
    ll p = 0, q = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    b[1] = a[1];
    b[2] -= a[1];
    for (int i = 2; i <= n; i++) { // b2~bn
        insert(i, i, a[i]);// 可以直接构造, c=a[i]-a[i-1]
        if (b[i] > 0) {
            p += b[i];
        } else {
            q -= b[i];
        }
    }
    cout << max(p, q) << endl << abs(p - q) + 1 << endl;
    return 0;
}



1.png

2.png

3.png

4.png

5.png

6.png

7.png

8.png

代码

//
// Created by Genes on 2020/12/2.
//
//增减序列 IncDec Sequence
#include <iostream>
#include<algorithm>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int n;
ll a[N], b[N];

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

int main() {
    ios;
    cin >> n;
    ll p = 0, q = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    b[1] = a[1];
    b[2] -= a[1];
    for (int i = 2; i <= n; i++) { // b2~bn
        insert(i, i, a[i]);// 可以直接构造, c=a[i]-a[i-1]
        if (b[i] > 0) {
            p += b[i];
        } else {
            q -= b[i];
        }
    }
    cout << max(p, q) << endl << abs(p - q) + 1 << endl;
    return 0;
}



1.png

2.png

代码

//
// Created by Genes on 2020/12/2.
//
// 激光炸弹

#include <algorithm>
#include <iostream>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 5e3 + 10; //不能开 1e5+10, 内存限制比较严格

int s[N][N];
int n, r;

int main() {
    ios;
    cin >> n >> r;
    r = min(5001, r); // 因为r最大可以取 10^9
    for (int i = 0; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
//        s[++x][++y]=w;  //错误
        s[++x][++y] += w; //右移一位, 就不需要考虑边界了, 并且必须是+=, 不能是=, 因为1个位置可能有多个目标
    }
    for (int i = 1; i <= 5001; i++) {
        for (int j = 1; j <= 5001; j++) {
//            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = r; i <= 5001; i++) {
        for (int j = r; j <= 5001; j++) {
            ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 99. 激光炸弹

//
// Created by Genes on 2020/12/2.
//
// 激光炸弹

#include <algorithm>
#include <iostream>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 5e3 + 10; //不能开 1e5+10, 内存限制比较严格

int s[N][N];
int n, r;

int main() {
    ios;
    cin >> n >> r;
    r = min(5001, r); // 因为r最大可以取 10^9
    for (int i = 0; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
//        s[++x][++y]=w;  //错误
        s[++x][++y] += w; //右移一位, 就不需要考虑边界了, 并且必须是+=, 不能是=, 因为1个位置可能有多个目标
    }
    for (int i = 1; i <= 5001; i++) {
        for (int j = 1; j <= 5001; j++) {
//            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = r; i <= 5001; i++) {
        for (int j = r; j <= 5001; j++) {
            ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 99. 激光炸弹

//
// Created by Genes on 2020/12/2.
//
// 激光炸弹

#include <algorithm>
#include <iostream>

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

using namespace std;

const int N = 5e3 + 10; //不能开 1e5+10, 内存限制比较严格

int s[N][N];
int n, r;

int main() {
    ios;
    cin >> n >> r;
    r = min(5001, r); // 因为r最大可以取 10^9
    for (int i = 0; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
//        s[++x][++y]=w;  //错误
        s[++x][++y] += w; //右移一位, 就不需要考虑边界了, 并且必须是+=, 不能是=, 因为1个位置可能有多个目标
    }
    for (int i = 1; i <= 5001; i++) {
        for (int j = 1; j <= 5001; j++) {
//            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    int ans = 0;
    for (int i = r; i <= 5001; i++) {
        for (int j = r; j <= 5001; j++) {
            ans = max(ans, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    cout << ans << endl;
    return 0;
}


新鲜事 原文

图片 图片 图片