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

· · 题解

思路

第一步，分解 \sum\limits_{i=1}^{n-1}i^2，可以得到 \sum\limits_{i=1}^{n-1}i^2 = 1 + 2 + 2 + 3 + 3 + 3 + ...... + (n-1) + (n-1) + (n-1)。\ 第二步，构造数组，我们可以构造以下数组：

1 ,n ,2 ,n - 2 ,3......

为什么呢？我们可以发现，相差为 1 的区间只有末尾那一个，相差为 2 的区间也只可以从末尾找到两个，因为相差为 2 的两个数后只剩下一个数了，以此类推。这样我们就可以得到代码了。

code:

#include<iostream>
#include<queue>
#define MOD 1000000007
using namespace std;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        if(n%2==1){
            for(int i=1;i<=n/2;i++){
                cout<<i<<" "<<n-i+1<<" ";
            }
            cout<<n/2+1<<"\n";
        }
        else{
            for(int i=1;i<=n/2;i++){
                cout<<i<<" "<<n-i+1<<" ";
            }
            cout<<"\n";
        }
    }
    return 0;
}