「MX-X5 / GFOI Round 1」T4 epitaxy 题解

EuphoricStar · 2024-09-29 15:40:28 · 题解

首先若 2m > n 最大价值就是 n，一个答案是：

否则最大价值是 n 的最大的 \le m 的因数，设其为 d。一个答案是：

最大价值是 d 的证明：

显然一个排列的价值是 n 的因数。因为前面已经给出了一个最大价值为 d 的构造，所以只需要证 n 的 > m 的因数不可能成为一个排列的价值。

任取 n 的一个 > m 的因数，设其为 x。那么首先每个长度为 m 的子段都一定要有一个 x 的倍数。

若一个 x 的倍数 y 是一个长度为 m 的子段的最大值，就称 y 支配了这个子段。

可以发现 x 最多只能支配 x - m + 1 个子段，还剩下 n - x 个子段需要支配。

显然一个数至多支配 m 个子段，剩下的 x 的倍数有 \frac{n}{x} - 1 个。

因为 (\frac{n}{x} - 1) \times m < (\frac{n}{x} - 1) \times x = n - x，所以这些数不可能支配所有长度为 m 的子段。

时间复杂度：每个测试用例 O(n)。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    if (m * 2 > n) {
        for (int i = 1; i <= n; ++i) {
            int x = i;
            if (i == m) {
                x = n;
            } else if (i > m) {
                --x;
            }
            printf("%d%c", x, " \n"[i == n]);
        }
    } else {
        while (n % m) {
            --m;
        }
        for (int i = 1; i <= n; ++i) {
            int t = i;
            if (i > m && (i - 1) % m == 0) {
                t += m - 1;
            } else if (i > m) {
                --t;
            }
            printf("%d%c", t, " \n"[i == n]);
        }
    }
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

闲话：这题一开始是 MX-X only 的 T1。