题解思路

这是一道结合组合数学和贪心构造的高难度问题。核心在于理解MEX函数的性质和子数组贡献度的计算。

1. MEX函数性质分析

MEX函数有以下重要性质：

• $\mathrm{mex}({0, 1, 2, \ldots, k-1}) = k$
• $\mathrm{mex}(S) \leq |S| + 1$（因为至多缺失一个小于等于集合大小的数）
• 要使MEX值尽可能大，需要子数组包含尽可能多的连续从0开始的数字

2. 子数组贡献度分析

对于一个排列，每个子数组都会对总和产生贡献。关键观察：

位置0的特殊性：包含位置0的子数组的MEX值至少为1，而不包含位置0的子数组的MEX值为0。因此，位置0应该尽可能出现在能被更多子数组包含的位置。

贪心策略：将较小的数字放在中间位置，使其能被更多的子数组包含，从而提高这些子数组的MEX值。

3. 最优排列构造算法

通过数学分析和实验验证，发现以下构造方法能达到最优解：

构造策略：

1. 从大到小依次放置n-2, n-4, n-6, ...（所有大于0的偶数，倒序）
2. 在中间位置放置0
3. 按升序补充剩余的奇数：1, 3, 5, ...

举例说明：

• n=5: [3, 1, 0, 2, 4]
• n=6: [4, 2, 0, 1, 3, 5]

4. 最大值计算公式

通过组合数学分析，可以推导出闭式解：

• 偶数情况：$\frac{n(n+2)(2n+5)}{24}$
• 奇数情况：$\frac{(n+1)(n+3)(2n+1)}{24}$

5. 复杂度分析

• 时间复杂度：$O(T \times n)$
• 空间复杂度：$O(n)$

Java题解代码

import java.io.*;
import java.util.*;

public class Main {
   
   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder result = new StringBuilder();
       
       int T = Integer.parseInt(br.readLine().trim());
       
       for (int t = 0; t < T; t++) {
           int n = Integer.parseInt(br.readLine().trim());
           
           // 计算最大MEX和
           long maxSum = calculateMaxMexSum(n);
           result.append(maxSum).append("\n");
           
           // 构造最优排列
           int[] optimalPermutation = constructOptimalPermutation(n);
           for (int i = 0; i < n; i++) {
               result.append(optimalPermutation[i]);
               if (i < n - 1) {
                   result.append(" ");
               }
           }
           result.append("\n");
       }
       
       System.out.print(result.toString());
   }
   
   /**
    * 计算给定长度下的最大MEX和
    */
   private static long calculateMaxMexSum(int n) {
       if (n % 2 == 0) {
           // 偶数公式：n(n+2)(2n+5)/24
           return (long) n * (n + 2) * (2L * n + 5) / 24;
       } else {
           // 奇数公式：(n+1)(n+3)(2n+1)/24
           return (long) (n + 1) * (n + 3) * (2L * n + 1) / 24;
       }
   }
   
   /**
    * 构造达到最大MEX和的排列
    */
   private static int[] constructOptimalPermutation(int n) {
       List<Integer> permutation = new ArrayList<>();
       boolean[] used = new boolean[n];
       
       // 第一步：从大到小放置n-2, n-4, n-6, ... (大于0的偶数倒序)
       for (int val = n - 2; val > 0; val -= 2) {
           permutation.add(val);
           used[val] = true;
       }
       
       // 第二步：放置0
       permutation.add(0);
       used[0] = true;
       
       // 第三步：按升序补充剩余未使用的数字
       for (int val = 1; val < n; val++) {
           if (!used[val]) {
               permutation.add(val);
           }
       }
       
       return permutation.stream().mapToInt(Integer::intValue).toArray();
   }
}

C++题解代码

#include <iostream>
#include <vector>
#include <ios>

using namespace std;

class MaxMexSolver {
public:
    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int T;
        cin >> T;
        
        while (T--) {
            int n;
            cin >> n;
            
            // 计算并输出最大MEX和
            long long maxSum = calculateMaxSum(n);
            cout << maxSum << "\n";
            
            // 构造并输出最优排列
            vector<int> optimal = buildOptimalPermutation(n);
            for (int i = 0; i < n; i++) {
                cout << optimal[i];
                if (i < n - 1) cout << " ";
            }
            cout << "\n";
        }
    }
    
private:
    /**
     * 使用闭式公式计算最大MEX和
     */
    long long calculateMaxSum(int n) {
        if (n % 2 == 0) {
            // 偶数情况：n(n+2)(2n+5)/24
            return (long long)n * (n + 2) * (2LL * n + 5) / 24;
        } else {
            // 奇数情况：(n+1)(n+3)(2n+1)/24
            return (long long)(n + 1) * (n + 3) * (2LL * n + 1) / 24;
        }
    }
    
    /**
     * 构造最优排列：先放大偶数(倒序)，然后0，最后补充剩余数字
     */
    vector<int> buildOptimalPermutation(int n) {
        vector<int> result;
        vector<bool> used(n, false);
        
        // 步骤1：添加大偶数序列 n-2, n-4, n-6, ... (>0)
        for (int value = n - 2; value > 0; value -= 2) {
            result.push_back(value);
            used[value] = true;
        }
        
        // 步骤2：添加0
        result.push_back(0);
        used[0] = true;
        
        // 步骤3：按升序添加剩余未使用的数字
        for (int value = 1; value < n; value++) {
            if (!used[value]) {
                result.push_back(value);
            }
        }
        
        return result;
    }
};

int main() {
    MaxMexSolver solver;
    solver.solve();
    return 0;
}