题解：P12373 「LAOI-12」命运。

可爱大黄兔 · 2025-04-27 17:47:05 · 题解

思路

先拆式子：

\begin{aligned} \sum\limits_{i=1}^{n-1}i^2 = 1^2+2^2+\cdots+n^2 \\ = n^2+\cdots+2^2+1^1 \end{aligned}

再依据题意构造，使第 i 个数与第 i+1 个数的方差为 (n-i)^2 即可。

因此我们可以构造这样一个序列：

当 n 为偶数： n,1,n-1,2,n-2,3,\cdots,\frac{n}2+1,\frac{n}2-1
当 n 为奇数： n,1,n-1,2,n-2,3,\cdots,\frac{n}2-1,\frac{n}2+1

代码

#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> ans;
int n;

int main() {
    scanf("%d", &T);
    while (T--) {
        ans.clear();
        cin >> n;
        ans.push_back(n);
        int l = 1, r = n - 1;
        bool flag = true;
        while (l <= r) {
            if (flag) {
                ans.push_back(l);
                l++;
            } else {
                ans.push_back(r);
                r--;
            }
            flag = !flag;
        }
        for (int x : ans) {
            printf("%d ", x);
        }
        puts("");
    }

    return 0;
}