2024昆明邀请赛

B 金牌

真是忙碌的一周！这个周末, 将会有 $n$ 场程序设竞赛同时进行。

每场竞赛将会从每 $k$ 支参加该竞赛的队伍中颁发一枚金牌。也就是说, 如果有 $t$ 支队伍参加竞赛, 将会颁发 $⌊ \frac{t}{k} ⌋$ 枚金牌, 其中 $⌊ x ⌋$ 是不超过 $x$ 的最大整数。目前第 $i$ 场竞赛有 $a_{i}$ 支队伍参加。
堡堡是一所大学的教练, 该大学有 $m$ 支队伍, 并且他还没有决定每支队伍应该参加哪场竞赛。请帮助他为每支队伍分配一场竞赛，使得所有竞赛颁发的金牌总数最多。

贪心

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1), yu(n + 1);
    int sum = 0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];sum += a[i] / k;yu[i] = a[i] % k;
    }
    int m;cin >> m;
    sort(yu.begin() + 1, yu.end(), greater<int>());
    for (int i = 1;i <= n;i++) {
        if (m >= k - yu[i])sum++, m -= k - yu[i];
    }
    cout << sum + m / k << '\n';
}

G 乐观向上

求字典序最小的序列 $p_{0}, p_{1}, p_{2} \dots, p_{n - 1}$ , 该序列是 $0, 1, 2, \dots, (n - 1)$ 的一个排列, 且满足以下限制:

对于所有 $0 \leq i < n$ , 都有 $p_{0} \oplus p_{1} \oplus \dots \oplus p_{i} > 0$ 。

void solve() {
    int n;cin >> n;
    if (n % 4 == 0 || n == 1) {
        cout << "impossible\n";return;
    }
    cout << "1 0 ";
    for (int i = 2;i < n;i++) {
        if (i % 4 == 0) {
            cout << i - 1 << ' ';continue;
        }
        if (i % 4 == 3) {
            cout << i + 1 << " ";continue;
        }
        cout << i << " ";
    }
    cout << '\n';
}

I 左移 2

给定一个由小写字母组成的字符串, 称该字符串是美丽的, 若字符串中每一对相邻的字符都不相同。

给定由小写英文字母组成的, 长度为 $n$ 的字符串 $S = s_{0} s_{1} \dots s_{n - 1}$ , 令 $f (S, d)$ 表示将 $S$ 左移 $d$ 次后获得的字符串。也就是说 $f (S, d) = s_{(d + 0) mod n} s_{(d + 1) mod n} \dots s_{(d + n - 1) mod n}$ 。

令 $g (S, d)$ 表示将 $f (S, d)$ 变得美丽的最小操作次数。每次操作中, 您可以将 $f (S, d)$ 中的任意一个字符改为任意小写字母。
找到一个非负整数 $d$ 最小化 $g (S, d)$ , 并输出这个最小化的值。

Solution:
容易知道的是：若将这个字符串看作环形字符串，那么在这个环形字符串中相同的各段中只要出现了偶数，答案就可以割掉一个。

void solve() {
    string s;cin >> s;
    vector<int> a;
    int cnt = 1;
    for (int i = 1;i < s.size();i++) {
        if (s[i] == s[i - 1]) {
            cnt++;
        } else {
            a.push_back(cnt);
            cnt = 1;
        }
    }
    a.push_back(cnt);
    if (a.size() == 1) {
        cout << a[0] / 2 << '\n';return;
    }
    if (s[0] == s[s.size() - 1]) {
        a[0] += a.back();a.pop_back();
    }
    int ans = 0, ok = 0;
    for (auto x : a) {
        if (x % 2 == 0)ok = 1;
        ans += x / 2;
    }
    cout << ans - ok << '\n';
}

A 两星级竞赛

教育专家们出于某种原因, 准备对 $n$ 项竞赛进行评级。专家们已经决定了每项竞赛的评级结果, 其中第 $i$ 项竞赛被评为 $s_{i}$ 星级竞赛。

据说每项竞赛都会依据 $m$ 种属性进行评级, 其中第 $i$ 项竞赛的第 $j$ 种属性记为 $p_{i, j}$ , 每种属性的取值范围从 0 到 $k$ (含两端)。一项竞赛的分数是其所有 $m$ 种属性的总和。也就是说, 令 $v_{i}$ 表示第 $i$ 项竞赛的分数, 我们有 $v_{i} = \sum_{j = 1}^{m} p_{i, j}$ 。

如果一项星级更高的赛事有更高的分数, 看起来会比较自然。专家们要求, 对于任意两项竞赛 $1 \leq i, j \leq n$ , 若 $s_{i} > s_{j}$ , 则必须有 $v_{i} > v_{j}$ 。不幸的是, 专家们忘了采集一些竞赛部分 (甚至全部）属性的数据。作为专家们的助手, 您被要求填充这些不存在的属性值, 使得上述限制条件对任意两项竞赛都成立。

从小到大贪心即可，注意一个 trick：如何将下标还原？ $\to$ 逆向 sort 即可。

#define int long long
void solve() {
    int n, m, k;cin >> n >> m >> k;

    vector<int> s(n + 1);
    vector<vector<int>> v(n + 1, vector<int>(m + 4));

    for (int i = 1;i <= n;i++) {
        cin >> s[i];v[i][0] = s[i];
        int sum = 0, cnt = 0;
        for (int j = 1;j <= m;j++) {
            cin >> v[i][j];
            if (v[i][j] != -1) {
                sum += v[i][j];
            } else {
                cnt++;
            }
        }
        v[i][m + 1] = sum;
        v[i][m + 2] = cnt;
        v[i][m + 3] = i;
    }
    sort(v.begin(), v.end(), [](auto x, auto y) {
        return x[0] < y[0];
        });

    int last = -1, cur = -1;
    for (int i = 1;i <= n;i++) {
        if (v[i][0] != v[i - 1][0]) {
            last = cur;
        }

        int x = v[i][m + 1] - last - 1;
        if (x >= 0) {
            for (int j = 1;j <= m;j++) {
                if (v[i][j] == -1) {
                    v[i][j] = 0;
                }
            }
        } else {
            x = -x;
            if (v[i][m + 2] * k + v[i][m + 1] <= last) {
                cout << "No\n";return;
            }
            for (int j = 1;j <= m;j++) {
                if (v[i][j] == -1) {
                    v[i][j] = min(k, x);
                    x -= v[i][j];
                }
            }
        }
        int sum = 0;
        for (int j = 1;j <= m;j++) {
            sum += v[i][j];
        }
        cur = max(cur, sum);
    }
    cout << "Yes\n";

    sort(v.begin(), v.end(), [&](auto x, auto y) {
        return x[m + 3] < y[m + 3];
        });

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << v[i][j] << " \n"[j == m];
        }
    }
}

E 学而时习之

给定长度为 $n$ 的正整数序列 $a_{1}, a_{2}, \dots, a_{n}$ 以及一个非负整数 $k$ , 您可以执行以下操作至多一次:

选择两个整数 $l$ 和 $r$ 满足 $1 \leq l \leq r \leq n$ , 之后对于每个 $l \leq i \leq r$ , 将 $a_{i}$ 变为 $(a_{i} + k)$ 。

即区间 $[l, r]$ 整体加 $k$ ，要求最大化整个序列的最大公因数。

差分思想+思维

暴力：发现这个题目对于差分数组只会涉及到两个下标，若纯差分，则只需要枚举差分数组中的两个下标即可。只是时间复杂度为 $O (n^{3} \log n)$ ，必然超时。

void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1), dif(n + 2);
    int ans = a[1];
    for (int i = 1;i <= n;i++)cin >> a[i], ans = __gcd(ans, a[i]);
    for (int i = 1;i <= n;i++)dif[i] = a[i] - a[i - 1];
    
    for (int i = 1;i <= n;i++) {
        for (int j = i;j <= n;j++) {
            dif[i] += k;dif[j + 1] -= k;
            int res = dif[1];
            for (int k = 1;k <= n;k++) {
                res = __gcd(dif[k], res);
            }
            ans = max(ans, abs(res));

            dif[i] -= k;dif[j + 1] += k;
        }
    }
    cout << ans << '\n';
}

Solution：这个题目可以将 $[1, n]$ 分为 4 个部分： $[1, l - 1], [l, r - 1], r, [r + 1, n]$

答案为 $gcd (a_{1}, a_{2}, \dots a_{l - 1}), gcd (| a_{l} - a_{l + 1} |, \dots, | a_{r - 1} - a_{r} |), a_{r} + k, gcd (a_{r + 1}, \dots a_{n})$ 这四个数的 gcd。

对于前缀和后缀的 gcd 和之前结果相比改变了的点不会很多，依次枚举即可。

方法不止一种，关键在于想到使得 gcd 改变的数量很少的特性。

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    if (n == 1) {
        cout << k + a[1] << '\n';return;
    }

    unordered_set<int>s1, s2;
    s1.insert(1);
    s2.insert(n);
    int g = a[1];
    for (int i = 1;i <= n;i++) {
        int gg = g;
        g = __gcd(g, a[i]);
        if (gg != g) {
            s1.insert(i);
        }
    }

    g = a[n];
    for (int i = n;i >= 1;i--) {
        int gg = g;
        g = __gcd(g, a[i]);
        if (gg != g) {
            s2.insert(i);
        }
    }

    vector<int> pre(n + 1), suf(n + 1);
    pre[1] = a[1];suf[n] = a[n];
    for (int i = 2;i <= n;i++) {
        pre[i] = __gcd(pre[i - 1], a[i]);
    }
    for (int i = n - 1;i >= 1;i--) {
        suf[i] = __gcd(suf[i + 1], a[i]);
    }

    int ans = pre[n];
    for (auto l : s1) {
        for (auto r : s2) {
            if (l <= r) {
                int x = __gcd(pre[l - 1], suf[r + 1]);
                if (l == 1) {
                    x = suf[r + 1];
                }
                if (r == n) {
                    x = pre[l - 1];
                }

                int res = l != r ? abs(a[l] - a[l + 1]) : a[r] + k;
                for (int i = l + 1;i <= r - 1;i++) {
                    res = __gcd(res, abs(a[i] - a[i + 1]));
                }
                int y = __gcd(res, a[r] + k);
                if (l == 1 && r == n) {
                    x = y;
                }
                ans = max(ans, __gcd(x, y));
            }
        }
    }
    cout << ans << '\n';
}

M 意大利美食

堡堡为您准备了一份披萨！这个披萨是一个凸多边形，每条饼边里都有芝士夹心。但这些夹心边很脆弱，导致切披萨的时候只能经过多边形的顶点，而不能从边的中间切开。

不幸的是，披萨上有一片您肯定不喜欢的, 巨大的圆形菠夢片。

求沿着直线切一刀之后, 可以获得的最大的没有菠萝的披萨的面积。称一块披萨上没有菠萝, 当且仅当菠萝没有任何部分严格位于披萨块内。也就是说, 菠萝和披萨的相交面积为 0 。

![](/img/user/ZZZ-Misc/Z-Attachment/images-old-ACM/Pasted image 20240529152421.png)

(挖坑...)

J 冲向黄金城

某个国家有 $n$ 座城市以及 $m$ 条连接城市的双向铁路。第 $i$ 条铁路由第 $c_{i}$ 家铁路公司运营，铁路的长度
是 $l_{i} \circ$
您想要从城市 1 开始进行全国旅行。您已经为旅行购买了 $k$ 张车票。第 $i$ 张车票可以记为两个整数 $a_{i}$ 和 $b_{i}$ ，表示如果您使用了这张车票，就可以一次性经过若干条均由公司 $a_{i}$ 运营的，且总长度不超过 $b_{i}$ 的铁路。即使您使用了车票，也可以选择待在当前城市。您同时只能使用一张车票，且每张车票只能使用一次。
由于决定车票的使用顺序太麻烦了，您打算直接按现有的顺序使用车票。更正式地，您将执行 $k$ 次操作。在第 $i$ 次操作中，您可以选择待在当前的城市 $u;$ 也可以选择一座不同的城市 $v$ ，满足城市 $u$ 和 $v$ 之间存在一条路径，且路径上的所有铁路均由公司 $a_{i}$ 运营，且铁路总长不超过 $b_{i}$ ，然后移动到城市 $v$ 。对于每座城市，判断在使用 $k$ 张车票之后能否到达该城市。

L 漫步野径

堡堡正在一块无穷大的二维平面上散步。对于平面上每个满足 $x$ 和 $y$ 均是整数的点 $(x, y)$ ，都有一条双向小径连接点 $(x, y)$ 和 $(x + 1, y)$ ，还有另一条双向小径连接点 $(x, y)$ 和 $(x, y + 1)$ 。另外，还有 $n$ 条额外的双向小径，其中第 $i$ 条连接点 $(x_{i}, y_{i})$ 和 $(x_{i} + 1, y_{i} + 1)$ 。
堡堡只能沿着小径移动。令 $f (x, y)$ 表示堡堡从点 (0，0)出发到达点 $(x, y)$ 最少需要经过几条小径。给定
两个整数 $p$ 和 $q$ ，计算

\sum_{x = 0}^{p} \sum_{y = 0}^{q} f (x, y)