2015 ICPC EC-Final (Gym 103957) 训练记录

正式训练

A. Boxes and Balls

易知答案一定可以表示为前 $m$ 个自然数的和。二分找出最大的 $m$ 即可。

L. Multiplication Table

实际上整个矩阵被左上角的坐标 $(x, y)$ 完全确定，而每个给出的数实际上是一个形如 $(x + i)(y + j) = a_{i, j}$ 的条件。

若矩阵中全是 ?，直接输出 Yes 即可。
若非 ? 的数至少有两个，则一定可以通过解二次方程确定出至多两组可能的 $(x, y)$，分别验证即可。
若非 ? 的数有且仅有一个，确定其是否可以被分解为两个不太小的因子相乘即可。

上面的后两种情况均可通过枚举因子实现。时间复杂度 $O(T \cdot RC \sqrt{V})$。

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

using LL = long long;
const int MX = 1003;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for(int _ = 1; _ <= T; _++) {
        int r, c;
        cin >> r >> c;

        vector<tuple<int, int, int>> info;
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                string qwq;
                cin >> qwq;
                if(qwq != "?") {
                    info.emplace_back(i, j, atoi(qwq.c_str()));
                }
            }
        }

        auto check = [&] (int x, int y) {
            for(auto [i, j, val] : info) {
                if((LL)(x + i) * (y + j) != val) {
                    return false;
                }
            }
            return true;
        };

        if(info.empty()) {
            printf("Case #%d: Yes\n", _);
        } else if(info.size() == 1) {
            bool result = false;
            int i, j, target;
            tie(i, j, target) = info[0];
            for(int t = min(i, j) + 1; t * (max(i, j) + 1) <= target; t++) {
                if(target % t == 0) {
                    result = true;
                    break;
                }
            }
            if(result) {
                printf("Case #%d: Yes\n", _);
            } else {
                printf("Case #%d: No\n", _);
            }
        } else {
            bool result = false;
            int i, j, target;
            tie(i, j, target) = info[0];

            int p, q, trigger;
            tie(p, q, trigger) = info[1];
            for(int t = min(i, j) + 1; t * (max(i, j) + 1) <= target; t++) {
                if(target % t != 0) {
                    continue;
                }
                int s = target / t;
                // s, t
                if((LL)(s - i + p) * (t - j + q) == trigger) {
                    if(check(s - i, t - j)) {
                        result = true;
                        break;
                    }
                }
                // t, s
                if((LL)(t - i + p) * (s - j + q) == trigger) {
                    if(check(t - i, s - j)) {
                        result = true;
                        break;
                    }
                }
            }

            if(result) {
                printf("Case #%d: Yes\n", _);
            } else {
                printf("Case #%d: No\n", _);
            }
        }
    }
    return 0;
}

B. Business Cycle

我们考虑沿着环走完一整圈会发生什么。不妨设 $S$ 为环上所有数的和，$m$ 为环上前缀和中的最小值，即 $\displaystyle\min_{1 \leq k \leq n} \sum_{i=1}^{k} V_i$。若我们当前手里的钱是 $x$，一圈之后手里的钱数 $f(x)$ 可表示为 $$ f(x) = \begin{cases} x + S, & x + m \geq 0 \newline S - m, & x + m < 0 \end{cases} $$ 处理完不是整圈的部分之后暴力沿着 $f$ 的反函数往回跳即可。

这里需要注意有两种情况。不妨设 $p = kn + r$，我们既可以选择跳不超过 $k$ 圈之后走一个不超过 $r$ 的弧段，又可以选择跳不超过 $k - 1$ 圈之后走一个长度任意的弧段。

时间复杂度 $O(Tn)$。

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

using LL = long long;

LL solve() {
    int n;
    LL g, p;
    cin >> n >> g >> p;

    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    LL sum = 0, min_sum = numeric_limits<LL>::max();
    for(int val : arr) {
        sum += val;
        if(sum < min_sum) {
            min_sum = sum;
        }
    }

    LL max_round = p / n;
    LL ans1 = g, ans2 = g;
    for(int i = n - 1; i >= 0; i--) {
        ans2 = min(g, max(0LL, ans2 - arr[i]));
        if(i < p % n) {
            ans1 = min(g, max(0LL, ans1 - arr[i]));
        }
    }

    if(max_round == 0) {
        return ans1;
    }

    if(sum <= 0) {
        if(ans1 <= sum - min_sum) {
            ans1 = 0;
        }
        if(max_round > 1 && ans2 <= sum - min_sum) {
            ans2 = 0;
        }
        return min(ans1, ans2);
    }

    if(ans1 / sum < max_round) {
        ans1 = 0;
    } else {
        ans1 -= max_round * sum;
    }

    if(ans2 / sum < max_round - 1) {
        ans2 = 0;
    } else {
        ans2 -= (max_round - 1) * sum;
    }

    LL ans = min(ans1, ans2);
    if(ans <= -min_sum || ans <= 0) {
        return 0;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for(int _ = 1; _ <= T; _++) {
        printf("Case #%d: %lld\n", _, solve());
    }
    return 0;
}

赛后补题

J. Dome and Steles

这个题其实训练还剩 80min 的时候就想出做法了，不过因为没有完全想清楚所有细节导致没写出来。

可以发现每个方块会给半径贡献一个 $\left( d^2 + a^2 + \dfrac{b^2}{4} \right)^{1/2}$ 的下界，其中 $d$ 是球心到方块外立面的距离。

显然，对每个方块取长宽中较小的作为 $a$ 是更好的。其次，当半径确定后，$a^2 + \dfrac{b^2}{4}$ 越大的方块越靠近球心。

我们的想法是二分答案，然后判定能不能放得下所有方块。判定的话注意到球心一定会被某个方块压住，不妨设球心离这个方块两边的长度分别为 $l$ 和 $r$，然后左半序列和右半序列会分别给出 $l$ 和 $r$ 的上界。我们最后只需要判断这两个上界是否与 $l + r = 1$ 相容即可。

时间复杂度 $O(T n \log n)$。

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

using LL = long long;
using LD = long double;

int read() {
    string str;
    cin >> str;
    str.erase(str.length() - 5, 1);
    return atoi(str.c_str()) * 2;
}

LL sqr(LL x) { return x * x; }

LD solve() {
    int n;
    cin >> n;

    vector<LL> bricks;
    for(int i = 1; i <= n; i++) {
        int a = read(), b = read();
        if(a < b) {
            swap(a, b);
        }
        LL chr = (LL)a * a / 4 + (LL)b * b;
        bricks.push_back(chr);
    }

    sort(bricks.begin(), bricks.end(), greater<LL>());

    LD l = sqrtl(bricks[0] / 4e8), r = 1.5e5;
    for(int i = 1; i <= 40; i++) {
        LD mid = (l + r) / 2, tmp = mid * mid;
        
        long double supr = 0.5;
        for(int i = 1; 2 * i - 1 < bricks.size(); i++) {
            supr = min(supr, sqrtl(tmp - bricks[2 * i - 1] / 4e8) - i);
        }

        long double supl = 1;
        for(int i = 0; 2 * i < bricks.size(); i++) {
            supl = min(supl, sqrtl(tmp - bricks[2 * i] / 4e8) - i);
        }

        if(supl + supr < 1 - 1e-6) {
            l = mid;
        } else {
            r = mid;
        }
    }

    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for(int _ = 1; _ <= t; _++) {
        printf("Case #%d: %.9Lf\n", _, solve());
    }
    return 0;
}

I. Champions League

很莫名其妙的一个状压 DP。由于对来自相同国家的球队分组有一个很麻烦的规则，我们自然可以想到逐个国家来处理。

同一国家的同一档次的球队在 DP 的过程中很难区分开来，我们索性在 DP 过程中只分配集合，最后再把那些阶乘统一乘进去。这样一来每个国家对 DP 的更新就可以通过逐档次枚举分组来实现。

注意到每个档次枚举的代价至多是 $\displaystyle \binom{8}{4} = 70$，考虑到同一国家的球队至多有 $5$ 个，每个国家的转移代价实际上只有 $10^4$ 数量级。因此总复杂度是可以接受的。

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

using LL = long long;

union data_t {
    unsigned mask;
    unsigned char ranks[4];
};

vector<unsigned> masks[6];

LL solve() {
    map<string, int> teams_id;
    map<int, array<int, 4>> teams_info;

    LL factor = 1;
    for(int i = 0; i <= 3; i++) {
        for(int j = 1; j <= 8; j++) {
            string str;
            cin >> str;
            if(!teams_id.count(str)) {
                teams_id[str] = teams_info.size();
            }
            factor *= ++teams_info[teams_id[str]][i];
        }
    }

    map<unsigned, LL> lst, cur;
    lst[0] = 1;

    for(const auto &[_, team] : teams_info) {
        for(const auto &[mask, val] : lst) {
            data_t S;
            S.mask = mask;

            function<void(size_t, unsigned)> dfs = 
                [&] (size_t rnk, unsigned groups) {
                    if(rnk == 4) {
                        cur[S.mask] += val;
                        return;
                    }
                    for(unsigned new_mask : masks[team[rnk]]) {
                        if(new_mask & (groups | S.ranks[rnk])) {
                            continue;
                        }

                        unsigned tmp = new_mask | groups;
                        if(abs(popcount(tmp & 0x0F) - popcount(tmp & 0xF0)) > 1) {
                            continue;
                        }

                        S.ranks[rnk] ^= new_mask;
                        dfs(rnk + 1, tmp);
                        S.ranks[rnk] ^= new_mask;
                    }
                };

            dfs(0, 0);
        }
        lst = cur;
        cur.clear();
    }

    return lst[-1] * factor;
}

int main() {
    for(unsigned i = 0; i < (1 << 8); i++) {
        int pc = popcount(i);
        if(pc <= 5) {
            masks[pc].push_back(i);
        }
    }

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for(int _ = 1; _ <= t; _++) {
        printf("Case #%d: %lld\n", _, solve());
    }
    return 0;
}

E. Colorful Floor

实际上手做了之后感觉两三句话说不清楚，因此新开了一篇文章专门讲这个。

由于期末考试，南京站之后就没写过代码。南京站我们队打得稀烂，再往前杭州站和南京站之间的那次训练也因为我得病被迫取消。这么其实算来已经有一个多月没好好写代码了。

这次训练打得磕磕绊绊的，先权当找回状态吧。希望之后能好一些。

补题的话 DFM 训练时候队友解决了，其他题感觉赛场上我们也不太可能做出来，就先咕了。