「题解」EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2)

Mohao2025/7/10大约 4 分钟

唉唉，某哈基詹太坏，利用我不熟悉 Codeforces 的赛制，恶意引导我赛程过半交一发已经 AC 了的题目。本来是上小分的，给哈基詹弄成掉小分了。被资本做局了吗……哈基詹，你这家伙。

比赛链接

A. Deranged Deletions

给定一个数组，让你任意地删除元素，判断是否能构造出一个「排序后的数组的每一个位置的元素与其原本的数组该位置元素不相同」的数组并输出答案。

我们考虑到可以删除任意多次，显然删成只存在一个逆序对是平凡解。如果一个逆序对也不存在，则该数组一定是单调不降的，也不存在可能的解。

B. Minimise Sum

给定一个数组，让你最多执行一次操作「选定 $i,\ j\ (i<j)$ ，令 $a_i:=a_i+a_j$ ，然后使 $a_j=0$ 」。问最小化前缀最小值的和。

因为我们只需要考虑前缀最小值，显然只会有两种情况：

当 $a_1>a_2$ 时，选定 $i = 1, j = 2$ 操作，这样值就是 $a_1+a_2$ ；
当 $a_1<a_2$ 时，选定 $i=2,j=3$ 操作，此时值为 $2a_1$ 。

C. Subset Multiplication

给定一个数组 $a$ ，其中每一个 $a_i$ 都能整除 $a_{i+1}$ ，然后给定一个数组 $b$ ，其在 $a$ 数组的基础上把某几个元素乘上了 $x$ 。已知 $b$ 求 $a$ 。

不难看出，如果存在 $b_{i+1}\bmod b_i \neq0$ ，那么第 $i$ 项一定是被乘过 $x$ 的。因此我们的 $x$ 就是所有 $b_i/\gcd(b_i,b_{i+1})$ 的最小公倍数。

因为在此时： $a_i=b_i/x$ ， $a_{i+1}=b_{i+1}$ ， $a_{i+1}\bmod a_i=0$ 可以得出 $x\times b_{i+1}\equiv0\pmod{b_i}$ 即 $b_i|b_{i+1}x$

我们在两侧同时约去最大公约数，有：

\frac{b_i}{gcd(b_i,b_{i+1})}|x

既然所有的上面那坨东西都能整除 $x$ ， $x$ 自然就是他们的最小公倍数。

D. Make a Palindrome

理论上来说这是一道蓝题，但是我那天晚上被🐙🫁弄哈气了所以没过捏。

给定一个数组和一个整数 $k$ ，可以在这个数组中任取长度大于等于 $k$ 的区间任意地删除其中一个第 $k$ 小的元素。判断是否能在任意多次删除后形成一个回文数组。

显然对于 $k=1$ 的情况我们把所有数组元素都图图掉的做法。然后我们再想想其他情况。

我们通过观察可以发现，对于整个数组最小的 $k-1$ 个元素，无论怎么选择我们都是删不掉的。我们令 $x$ 是第 $k$ 小的元素的值，所有 $a_i>x$ 是一定可以删掉的，所有 $a_i<x$ 都是删不掉的，我们只需要考虑 $a_i=x$ 的情况即可。

我们记有 cnt 个元素等于 $x$ ，然后使用双指针判断是否 $b_l$ 是否等于 $b_r$ 即可，如果 $b_l=b_r$ ，我们直接 $l:=l+1,r:=r-1$ 移动，否则若 $b_l=x \lor b_r=x$ ，我们删除 $x$ 的同时记录删除的次数即可，再否则就是无解。综合判断后输出即可。

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (k == 1) {
        cout << "YES\n";
        return;
    }
    auto b = a;
    rgs::nth_element(b, b.begin() + k - 2);
    int x = b[k - 2];
    vector<int> c;
    c.reserve(n);
    for (int i = 0; i < n; i++) {
        if (a[i] <= x)
            c.emplace_back(a[i]);
    }
    int l = 0, r = c.size() - 1;
    int cnt = c.size() - (k - 1);
    bool ok = true;
    while (l < r) {
        if (c[l] == c[r]) {
            l++, r--;
        } else if (cnt > 0 and c[l] == x) {
            l++, cnt--;
        } else if (cnt > 0 and c[r] == x) {
            r--, cnt--;
        } else {
            ok = false;
            break;
        }
    }
    if (ok)
        cout << "YES\n";
    else
        cout << "NO\n";
}

这里插播一下关于 std::nth_element(l, r, k) （l, r, k 三者均为迭代器）的用法：

该函数会原地修改你传入的 $[l,r)$ ，然后让第 $k$ 个元素刚好是数组中第 $k$ 小的。其平均复杂度是 $O(n)$ 。比完整的排序一个数组（ $O(n\log n)$ ）更快。