Educational Codeforces Round 55(A-E,G)

发表于 | 更新于 | 分类于 | 阅读次数：

一万个人会 G.. 已经记不得多久没写网络流了..

E 题 k=1的话还做做，大于1还没想好.. 这也太复杂了..

这里的老哥敲题可真快..

地址

A. Vasya and Book

水分类讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n, x, y, d;
        scanf("%d%d%d%d", &n, &x, &y, &d);
        int ans = 1e9+5;
        if (x%d == y%d) ans = min(ans, abs(x-y)/d);
        if (1%d == y%d) ans = min(ans, (y-1)/d+(x-1)/d+1);
        if (n%d == y%d) ans = min(ans, (n-y)/d+(n-x)/d+1);
        if (ans == 1e9+5) ans = -1;
        printf("%d\n", ans);
    }
}

B. Vova and Trophies

题意

一个只包含 'G' 'S' 的字符串，问你交换一次任意两个字符后，连续的 'G' 最多有多长

分析

枚举 'S'，判断这个'S' 换成 'G' 后加上其两边的总长，稍作讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int l[N], r[N];
int n, num;
char s[N];
int main() {
    scanf("%d%s", &n, s+1);
    for (int i = 1; i <= n; i++)
        if (s[i] == 'G') l[i] = l[i-1]+1, num++;
    for (int i = n; i >= 1; i--)
        if (s[i] == 'G') r[i] = r[i+1]+1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, l[i]);
        if (s[i] == 'S') {
            if (num == l[i-1]+r[i+1]) ans = max(ans, l[i-1]+r[i+1]);
            else ans = max(ans, l[i-1]+r[i+1]+1);
        }
    }
    printf("%d\n", ans);
}

C. Multi-Subject Competition

题意

给你每个学生的专攻方向和其技能等级，要求你所选的每个方向的人数都相同。

问你能得到的最大技能等级之和。

分析

按专攻方向分类，再分别从大到小排序。

然后分别算出这个专业选 i 人对答案的共献，即max(0, sum of prefix[i])。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m;
vector<int> v[N];
bool cmp1(int a, int b) {
    return a > b;
}
ll res[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        v[a].push_back(b);
    }
    for (int i = 1; i <= m; i++) sort(v[i].begin(), v[i].end(), cmp1);
    for (int i = 1; i <= m; i++) {
        ll tmp = 0;
        for (int j = 0; j < v[i].size(); j++) {
            tmp += v[i][j];
            if (tmp < 0) break;
            res[j+1] += tmp;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, res[i]);
    cout << ans << endl;
}

D. Maximum Diameter Graph

题意

给你每个点的度数限制，问你不超过度数限制的情况下如何连边，使得连通图的直径最长。

分析

点分为一度和大于一度。可以先判断下连不连通。

大于1度的点一定连成一条直线，然后头尾连俩一度的点，中间随便插即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 505;
int n, d[N];
vector<int> a, b;
vector<pii> res;
int main() {
    int s = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &d[i]);
        if (d[i] == 1) a.push_back(i);
        else b.push_back(i), s += d[i]-2;
    }
    if ((int)a.size()-2 > s) puts("NO");
    else {
        int ans = b.size() + min((int)a.size(),2);
        printf("YES %d\n", ans-1);
        if (b.size() == 0) {
            puts("1 2");
            return 0;
        }
        for (int i = 0; i < b.size()-1; i++) res.push_back(pii(b[i], b[i+1]));
        if (a.size() >= 1) res.push_back(pii(b[0], a[0]));
        if (a.size() >= 2) res.push_back(pii(b[b.size()-1], a[1]));
        int j = 0;
        for (int i = 2; i < a.size(); i++) {
            while (d[b[j]] <= 2) j++;
            res.push_back(pii(a[i], b[j]));
            d[b[j]]--;
        }
        printf("%d\n", res.size());
        for (auto p : res) printf("%d %d\n", p.first, p.second);
    }
}

E. Increasing Frequency

题意

给定一个数字序列。你有一次区间加法的机会，问操作后连续的数字 c 最多是多少个。

分析

不同数字分别考虑。然后 DP，对每个位置而言分别有三个状态：操作区间前，操作区间中，操作区间后。从前一个位置转移即可。

(代码写得略烂..写得我自己都有点浑..)

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, c, a[N];
int num[N];
vector<int> v[N];
int dp[N][3];
int main() {
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        num[i] = num[i-1];
        if (a[i] == c) num[i]++;
        v[a[i]].push_back(i);
    }
    int ans = num[n];
    for (int i = 1; i < N; i++) {
        if (i == c) continue;
        if (!v[i].size()) continue;
        dp[0][0] = num[v[i][0]];
        dp[0][1] = num[v[i][0]]+1;
        dp[0][2] = 0;
        for (int j = 1; j < v[i].size(); j++) {
            int tmp = num[v[i][j]]-num[v[i][j-1]];
            dp[j][0] = dp[j-1][0] + tmp;
            dp[j][1] = max(dp[j-1][0] + tmp+1, dp[j-1][1]+1);
            dp[j][2] = max(dp[j-1][2], dp[j-1][1]) + tmp;
        }
        int m = v[i].size();
        ans = max(ans, dp[m-1][2]+num[n]-num[v[i][m-1]]);
        ans = max(ans, dp[m-1][0]+num[n]-num[v[i][m-1]]);
        ans = max(ans, dp[m-1][1]+num[n]-num[v[i][m-1]]);
    }
    cout << ans << endl;
}

G. Petya and Graph

题意

选了边就要选两头的点。问你最终选出的子图边权减点权最大是多少。

分析

最大权闭合子图..

由于是二分图，复杂度不超过 O(n*m)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge {
    Edge() {}
    Edge(int a, int b, ll c, ll d) :from(a), to(b), cap(c), flow(d) {}
    int from, to;
    ll cap, flow;
};
const int N = 2e3+5;
const ll INF = 1e18;
struct Dinic {
    vector<Edge> edges;
    vector<int> G[N];
    bool vis[N];
    int d[N], cur[N], s, t;
    void Init() {
        for (int i = 0; i < N; i++) G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, ll cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        int x = edges.size();
        G[from].push_back(x - 2);
        G[to].push_back(x - 1);
    }
    bool BFS() {
        memset(vis, false, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = true;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = 0; i<G[x].size(); i++) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    ll DFS(int x, ll a) {
        if (x == t || a == 0) return a;
        ll flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++) {
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to]
                && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
    ll MaxFlow(int s, int t) {
        this->s = s; this->t = t;
        ll flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
}dinic;
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    int st = N-1, ed = N-2;
    for (int i = 1; i <= n; i++) {
        int w; scanf("%d", &w);
        dinic.AddEdge(i, ed, w);
    }
    ll ans = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dinic.AddEdge(st, n+i, w);
        dinic.AddEdge(n+i, u, INF);
        dinic.AddEdge(n+i, v, INF);
        ans += w;
    }
    ans -= dinic.MaxFlow(st, ed);
    cout << ans << endl;
}