Star's Blog

1
#include <iostream>
2

3
using namespace std;
4

5
const int N = 500010;
6

7
int a[N];
8

9
int main() {
10
    int n;
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        int b, c;
14
        scanf("%d%d", &b, &c);
15
        a[i] = b + c;
16
    }
17
    int res = 0, l = 0, r = a[1];
18
    for (int i = 2; i <= n; ++i) {
19
        if (a[i] < l) l = 0, r = a[i];
20
        else {
21
            res++;
22
            l = a[i] - l;
23
            r = max(0, a[i] - r);
24
            swap(l, r); // 这里是为了防止原来的变量被覆盖
25
        }
26
    }
27
    printf("%d\n", res);
28
    return 0;
29
}

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
int fa[10010], cnt[10010];
7

8
int getfa(int x) {
9
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
10
}
11

12
int main() {
13
    ios::sync_with_stdio(0);
14
    cin.tie(0), cout.tie(0);
15
    int n, m;
16
    cin >> n >> m;
17
    for (int i = 1; i <= n; ++i) {
18
        fa[i] = i;
19
        cnt[i] = 1;
20
    }
21
    for (int i = 1; i <= m; ++i) {
22
        int x, y;
23
        cin >> x >> y;
24
        x = getfa(x), y = getfa(y);
25
        if (x != y) fa[y] = x, cnt[x] += cnt[y];
26
    }
27
    int mx = 0;
28
    for (int i = 1; i <= n; ++i) {
29
        if (i == fa[i]) mx = max(mx, cnt[i]);
30
    }
31
    vector<int> res(1, 1);
32
    for (int i = 1; i <= mx; ++i) {
33
        for (int &t : res) t *= 2;
34
        for (int i = 0; i < res.size(); ++i) {
35
            if (res[i] > 9) {
36
                if (i == res.size() - 1) {
37
                    if (res.size() < 100) res.push_back(res[i] / 10);
38
                }
39
                else res[i + 1] += res[i] / 10;
40
                res[i] %= 10;
41
            }
42
        }
43
    }
44
    for (int i = res.size() - 1; i; --i) cout << res[i];
45
    cout << res[0] - 1 << endl;
46
    return 0;
47
}

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
using namespace std;
6

7
vector<int> f[10010];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n, m;
13
    cin >> n >> m;
14
    for (int i = 1; i <= m; ++i) {
15
        int x, y;
16
        cin >> x >> y;
17
        f[x].push_back(y);
18
        f[y].push_back(x);
19
    }
20
    int p = 1;
21
    for (int i = 1; i <= n; ++i) {
22
        if (f[i].size() > f[p].size()) p = i;
23
    }
24
    sort(f[p].begin(), f[p].end());
25
    for (int i : f[p]) {
26
        cout << i << ' ';
27
    }
28
    cout << endl;
29
    return 0;
30
}

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
long long f[1000010], a[1000010];
7
int q[1000010];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n, l, r;
13
    cin >> n >> l >> r;
14
    memset(f, 0x3f, sizeof(f));
15
    for (int i = 1; i <= n; ++i) {
16
        cin >> a[i];
17
    }
18
    int hh = 0, tt = -1;
19
    f[0] = 0;
20
    for (int i = 1; i <= n; ++i) {
21
        while (hh <= tt && q[hh] + r + 1 < i) hh++;
22
        if (i - l - 1 >= 0) {
23
            while (hh <= tt && f[q[tt]] >= f[i - l - 1]) tt--;
24
            q[++tt] = i - l - 1;
25
        }
26
        if (hh <= tt) f[i] = f[q[hh]] + a[i];
27
    }
28
    if (f[n] >= 0x3f3f3f3f3f3f3f3f) cout << -1 << endl;
29
    else cout << f[n] << endl;
30
    return 0;
31
}