CF1948E 题解

_Z_F_R_ · 2024-03-17 23:03:17 · 题解

Update on 2024.10.29：修改了一处笔误，感谢 @Bugbread 指出，顺便修改了一些表述。

玄学，赛时乱搞过了。

题意

给你 N 个点与正整数 k，让你给每个点赋一个权值 a_i，使得 \{a_i\} 是一个 1 \sim N 的排列。然后对所有满足 |i - j| + |a_i - a_j| \le k 的数对 (i, j)，在结点 i 与结点 j 之间有连一条边。求一个满足条件的 \{a_i\}，使图可以分成 M 个团，并最小化 M。

思路

以下 i, j 两数若同时出现，若无特殊说明，均为正整数，并满足 1 \le i, j \le N，且 i \not = j。

首先两个显然的贪心：

结论一：所有选择的团内，结点的编号一定连续，即，团内结点的编号的集合类似于 \{l, l + 1, l + 2, \dots, r - 1, r\}。
- 证明：设有两个团，且一个团内结点编号的最大值大于另一个团内结点编号的最小值，即类似的理解为这两个团节点编号在在值域上“相交”，那么可以合理“交换”两个点（即，在交换结点所在的团的同时，交换 a_i），使得两个团在值域上“不相交”。
例如：两个团的结点编号集合分别为 S_1 = \{1, 3\} 和 S_2 = \{2\}，\{a_i\} = \{1, 2, 3\}，那么可以交换为 S_1' = \{1, 2\} 和 S_2 = \{3\}，\{a_i'\} = \{1, 3, 2\}。

交换后，在不等式 |i - j| + |a_i - a_j| \le k 中，|a_i - a_j| 不变，|i - j| 总是减小。则只会连更多的边，不会影响结果。
结论二：所有选择的团内，所有结点的权值 a_i 排序后一定连续，即，团内结点的权值 a_i 的集合类似于 \{l, l + 1, l + 2, \dots, r - 1, r\}。
- 证明：将 a_i 看做新的结点编号，结点编号看做新的 a_i，构造新图。则在新图中，对于每个有连边的数对 (i, j)，在新图中 (a_i, a_j) 依然是连边的，无连边的数对亦然，余下同结论一证明。

还有两个结论：

结论三：每个团大小不超过 k。
- 证明：若团大小超过 k，则必有一个两个数均为团内结点编号的数对 (i, j)，使得 |i - j| \ge k。又因为对于任意 i,j，|a_i - a_j| \ge 1，所以 |i - j| + |a_i - a_j| > k，不满足团的性质。
结论四：对于任意整数 t，将每个团中各结点权值加上 t 不影响结果。
- 证明：令 a_i' = a_i + t，显然对于任意数对 (i, j)，|i - j| 不变，|a_i' - a_j'| = |(a_i + t) - (a_j + t)| = |a_i + t - a_j - t| = |a_i - a_j|，所以 |i - j| + |a_i' - a_j'| = |i - j| + |a_i - a_j|，不影响结果。

综上，可以得出最佳的划分方案：

将 1 \sim N 个结点划分成 t 个部分，使得每个部分内编号连续，每个部分内 a_i 的编号连续且其值域与结点编号的值域相等。形式化的，将 N 个结点划分为 [l_1, l_2), [l_2, l_3), [l_3, l_4), \dots, [l_{t - 1}, l_t), [l_t, l_{t + 1}) 这样 t 个部分，使得 1 = l_1 < l_2 < l_3 < \dots < l_t < l_{t + 1} = N + 1，且 \forall i \in [1, t]，l_i \le a_i < l_{i + 1}。

根据结论四，显然我们可以把图划分为若干部分，使得每个部分可以转化为：结点编号为 1 \sim M，\{a_i\} 是 1 \sim M 的排列，构造一个 \{a_i\} 使得这个图按给定方式连边后是一个团。

显然每个部分是否可以通过合适的 \{a_i\} 转化为团，只与其所含结点的数量有关。

根据结论三，不可能有 M > k，考虑构造 M = k 的情况。

可以构造：

\lfloor \frac{M}{2} \rfloor + 1 - i & \text{if } i \le \lfloor \frac{M}{2} \rfloor \\ M + \lfloor \frac{M}{2} \rfloor + 1 - i & \text{otherwise.} \end{cases}

来满足要求（即对于 \{a_i\} = \{1, 2, \dots, M\}，反转其区间 [1, \lfloor \frac{M}{2} \rfloor] 与区间 [\lfloor \frac{M}{2} \rfloor + 1, M]）。

证明（设 1 \le i < j \le M，且 i, j 是正整数）：

证毕。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
    int sig = 1;
    ll num = 0;
    char c = getchar();
    while(!isdigit(c)) {
        if(c == '-') {
            sig = -1;
        }
        c = getchar();
    }
    while(isdigit(c)) {
        num = (num << 3) + (num << 1) + (c ^ 48);
        c = getchar();
    }
    return num * sig;
}
void Write(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x >= 10) {
        Write(x / 10);
    }
    putchar((x % 10) ^ 48);
}

vector<int> Gen_vec(int siz) {
    int i;
    vector<int> vec;
    for(i = siz / 2; i >= 1; i--) {
        vec.push_back(i);
    }
    for(i = siz; i > siz / 2; i--) {
        vec.push_back(i);
    }
    return vec;
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, k, i, j;
        n = Read(), k = Read();
        for(i = 1; i <= n; i += k) {
            int l = i, r = min(i + k - 1, n);
            auto vec = Gen_vec(r - l + 1);
            for(auto v : vec) {
                Write(v + i - 1), putchar(' ');
            }
        }
        putchar('\n'), Write((n + k - 1) / k), putchar('\n'); // (n + k - 1) / k 下取整 = n / k 上取整
        for(i = 1; i <= n; i += k) {
            int l = i, r = min(i + k - 1, n);
            for(j = l; j <= r; j++) {
                Write((l - 1) / k + 1), putchar(' ');
            }
        }
        putchar('\n');
    }
    return 0;
}