C - Constellations

我们的大方向肯定是用某种数据结构维护 distance 的，所以，我们考虑能否用 std::priority_queue\tt std::priority\_queue 进行维护。

很快我们发现一个问题是，假设当前 (u,v,du,v)(u,v,d_{u,v}) 是最小的，我把他们两个合并之后，应该如何计算受到影响的 distance？也就是，当我合并了 u,vu,v 之后（假设合并的新星系是 ww），我该怎么更新 di,w,i<wd_{i,w},i\lt w（这里 i<wi\lt w 是因为可能其他星系的合并结果保存在 [n+1,w−1][n+1, w-1] 里）？

所以这时候我们得将式子拆开为两部分，一部分是分母的 size\tt size，另一部分是分子的 f(A,B)=∑a∈A∑b∈B∥a−b∥2f(A,B)=\sum_{a\in A}\sum_{b\in B} \|a-b\|^2. 我们发现分子具有可加性，也就是如果我们想更新 f(i,A+B)f(i,A+B)，只需要 f(i,A+B)=f(i,A)+f(i,B)f(i,A+B)=f(i,A)+f(i,B) 即可，而 size\tt size 也具有可加性。

所以这就提示我们需要分别维护 f(i,j)f(i,j) 和 size\tt size. 每次合并完成后（w←u+vw\gets u+v），需要 O(n)O(n) 遍历 i<wi\lt w 以更新 f(i,w)=f(i,u)+f(i,v)f(i,w)=f(i,u)+f(i,v)，并将他们全部插入 std::priority_queue\tt std::priority\_queue. 时间复杂度 O(n2log⁡n)O(n^2\log n).

此外，题目中的“按时间合并”的条件可以转化为：将合并后的新星系编号成 [n+1,2n−1][n+1, 2n-1]，这样时间的条件就变成了三元数组的偏序关系 (dis[i,j],i,j)\tt (dis[i,j], i, j) 其中 i<ji\lt j.

AC Code
 
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
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using pts = std::complex<ll>;
constexpr int N = 2005;

struct node {
    ll up, div;
    int u, v;
};
auto comp = [](node a, node b) {
    ll L = a.up * b.div, R = b.up * a.div;
    if (L != R) return L > R;
    if (a.u != b.u) return a.u > b.u;
    else return a.v > b.v;
};

int n;
ll d[N * 2][N * 2];
int mark[N * 2], size[N * 2];
pts p[N];
std::priority_queue<node, std::vector<node>, decltype(comp)> q(comp);

int main() {
    std::cin >> n;
    for (int i = 1, u, v; i <= n; i++) {
        std::cin >> u >> v;
        p[i] = {u, v};
    }
    for (int i = 1; i <= n; i++) {
        size[i] = 1;
        for (int j = i + 1; j <= n; j++) {
            d[i][j] = d[j][i] = std::norm(p[i] - p[j]);
            q.push({d[i][j], 1, i, j});
        }
    }

    for (int w = 1 + n; w <= 2 * n - 1; w++) {
        while (!q.empty()) {
            auto [a, b, u, v] = q.top();
            q.pop();

            if (mark[u] || mark[v]) continue;
            mark[u] = mark[v] = 1;
            size[w] = size[u] + size[v];

            std::cout << size[w] << "\n";

            for (int i = 1; i < w; i++) {
                if (mark[i]) continue;
                d[i][w] = d[w][i] = d[u][i] + d[v][i];
                q.push({d[i][w], size[i] * size[w], i, w});
            }

            break;
        }
    }
}

D - Deforestation

赛时理解错题意了，以为可以从树上切下相邻连续的树枝……比如说 W=5W=5，一个点延伸出 3,2,4,1,5\tt 3,2,4,1,5 五根树枝，实际上并不能切成 33 段（(3,2),(4,1),(5)(3,2),(4,1),(5)），只能切成 44 段（(3),(4),(5),(2,1)(3),(4),(5),(2,1)）

我们考虑从叶子往根的过程，在叶子处，我们首先把树枝切成 li/wl_i/w 段，剩下 limod  wl_i \mod w 的剩余 rir_i。然后来到叶子的父亲节点，我们要做的是让一部分叶子的 rir_i 和父亲的树枝 lil_i 放一起被切下来，让令一部分叶子的 rir_i 单独被切下来，并且使单独被切下来的 rir_i 尽可能少。

所以可以得出一个贪心的结论：在节点处，把子节点的 rir_i 从大往小排序，不断放入 rir_i，如果超过 ww 则扔掉背包里最大的 rir_i 让他被单独切掉。最后还留在背包里的 ∑jrj\sum_j r_j 和父亲节点的 lil_i 放在一起考虑，最后在父亲节点处还会剩下 (li+∑jrj)mod  w(l_i+\sum_j r_j)\mod w.

注意，如果 rrootr_{root} 不为 00，这个部分需要单独装一个背包（即答案 +1+1）。时间复杂度 O(nlog⁡n)O(n\log n)

AC Code
 
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 ll = long long;
using pil = std::pair<int, ll>;
constexpr int N = 1e5 + 10;

int n{1};
ll w, a[N], rest[N];
std::vector<int> G[N];

void input(int id) {
    int c;
    std::cin >> a[id] >> c;
    for (int i = 1; i <= c; i++) {
        n++;
        G[id].push_back(n);
        input(n);
    }
}

int main() {
    std::cin >> w;
    input(1);

    ll ans = 0;
    auto dfs = [&](auto F, int u) -> void {
        rest[u] = a[u];
        std::vector<ll> ws;
        for (auto v : G[u]) {
            F(F, v);
            ws.push_back(rest[v]);
        }

        std::sort(ws.begin(), ws.end(), std::greater<>());

        ll sum = 0;
        int d = 0;
        for (int i = 0; i < ws.size(); i++) {
            sum += ws[i];
            if (sum > w) sum -= ws[d++], ans++;
        }
        sum += a[u];
        ans += sum / w;
        rest[u] = sum % w;
    };
    dfs(dfs, 1);

    std::cout << ans + (rest[1] ? 1 : 0) << "\n";
}

E - Denormalization

蚌埠住了，居然真的是暴力

我们直接枚举 min⁡xi\min x_i 对应的是哪个整数 tt，然后 O(n)O(n) 计算 std::round\tt std::round 之后的累计浮点误差 s=∑iΔs=\sum_i\Delta。那么如果 tt 是答案对应的整数，那么 ss 应该很小。

所以我们 O(V)O(V) 枚举之后，O(n)O(n) 计算累计误差，排序后选择最小的那个即可。时间复杂度 O(nV)O(nV)

AC Code
 
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
#include <bits/stdc++.h>
using ld = long double;
constexpr int N = 1e4 + 5;
constexpr int V = 1e4;
constexpr ld eps = 1e-4;

struct number {
    ld v;
    int id;
    bool operator<(number x) const { return v < x.v; }
} a[N];

int n;
int ans[N], t[N];
ld tmp[N];

void construct(int v) {
    t[1] = v, tmp[1] = v;
    for (int i = 1; i <= n; i++) {
        tmp[i] = tmp[1] * a[i].v / a[1].v;
        t[i] = std::round(tmp[i]);
    }

    int g = 0;
    for (int i = 1; i <= n; i++) g = std::gcd(g, t[i]);
    for (int i = 1; i <= n; i++) t[i] /= g, ans[a[i].id] = t[i];
}

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i].v, a[i].id = i;
    std::sort(a + 1, a + 1 + n);

    bool found = false;
    std::vector<std::pair<ld, int>> c;
    for (int v = 1; v <= V; v++) {
        ld diff = 0;
        tmp[1] = v, t[1] = v;
        for (int i = 2; i <= n; i++) {
            tmp[i] = tmp[1] * a[i].v / a[1].v;
            t[i] = std::round(tmp[i]);
            diff += std::abs(tmp[i] - t[i]);
        }

        c.push_back({diff, v});
    }
    std::sort(c.begin(), c.end());
    construct(c[0].second);
    for (int i = 1; i <= n; i++) std::cout << ans[i] << " \n"[i == n];
}

F - Differences

挺好的题，没想到哈希还可以这么用。

考虑每一位 ii 和字符 cc，令 f(i,c)={ x:xi=c }f(i,c)=\set{x:x_i=c}，那么我们就想找 x′x' 使得

∀i,∣∑c∈{ A,B,C,D }f(i,c)−f(i,xi′)∣=k \forall i,|\sum_{c\in\set{\texttt{A,B,C,D}}}f(i,c)-f(i,x'_i)|=k

那么我们怎么快速检查是否 =k=k 呢？考虑哈希，令

g(i,c)=∑j∈f(i,c)pj(modM) g(i,c)=\sum_{j\in f(i,c)} p^j \pmod M

则 =k=k 的条件可以通过对 ∑i\sum_i 求和得到

∑i∣∑c∈{ A,B,C,D }g(i,c)−g(i,xi′)∣=k⋅∑ipi−k⋅px′(modM) \sum_i \Big|\sum_{c\in\set{\texttt{A,B,C,D}}}g(i,c)-g(i,x'_i)\Big|=k\cdot\sum_i p^i - k\cdot p^{x'} \pmod M

时间复杂度 O(nm)O(nm)

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

template <int MOD = 998244353>
class Modulo {
  private:
    static int Pow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) { res = (1ll * res * a) % MOD; }
            b >>= 1, a = (1ll * a * a) % MOD;
        }
        return res;
    }
    static int Inv(int x) { return Pow(x, MOD - 2); }

  public:
    int num;
    /*====================*/
    Modulo(long long temp = 0) { num = temp % MOD; }
    Modulo(const Modulo &temp) { num = temp.num; }
    /*====================*/
    constexpr friend Modulo operator+(const Modulo &a, const Modulo &b) { return Modulo((a.num + b.num) >= MOD ? a.num + b.num - MOD : a.num + b.num); }
    constexpr friend Modulo operator-(const Modulo &a, const Modulo &b) { return Modulo((a.num - b.num + MOD) >= MOD ? a.num - b.num : a.num - b.num + MOD); }
    constexpr friend Modulo operator*(const Modulo &a, const Modulo &b) { return Modulo(1ll * a.num * b.num % MOD); }
    constexpr friend Modulo operator/(const Modulo &a, const Modulo &b) { return Modulo(1ll * a.num * Inv(b.num) % MOD); }
    constexpr friend Modulo operator%(const Modulo &a, const Modulo &b) { return a; }
    /*====================*/
    constexpr friend bool operator<(const Modulo &a, const Modulo &b) { return a.num < b.num; }
    constexpr friend bool operator==(const Modulo &a, const Modulo &b) { return a.num == b.num; }
    constexpr friend bool operator>(const Modulo &a, const Modulo &b) { return a.num > b.num; }
    constexpr friend bool operator<=(const Modulo &a, const Modulo &b) { return a.num <= b.num; }
    constexpr friend bool operator!=(const Modulo &a, const Modulo &b) { return a.num != b.num; }
    constexpr friend bool operator>=(const Modulo &a, const Modulo &b) { return a.num >= b.num; }
    /*====================*/
    constexpr void operator+=(const Modulo &x) {
        num = num + x.num;
        if (num >= MOD) num -= MOD;
    }
    constexpr void operator-=(const Modulo &x) {
        num = num - x.num + MOD;
        if (num >= MOD) num -= MOD;
    }
    constexpr void operator*=(const Modulo &x) { num = 1ll * num * x.num % MOD; }
    constexpr void operator/=(const Modulo &x) { num = 1ll * num * Inv(x.num) % MOD; }
    constexpr void operator%=(const Modulo &x) { num = num % x.num; }
    /*====================*/
    friend std::ostream &operator<<(std::ostream &output, Modulo integer) {
        output << integer.num;
        return output;
    }
    friend std::istream &operator>>(std::istream &input, Modulo &integer) {
        int temp;
        input >> temp;
        integer = (temp % MOD + MOD) % MOD;
        return input;
    }
};

using Z = Modulo<998244353>;
using Zn = Modulo<int(1e9 + 7)>;

constexpr int P = 34631;
constexpr int N = 1e5 + 10;

int n, m, k;
std::string a[N];
Zn p[N];
Zn v[N][5], sv[N];
// std::bitset<N> ok;

int main() {
    std::cin >> n >> m >> k;
    p[0] = 1;
    for (int i = 1; i < N; i++) p[i] = p[i - 1] * P;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        // ok.set(i);
        for (int j = 1; j <= m; j++) v[j][a[i][j - 1] - 'A'] += p[i];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < 4; j++) sv[i] += v[i][j];

    Zn tmp = 0;
    for (int i = 1; i <= n; i++) tmp += p[i];

    for (int x = 1; x <= n; x++) {
        std::vector<Zn> u(m + 1, 0);
        for (int j = 1; j <= m; j++) u[j] = sv[j] - v[j][a[x][j - 1] - 'A'];

        Zn sum = 0;
        for (int j = 1; j <= m; j++) sum += u[j];

        if (sum == tmp * k - p[x] * k) {
            std::cout << x << "\n";
            return 0;
        }
    }
}

L - Circuit Board Design

赛时把角度的上下界搞错了，假设以 aa 为根的子树分配到的角度范围是 [l,r][l,r]，那么 dfs 的时候，aa 的儿子应该按子树大小等比例划分 [l,r][l,r]，赛时把角度范围写成了 [angle−diff,angle+diff]\tt [angle - diff, angle + diff]，但实际应该是 [l,r]\tt [l,r]，不然的话，在角度的分界处可能会存在两个点很靠近。

如上图所示，灰色射线表示分配给 CC 子树的角度范围，如果 CC 的子树划分红色射线的角度范围，那么子树节点很可能跨过当初划定的灰色范围，导致错误。所以必须是绿色范围，而令绿色范围尽可能大，那么就是平行于两条灰色射线，即 [l,r]\tt [l,r]

假设以 rr 为根的树分配到的角度范围是 [L,R][L,R]，那么考虑 rr 的儿子 sis_i，我们令子树大小更大的 sis_i 分配更大的角度范围，然后递归即可。时间复杂度 O(n)O(n).

AC Code

实现使用了 C++ 的 std::complex\tt std::complex 作为点的表示，可以用 std::polar\tt std::polar 更加快捷地实现旋转。

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
#include <bits/stdc++.h>
using ld = long double;
using point = std::complex<ld>;
using vi = std::vector<int>;

constexpr int N = 1005;
const ld pi = std::acos((ld)-1.0);

int n, width[N];
point p[N];
vi G[N];

int main() {
    std::cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        std::cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }

    auto pre = [&](auto F, int u, int f) -> void {
        width[u] = 1;
        for (auto v : G[u]) {
            if (v == f) continue;
            F(F, v, u);
            width[u] += width[v];
        }
    };
    pre(pre, 1, 0);

    auto dfs = [&](auto F, int u, int f, ld l, ld r) -> void {
        ld slice = (r - l) / (width[u] - 1), al = l;
        for (auto v : G[u]) {
            if (v == f) continue;
            ld t = al + slice * width[v];
            p[v] = p[u] + std::polar(1.0L, (t + al) / 2);
            F(F, v, u, al, t);
            al = t;
        }
    };
    p[1] = {0, 0};
    dfs(dfs, 1, 0, 0, pi * 2);

    for (int i = 1; i <= n; i++) std::cout << std::setprecision(20) << std::fixed << p[i].real() << " " << p[i].imag() << "\n";
}

M - The Game

没啥好说的，纯模拟。需要注意：

  1. 当牌山打空时，还需要不断操作手牌直到无法操作；
  2. 每一堆牌山开头是有数字的（1,1,100,1001,1,100,100）；
  3. 每次要连续打两张牌才能摸牌。
AC Code
 
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
#include <bits/stdc++.h>

std::deque<int> pile;
std::vector<int> hand;
std::vector<int> row[4];

void draw() {
    if (pile.empty()) return;
    hand.push_back(pile.front());
    pile.pop_front();
}

bool backward(int r, int val) {
    if (r < 2) return val == row[r].back() - 10;
    else return val == row[r].back() + 10;
}

bool operate() {
    bool placed = false;
    std::vector<std::pair<int, int>> cand;
    for (int i = 0; i < hand.size(); i++) {
        for (int r = 0; r < 4; r++) {
            if (backward(r, hand[i])) {
                cand.push_back({i, r});
                placed = true;
                break;
            }

            if (cand.size() != 0) break;
        }
        if (cand.size() != 0) break;
    }
    for (auto [id, r] : cand) {
        // std::cerr << hand[id] << " is backwarded.\n";
        row[r].push_back(hand[id]);
        hand.erase(hand.begin() + id);
    }

    if (cand.size() != 0) return true;

    std::vector<std::tuple<int, int, int>> f;
    for (int i = 0; i < hand.size(); i++)
        for (int r = 0; r < 4; r++) {
            if (r < 2) {
                if (hand[i] > row[r].back()) f.push_back({std::abs(hand[i] - row[r].back()), i, r}), placed = true;
            } else {
                if (hand[i] < row[r].back()) f.push_back({std::abs(hand[i] - row[r].back()), i, r}), placed = true;
            }
        }

    if (f.empty()) return false;
    std::sort(f.begin(), f.end());

    auto [_, i, r] = *f.begin();
    row[r].push_back(hand[i]);
    hand.erase(hand.begin() + i);
    return true;
}

int main() {
    for (int i = 1, a; i <= 98; i++) std::cin >> a, pile.push_back(a);
    row[0].push_back(1), row[1].push_back(1);
    row[2].push_back(100), row[3].push_back(100);

    while (true) {
        while (hand.size() < 8) draw();
        if (hand.empty() || pile.empty()) break;

        bool res = operate();
        // if (!res) break;
        res &= operate();
        if (!res) break;
    }

    int p = hand.size();
    while (true) {
        if (!operate()) break;
        // if (hand.size() == p) break;
    }

    for (int r = 0; r < 4; r++) {
        for (auto i : row[r]) std::cout << i << " ";
        std::cout << "\n";
    }
    for (auto i : hand) std::cout << i << " ";
    std::cout << "\n";
    for (auto i : pile) std::cout << i << " ";
    std::cout << "\n";
}
ICPC/UCup/2025
License

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