2015 ACM-ICPC, Asia Beijing Regional

字数统计: 1.3k字   |   阅读时长: 7分
训练题解
solved A B C D E F G H I J K
3 / 11 O · · · · · O · · O ·
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

比赛链接

A - Xiongnu’s Land

solved by lllllan. 01:14(+3)

AC代码 
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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 7;
typedef long long ll;

#define pii piar<int, int>

inline void _max (int& a, int b) { if (a < b) a = b; }
inline void _min (int& a, int b) { if (a > b) a = b; }

ll d[maxn];
ll a[maxn];
ll sum[maxn];

void run () {
    memset(d, 0, sizeof d);
    memset(a, 0, sizeof a);
    memset(sum, 0, sizeof sum);

    int n, R;

    scanf("%d%d", &R, &n);

    ll Sum = 0;
    while (n--) {
        int l, t, w, h;

        scanf("%d%d%d%d", &l, &t, &w, &h);

        d[l + 1] += 1ll *h;
        d[l + w + 1] -= 1ll * h;

        Sum += (1ll * w * h);

    }

    int ans = -1;
    sum[0] = a[0] = d[0];
    for (int i = 1; i <= R; ++i) {
        a[i] = a[i - 1] + d[i];
        sum[i] = sum[i - 1] + a[i];

        if (sum[i] * 2 >= Sum &&  (ans == -1 || sum[ans] == sum[i])) {
            ans = i;
        }
    }

    printf("%d\n", ans);
}

int main () {

    int _ = 1;

    scanf("%d", &_);

    while (_--) run();

    return 0;
}

D - Kejin Game

solved by lllllan. (-)

AC代码 
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
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

inline int rd() {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

inline void _max (int& a, int b) { if (a < b) a = b; }
inline void _min (int& a, int b) { if (a > b) a = b; }

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
const int maxm = 4e4 + 10;

int cnt, head[maxn];
struct edge {
	int v, w, next;
} e[maxm];

inline void add (int u, int v, int w) {
	e[cnt] = {v, w, head[u]}, head[u] = cnt++;
}

inline void addedge (int u, int v, int w) {
	add(u, v, w), add(v, u, 0);
}

int s, t;
int dep[maxn];
bool bfs () {
	memset(dep, 0, sizeof dep);
	queue<int> Q;
	Q.emplace(s); dep[s] = 1;
	
	while (Q.size()) {
		int u = Q.front(); Q.pop();
		for (int i = head[u]; ~i; i = e[i].next) {
			int v = e[i].v, w = e[i].w;
			if (0 == dep[v] && w > 0) {
				dep[v] = dep[u] + 1;
				Q.emplace(v);
			}
		}
	}
	
	return dep[t] > 0;
}

int cur[maxn];
int dfs (int u, int flow) {
	if (u == t) return flow;
	for (int& i = cur[u]; ~i; i = e[i].next) {
		int v = e[i].v, w = e[i].w;
		if (dep[v] == dep[u] + 1 && w) {
			int minflow = dfs(v, min(flow, w));
			if (minflow > 0) {
				e[i].w -= minflow;
				e[i ^ 1].w += minflow;
				return minflow;
			}
		}
	}
	return 0;
}

int dinic () {
	int ans = 0;
	while (bfs()) {
		for (int i = 1; i <= t; ++i) cur[i] = head[i];
		while (int d = dfs(s, inf)) ans += d;
	}
	return ans;
}

void run () {
	
	int n = rd(), m = rd(), k = rd();
	
	s = 2 * n + 1, t = s + 1;
	
	cnt = 0;
	memset(head, -1, sizeof head);
	
	for (int i = 1; i <= m; ++i) {
		int u = rd(), v = rd(), w = rd();
		addedge(2 * u, 2 * v - 1, w);
	}
	
	for (int i = 1; i <= n; ++i) addedge(s, 2 * i - 1, rd() );
	
	for (int i = 1; i <= n; ++i) addedge(2 * i - 1, 2 * i, rd() );
	
	add(2 * k, t, inf);
	
	printf("%d\n", dinic());

}

int main () {

	int _ = 1;

	_ = rd();

	while (_--) run();

	return 0;
}

G - Mysterious Antiques in Sackler Museum

solved by Tryna. 00:45(+1)

AC代码 
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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 +10;
const int N = 2e5 +10;

#define pii piar<int, int>
int w[10], h[10];

void run () {
    map<int,int>mp;
    for(int i = 1; i <= 4; i++) {
        scanf("%d%d", &w[i], &h[i]);
        mp[w[i]]++;
        if(w[i] != h[i]) mp[h[i]]++;
    }
    for(auto g : mp) {
        if(g.second >= 3) {
            puts("Yes");
            return ;
        }
    }
    for(int i = 1; i <= 4; i++) {
        for(int j = i + 1; j <= 4; j++) {
            int ans = 0;
            if(w[i] == w[j]) {
                ans = h[i] + h[j];
                for(int k = 1; k <= 4; k++) {
                    if(k == i || k == j) continue;
                    if(w[k] == ans || h[k] == ans) {
                        puts("Yes");
                        return ;
                    }
                }
            }
            if(h[i] == h[j]) {
                ans = w[i] + w[j];
                for(int k = 1; k <= 4; k++) {
                    if(k == i || k == j) continue;
                    if(w[k] == ans || h[k] == ans) {
                        puts("Yes");
                        return ;
                    }
                }
            }
            if(w[i] == h[j]) {
                ans = h[i] + w[j];
                for(int k = 1; k <= 4; k++) {
                    if(k == i || k == j) continue;
                    if(w[k] == ans || h[k] == ans) {
                        puts("Yes");
                        return ;
                    }
                }
            }
            if(h[i] == w[j]) {
                ans = w[i] + h[j];
                for(int k = 1; k <= 4; k++) {
                    if(k == i || k == j) continue;
                    if(w[k] == ans || h[k] == ans) {
                        puts("Yes");
                        return ;
                    }
                }
            }
        }
    }
    puts("No");
}

int main () {

    int _ = 1;

    scanf("%d", &_);

    while (_--) run();

    return 0;
}

J - Osu! Master

solved by Sstee1XD. 00:33(+)

AC代码 
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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 +10;
const int N = 2e5 +10;

#define pii piar<int, int>

char ch, pch;
int pre, now, n;

void run () {
    int ans = 0;
    pre = -1;
    pch = 'x';

    for (int i = 1; i <= n; ++i) {
        getchar();
        scanf("%c", &ch);
        if (ch != 'S') scanf(" %d", &now);
        if (i != 1) {
            if (pch == 'C' || pch == 'B') {
                if ((ch == 'C' || ch == 'B') && now == pre + 1) {

                } else {
                    ans++;
                }
            } else {
                if (ch != 'S') ans++;

            }
        }
        pre = now;
        pch = ch;
    }
    if (n) ans++;
    printf("%d\n", ans);
}

int main () {

    int _ = 1;

    while (~scanf("%d", &n)) run();

    return 0;
}
文章目录
  1. A - Xiongnu’s Land
  2. D - Kejin Game
  3. G - Mysterious Antiques in Sackler Museum
  4. J - Osu! Master
|