发布于 

Codeforces Round 536 (Div. 2)

Codeforces 题解 OI

昨天晚上打开CF突然发现有个比赛,激动至极,遂猝不及防地与@llf0703合作了一把

结果评测机锅了,Unrated...(明明是因为把Div.3标成了Div.2)

这次的题面是春节主题的,有意思

A. Lunar New Year and Cross Counting

题意过于显然,自己看吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 510;

char a[MAXN][MAXN];

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

// 统计图中'X'的数量(直接n^2暴力枚举就能A了吧)

/*
X.X
.X.
X.X
*/

int main() {
    // ifstream cin(".in");
    // ofstream cout(".out");

    int n = read();
    for (int i = 1; i <= n; i++) {
        scanf("%s", a[i] + 1);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 'X' && a[i][j] == a[i - 1][j - 1] &&
                a[i][j] == a[i - 1][j + 1] && a[i][j] == a[i + 1][j - 1] &&
                a[i][j] == a[i + 1][j + 1]) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

B. Lunar New Year and Food Ordering

十分显然的大模拟,照着题意写就好,稍稍加一个优化,就是记录一下上一次取走的最便宜的菜,不要每次从头枚举,记得开int64

代码是llf0703的,被int64和优化坑了两次罚时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

#include <cctype>

inline int64 read() {
    int64 X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

struct node {
    int64 cnt, price, id;
} a[MAXN];

int ord[MAXN];

bool cmp(const node& x, const node& y) {
    return (x.price == y.price) ? x.id < y.id : x.price < y.price;
}

inline void write(int64 x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    int n = read();
    int m = read();
    int64 tot = 0;
    for (int i = 1; i <= n; i++) {
        a[i].cnt = read();
        a[i].id = i;
        tot += a[i].cnt;
    }

    for (int i = 1; i <= n; i++) {
        a[i].price = read();
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        ord[a[i].id] = i;
    }
    int cheapest = 1;
    for (int i = 1; i <= m; i++) {
        int64 t = read();
        int64 d = read();
        if (d > tot) {
            tot = 0;
            puts("0");
            continue;
        }
        if (a[ord[t]].cnt >= d) {
            a[ord[t]].cnt -= d;
            tot -= d;
            write(a[ord[t]].price * d);
            putchar('\n');
        } else {
            tot -= d;
            d -= a[ord[t]].cnt;
            int pos = cheapest;
            int64 ans = a[ord[t]].cnt * a[ord[t]].price;
            a[ord[t]].cnt = 0;
            while (true) {
                if (d >= a[pos].cnt) {
                    d -= a[pos].cnt;
                    ans += a[pos].price * a[pos].cnt;
                    a[pos].cnt = 0;
                } else {
                    a[pos].cnt -= d;
                    cheapest = pos;
                    ans += a[pos].price * d;
                    break;
                }
                pos++;
            }
            write(ans);
            putchar('\n');
        }
    }
    return 0;
}

C. Lunar New Year and Number Division

这题第一反应是一大一小直接贪,然鹅并不会证明,比赛时也找不到反例(卡了20分钟找反例,不肯相信这么显然)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 3e5 + 10;

int64 a[MAXN];

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

//题意:n个正整数,分成j组(自选),求最小的每组的和的平方和
//贪心,每组肯定只有2个数,直接最大的加最小的? 不太可能
// 1 2 100 200 500 600

int main() {
    // ifstream cin(".in");
    // ofstream cout(".out");

    int n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    sort(a + 1, a + n + 1);

    int64 ans = 0;
    for (int i = 1; i <= n / 2; i++) {
        ans += (a[i] + a[n + 1 - i]) * (a[i] + a[n + 1 - i]);
    }
    cout << ans << endl;

    return 0;
}

D. Lunar New Year and a Wander

类似NOIP2018 D2T1,不过限制条件更少,直接优先队列BFS就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

class LFS {
   public:
    LFS() {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = 0;
    }
    LFS(int N) {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = N;
    }
    void adde(int from, int to, int w) {
        e[ecnt].to = to;
        e[ecnt].w = w;
        e[ecnt].next = head[from];
        head[from] = ecnt++;
    }
    void addde(int a, int b, int w) {
        adde(a, b, w);
        adde(b, a, w);
    }

    void solve() {
        memset(vis, false, sizeof vis);
        while (!q.empty()) {
            q.pop();
        }
        q.push(1);
        while (!q.empty()) {
            int u = q.top();
            q.pop();
            if (vis[u]) {
                continue;
            }
            cout << u << ' ';
            vis[u] = true;
            for (int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].to;
                if (!vis[v]) {
                    q.push(v);
                }
            }
        }
    }

   protected:
    struct Edge {
        int to, next, w;
    } e[MAXN * 2];
    int head[MAXN];
    int ecnt;
    int n;
    bool vis[MAXN];
    priority_queue<int, vector<int>, greater<int>> q;

   private:
    void dfs(int u, int fa) {
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (v != fa) {
                dfs(v, u);
            }
        }
    }
};

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int main() {
    int n = read();
    int m = read();
    LFS* tree = new LFS(n);
    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        if (u == v) {
            continue;
        }
        tree->addde(u, v, 1);
    }
    tree->solve();
    delete tree;
}

EF

比赛时看到Unrated心头一凉,E题基本想出来了没有写,F题放弃,有空再补上代码吧

许可协议

本文采用 署名-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章
快来参与讨论吧