2024昆明邀请赛

题解

B 金牌

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

每场竞赛将会从每 k 支参加该竞赛的队伍中颁发一枚金牌。也就是说, 如果有 t 支队伍参加竞赛, 将会颁发 tk 枚金牌, 其中 x 是不超过 x 的最大整数。目前第 i 场竞赛有 ai 支队伍参加。
堡堡是一所大学的教练, 该大学有 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 乐观向上

求字典序最小的序列 p0,p1,p2,pn1, 该序列是 0,1,2,,(n1) 的一个排列, 且满足以下限制:

对于所有 0i<n, 都有 p0p1pi>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=s0s1sn1, 令 f(S,d) 表示将 S 左移 d 次后获得的字符串。也就是说 f(S,d)=s(d+0)modns(d+1)modns(d+n1)modn

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 项竞赛被评为 si 星级竞赛。

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

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

从小到大贪心即可,注意一个 trick:如何将下标还原? 逆向 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 的正整数序列 a1,a2,,an 以及一个非负整数 k, 您可以执行以下操作至多一次:

选择两个整数 lr 满足 1lrn, 之后对于每个 lir, 将 ai 变为 (ai+k)

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

差分思想+思维

暴力:发现这个题目对于差分数组只会涉及到两个下标,若纯差分,则只需要枚举差分数组中的两个下标即可。只是时间复杂度为 O(n3logn),必然超时。

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,l1],[l,r1],r,[r+1,n]

答案为 gcd(a1,a2,al1),gcd(|alal+1|,,|ar1ar|),ar+k,gcd(ar+1,an) 这四个数的 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 条铁路由第 ci 家铁路公司运营,铁路的长度
li
您想要从城市 1 开始进行全国旅行。您已经为旅行购买了 k 张车票。第 i 张车票可以记为两个整数 aibi,表示如果您使用了这张车票,就可以一次性经过若干条均由公司 ai 运营的,且总长度不超过 bi 的铁路。即使您使用了车票,也可以选择待在当前城市。您同时只能使用一张车票,且每张车票只能使用一次。
由于决定车票的使用顺序太麻烦了,您打算直接按现有的顺序使用车票。更正式地,您将执行 k 次操作。在第 i 次操作中,您可以选择待在当前的城市 u; 也可以选择一座不同的城市 v,满足城市 uv 之间存在一条路径,且路径上的所有铁路均由公司 ai 运营,且铁路总长不超过 bi,然后移动到城市 v。对于每座城市,判断在使用 k 张车票之后能否到达该城市。

L 漫步野径

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

x=0py=0qf(x,y)

F 收集硬币