题解 | 构造数列

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//对于一组相邻的偶数 例如2和4 我们要构造一组和他们的和相等的奇数 可以令前面的数减一后面的数加一 这样既得到了奇数 也没有改变和
//我们可以将此方法推广到多个偶数 让前n/2个偶数减一 后n/2个偶数加一即可 所以如果题目中所给n除以2后如果得到奇数 说明不能再二分构造 故输出NO
//当n除以2为偶数 我们模拟上述过程即可 只需将数组遍历一遍 时间复杂度O(n)
    int n;
	cin >> n;
	if(n/2%2==1)
	{
		cout << "NO" << "\n";
		return;
	}
	else
	{
		cout << "YES" << "\n";
		vector<int>v(n+1,0);
		for(int i=1;i<=n/2;i++) v[i]=i*2;
		for(int i=n/2+1;i<=n/4*3;i++) v[i]=v[i-n/2]-1;
		for(int i=n/4*3+1;i<=n;i++) v[i]=v[i-n/2]+1;
		for(int i=1;i<=n;i++) cout << v[i] << " ";
		cout << "\n";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}