2019 ACM-ICPC, Asia Nanchang Regional

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

比赛链接

B - A Funny Bipartite Graph

solved by lllllan. 03:57(+)

题意： 有两个均不超过18个点的集合，一开始给定的二分图中，左边集合中的每个点度数最大只有3（最多有三条边连接右边的点），并且左边集合编号为k的点，只会于右边编号不小于k的点相连。要求从给定的二分图中，选取一些点和边构造出一个新的二分图，要求如下:

  • 题目会规定左边集合中，哪些点不能同时选中。这些不能同时出现的点最多只能选择其一。
  • 右边集合的所有点都必须选中，并且和左边集合的点要有连线。
  • 左边集合的每个点都有自己的权值，这个点的权值*该点的度数=选择该点的花费。

求是否能构造出满足题意要求的二分图，并求出最小花费。

题解： 【其实一开始被二分图带跑偏，顺着匈牙利算法的思路去思考如何匹配，然后如何选择更小的花费，我当然是没办法处理那么多条件的】。注意到数据范围——两个集合最多只有18个点，并且左边集合每个点的最大度数仅为3，那一共的点和边也才多少，直接暴搜求最小花费即可。注意点：

  • 剪枝，亲测毫无剪枝是会TLE的，在某次暴搜过程中，如果花费已经超过先前求得的最小花费，就没有继续搜下去的必要了。
  • 对于不能同时被选中的一些点，定义数组进行标记即可。！！但是，要类似于度数一直累加，不能是简单的01标记，否则回溯上会出现问题。【举个栗子，1和3不能被同时选中，2和3不能被同时选中。搜索过程中我先选中了点1，然后对点3标记为1表示不能再被选中；后来搜到了选中了点2也对点3标记为1表示不能再被选中，如果此时回溯，将点3标记为0然后被选中的话，有可能会和点1造成冲突。所以应该是类似于度数的标记，只有标记度为0的点才可以被选中】
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
#include <bits/stdc++.h>
using namespace std;
const int N = 22;
const int inf = 0x3f3f3f3f;

vector<int> G[N];
vector<int> ban[N];

int n, ans;
int vis[N];
int deg[N];
int val[N];

int get(int u) { return deg[u] ? pow(val[u], deg[u]) : 0; }

void dfs(int u, int sum) {
    if (u == n + 1) return (void)(ans = min(ans, sum));
    if (sum > ans) return;

    for (int v : G[u]) {
        if (vis[v]) continue;

        for (int nex : ban[v]) vis[nex]++;

        int pre = get(v);
        deg[v]++;
        int now = get(v);

        dfs(u + 1, sum + now - pre);

        deg[v]--;
        for (int nex : ban[v]) vis[nex]--;
    }
}

void run() {
    scanf("%d", &n);

    for (int i = 0; i <= n; ++i) {
        vis[i] = deg[i] = 0;
        G[i].clear();
        ban[i].clear();
    }

    char s[N];
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; ++j) {
            if (s[j] == '1') G[j].push_back(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; ++j) {
            if (s[j] == '1') ban[i].push_back(j);
        }
    }

    for (int i = 1; i <= n; ++i) scanf("%d", val + i);

    ans = inf;
    dfs(1, 0);
    printf("%d\n", ans == inf ? -1 : ans);
}

int main() {
    int _;
    scanf("%d", &_);
    while (_--) run();
    return 0;
}

C - And and Pair

solved by Tryna.3:02(+3)

题意 给出一个二进制数nn, 要求我们对一个二元组(i,j)(i, j)进行计数,这个二元组满足

  • 0≤j≤i≤n0\leq j \leq i \leq n
  • i&n=ii \& n = i
  • i&j=0i \& j = 0

题解： 首先我们要根据题目知道ii和jj每一位的放置规则。

  • i:ni:n为11, ii为任意, nn为00, ii为00
  • j:ij:i为11, jj为00，ii为00, jj为任意

然后我们从高位到低位枚举nn为11的位,因为i>ji > j, 所以我们只用考虑低位了。 对于剩下的位置, 我们记录00和11的个数。

  • 当这位为11时，ii就有两种情况，对应着jj就有三种情况，所以对答案的贡献为33
  • 当这位为00时，ii就有一种情况，对应着jj就有两种情况，所以对答案的贡献为22
  • 最后还有一种就是所有位全为00的情况
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
string s;
int pre0[maxn], pre1[maxn], pos1[maxn];
ll qpow(ll n, ll k) {
    ll ans = 1;
    while (k) {
        if (k & 1)
            ans = ans * n % mod;
        n = n * n % mod;
        k >>= 1;
    }
    return ans;
}
void run() {
    cin >> s;
    int len = s.size();
    for (int i = 0; i <= len; i++)
        pre1[i] = pre0[i] = pos1[i] = 0;
    for (int i = len - 1; i >= 0; i--) {
        if (s[i] == '1') {
            pre1[i] = pre1[i + 1] + 1;
            pre0[i] = pre0[i + 1];
        }
        if (s[i] == '0') {
            pre0[i] = pre0[i + 1] + 1;
            pre1[i] = pre1[i + 1];
        }
    }
    int num = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == '1') pos1[++num] = i;
    }
    ll ans = 1;
    for (int i = 1; i <= num; i++) {
        ll res = 1;
        res = res * qpow(3, pre1[pos1[i] + 1]) % mod * qpow(2, pre0[pos1[i] + 1]) % mod;
        ans = (ans + res) % mod;
    }
    printf("%lld\n", ans);
}

int main() {
    int t;
    cin >> t;
    while (t--)
        run();
    return 0;
}

E - Bob’s Problem

solved by Tryna & lllllan. 1:18(+1)

题意： 给出nn个点，mm条边，kk条可选的白边。接下来mm行，每一行输入一组无向边和他们的颜色。我们可以选任意条黑色边和kk条白色边。选择若干条边，使这张图连通，求最大的边权值，可以用重边和环。

题解： 贪心地去想，我们要使权值最大，肯定得选所以黑色边，然后将连通的点加入到一个集合里面。接着在考虑白边，我们优先使图连通，如果选完了kk条白边还没连通了，那么就输出−1-1，如果还没选完kk条边就连通了，那么剩下的边就优先选权值大的白边。抢了苏妈妈的图论题，嘿嘿嘿。

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int maxn = 5e5 + 10;

struct Edge {
    int u, v, w, op;
    bool operator<(const Edge &r) const {
        return w > r.w;
    }
} black[maxn], white[maxn];
int num1, num2, n, m, k, f[maxn];
ll ans;
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}
void Kruskal() {
    for (int i = 1; i <= n; i++)
        f[i] = i;
    int num = n - 1;
    for (int i = 1; i <= num1; i++) {
        int f1 = find(black[i].u);
        int f2 = find(black[i].v);
        if (f1 != f2) {
            f[f1] = f2;
            num--;
        }
        ans += black[i].w;
    }
    sort(white + 1, white + 1 + num2);
    for (int i = 1; i <= num2; i++) {
        int f1 = find(white[i].u);
        int f2 = find(white[i].v);
        if (f1 != f2) {
            f[f1] = f2;
            num--;
            ans += white[i].w;
            k--;
            white[i].op = 1;
        }
        if (num == 0) break;
        if (k == 0) break;
    }
    if (num != 0) {
        ans = -1;
        return;
    }
    for (int i = 1; i <= num2; i++) {
        if (k == 0) break;
        if (white[i].op == 1) continue;
        ans += white[i].w;
        k--;
    }
}
void run() {
    scanf("%d %d %d", &n, &m, &k);
    num1 = num2 = 0;
    ans = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w, op;
        scanf("%d %d %d %d", &u, &v, &w, &op);
        if (op == 0) {
            black[++num1].u = u;
            black[num1].v = v;
            black[num1].w = w;
        } else {
            white[++num2].u = u;
            white[num2].v = v;
            white[num2].w = w;
            white[num2].op = 0;
        }
    }
    Kruskal();
    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--)
        run();
    return 0;
}

G. Eating Plan

Solved by Sstee1XD & Tryna. 4:27(+9)

题意： 给你一个11 ~ nn的排列aa，aia_i的权值为ai! mod 998857459a_i!\ mod\ 998857459。mm次询问，请你在这段排列中找到一段长度最小的连续区间[i,j][i, j]，使得(∑x=1jax) mod 998857459>ki(\sum_{x = 1}^ja_x)\ mod\ 998857459 > k_i。

题解： 998857459998857459并不是一个常见的模数。我们打表发现当s>2802s>2802时，s! mod 998857459s!\ mod\ 998857459均为00，所以我们想要当前值发生改变的话，中间一段大于28022802的区间都得取，直到下一个≤2802\leq2802的数为止。所以我们可以先优化一下他给我们的序列，然后就可以280222802^2预处理出所有能取到的值。对于这部分的值，我们用一个maxxmaxx数组来记录，maxximaxx_i代表取长度为i的区间能取到的最大值，接着我们O(n)O(n)遍历这个数组，将需要的值插入setset中，之后每次询问就可以二分出答案了。注意我们在插入的时候要记录之前插入的最大值，当后面长度的最大值小于这个最大值的时候，我们不能将这个值插入setset中，否则会影响我们最终的答案。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const ll mod = 998857459;

inline int rd() {
    int w = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        w = w * 10 + ch - '0';
        ch = getchar();
    }
    return w * f;
}

int n, m;
ll maxx[N];

ll val[3005];
int b[3005], q;
int a[N], len[3005], tot;

struct Node {
    ll v;
    int len;
    bool operator<(const Node &a) const {
        if (v == a.v) return len < a.len;
        return v < a.v;
    }
};

set<Node> st;
set<Node>::iterator it;

int main() {
    n = rd();
    m = rd();
    val[1] = 1;
    for (int i = 2; i <= 2802; ++i) {
        val[i] = val[i - 1] * (ll)i % mod;
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
        maxx[i] = -1;
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i] <= 2802) {
            b[++tot] = a[i];
            len[tot] = 1;
            while (i < n && a[i + 1] > 2802) {
                len[tot]++;
                i++;
            }
        }
    }
    for (int i = tot; i >= 1; --i) {
        ll tmp = val[b[i]];
        int l = 1;
        if (tmp > maxx[l]) {
            maxx[l] = tmp;
        }
        for (int j = i - 1; j >= 1; --j) {
            tmp = (tmp + val[b[j]]) % mod;
            l += len[j];
            if (tmp > maxx[l]) {
                maxx[l] = tmp;
            }
        }
    }
    ll now = -1;
    for (int i = 1; i <= n; i++) {
        if (maxx[i] == -1) continue;
        if (now < maxx[i]) {
            st.insert({maxx[i], i});
            now = maxx[i];
        }
    }
    for (int i = 1; i <= m; ++i) {
        q = rd();
        it = st.lower_bound({q, 0});
        if (it != st.end())
            printf("%d\n", it->len);
        else
            puts("-1");
    }
    return 0;
}

K. Tree

题意：
给定以11为根的有向树，编号为ii的点具有权值viv_i，问树上存在多少有序对x,y{x, y}，设LCAx,y=zLCA_{x, y} = z，使得x≠zx \neq z，y≠zy \neq z，xx和yy的树上距离不超过kk，且vx+vy=2×vzv_x + v_y = 2 \times v_z

思路：
树上距离同样可以通过LCALCA来求解，那么我们在确定了LCALCA之后，找这些点对就比较有想法了。

一次找两个点，同样还是有点困难的，先考虑如何暴力去找。设LCALCA为点zz，我们枚举点xx，那么就能算出想要的点yy的深度和权值了。权值是确定的，但是深度是一个区间，考虑一次性对区间进行询问。对于不同的权值，我们每次要询问一个区间，那么就对每个权值建一棵权值线段树，代表某一深度的数量。直接开会太大，采用动态开点的策略。

接下来考虑如何减小时间复杂度。我们枚举点zz做为LCALCA时，其实就是在以点zz为根节点的子树上进行询问。因为xx和yy互相没有祖先关系，如果每次确定点xx所在的链，询问之后再将这条链加入询问集合，就能直接避免出现这种情况，并且再将询问结果∗2*2就能得到有序对的答案，很像dsu on tree的过程，那么剖完大力合并就行了。

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

using namespace std;

#define endl "\n"

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;

int n, k, tot, son;
int w[N], dep[N], sz[N], bigSon[N];
int rt[N * 80], ls[N * 80], rs[N * 80], num[N * 80];
ll ans;
vector<int> G[N];

void modify(int &id, int l, int r, int p, int v) {
    if (!id) id = ++tot;
    num[id] += v;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid)
        modify(ls[id], l, mid, p, v);
    else
        modify(rs[id], mid + 1, r, p, v);
}

int query(int id, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return num[id];
    int ans = 0;
    int mid = l + r >> 1;
    if (ql <= mid) ans += query(ls[id], l, mid, ql, qr);
    if (qr > mid) ans += query(rs[id], mid + 1, r, ql, qr);
    return ans;
}

void dfsSz(int u) {
    sz[u] = 1;
    for (auto v : G[u]) {
        dep[v] = dep[u] + 1;
        dfsSz(v);
        sz[u] += sz[v];
        if (sz[v] > sz[bigSon[u]]) bigSon[u] = v;
    }
}

void add(int u, int val) {
    modify(rt[w[u]], 1, n, dep[u], val);
    for (auto v : G[u]) {
        add(v, val);
    }
}

void calc(int u, int fa) {
    int dv = 2 * dep[fa] + k - dep[u];
    int wv = 2 * w[fa] - w[u];
    dv = min(dv, n);
    if (dv >= 1 && wv >= 0 && wv <= n) ans += 2ll * (ll)query(rt[wv], 1, n, 1, dv);
    for (auto v : G[u]) {
        calc(v, fa);
    }
}

void dfs(int u) {
    for (auto v : G[u]) {
        if (v == bigSon[u]) continue;
        dfs(v);
        add(v, -1);
    }
    if (bigSon[u]) dfs(bigSon[u]);

    for (auto v : G[u]) {
        if (v == bigSon[u]) continue;
        calc(v, u);
        add(v, 1);
    }
    modify(rt[w[u]], 1, n, dep[u], 1);
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    for (int i = 2, u; i <= n; ++i) {
        cin >> u;
        G[u].push_back(i);
    }
    dep[1] = 1;
    dfsSz(1);
    dfs(1);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int t = 1;
    while (t--) solve();
    return 0;
}

L - Who is the Champion

solved by lllllan. 00:20(+1)

题意： n支队伍两两之间会进行一场比赛，进球数比对方多的获得三分，进球数一样多双方均获得一分，否则不得分。找到所有队伍中得分最高的队伍，如果存在多支队伍得分相同，则找到单场进球数最多的队伍；如果还存在多支队伍单场最高进球数相同，则输出play-offs

题解： 按题意得分规则模拟即可

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 107;

int n;
int G[maxn][maxn];
int p[maxn];
int g[maxn];

int cmp(int a, int b) { return a > b; }

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", G[i] + j);
            //   g[i] += G[i][j];
            g[i] = max(g[i], G[i][j]);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int x = G[i][j];
            int y = G[j][i];

            if (x > y)
                p[i] += 3;
            else if (x < y)
                p[j] += 3;
            else
                p[i]++, p[j]++;
        }
    }

    int maxx = 1;
    int flag = 1;
    for (int i = 2; i <= n; ++i) {
        if (p[i] > p[maxx]) {
            maxx = i;
            flag = 1;
        } else if (p[i] == p[maxx]) {
            if (g[i] > g[maxx]) {
                maxx = i;
                flag = 1;
            } else if (g[i] == g[maxx]) {
                flag = 0;
            }
        }
    }

    if (flag)
        printf("%d\n", maxx);
    else
        printf("play-offs\n");

    return 0;
}
文章目录
  1. B - A Funny Bipartite Graph
  2. C - And and Pair
  3. E - Bob’s Problem
  4. G. Eating Plan
  5. K. Tree
  6. L - Who is the Champion
|