杭州软件建设_开网店一个月能赚多少钱_移动营销_线上广告推广平台

https://codeforces.com/problemset/problem/1978/C

证明一

证： 一个序列里数字进行相加减，其奇偶性和该序列的奇数个数相一致的。

奇数±偶数=奇数
偶数±偶数=偶数

如果m个偶数相加减

$$\sum _i^{n}eve{n}_i=even\text{\hspace{1em}(1)}$$

假设序列有$n,m$个奇数和偶数

根据加减法的交换性质，把奇数(odd)都移动到最前面

$$[od{d}_1,\cdots ,od{d}_n,eve{n}_1,\cdots ,eve{n}_m]$$

由(1)式得

$$[od{d}_1,\cdots ,od{d}_n,even]$$

相似的，减法也依旧成立。

最终相加减的结果和序列的奇偶性相关

题解

由证明一得到，因为最终结果是偶数个奇数，所以我们序列最后的结果一定是偶数。

因此，当$k\%2==0$，结果一定不存在。

我们接着考虑最大值，最大排序一定是倒序，得到的值$max$, 该证明省略，比较直觉。

第一轮，通过交换1和$x(1<=x<=n)$，能够构造出$[0,2\cdot (n-1)]$之间的收益
第二轮，我们能得到的收益是，$[2\cdot (n-1),2\cdot (n-1)+2\cdot (n-3)]$, 通过交换$2和x(2<=x<=n-2)$
通过递推维护，我们能得到的收益就能均匀的出现分布在$[0,max]$之间的偶数分布。

用该方式构造即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{ll mx = 0;ll n, k;cin >> n >> k;for (int i = 1; i <= n; i++)mx += abs((n - i + 1) - i);if (k > mx || k % 2){cout << "No\n";}else{ll cnt = 0;int i = 1;int ts = (n - 2 * i + 1) * 2;while (cnt + ts < k){cnt += ts;i++;ts = (n - 2 * i + 1) * 2;}vector<int> res(n + 1);for (int i = 1; i <= n; i++){res[i] = i;}for (int j = 1; j <= i - 1; j++){res[j] = n - j + 1;res[n - j + 1] = j;}int j = i + (k - cnt) / 2;swap(res[i], res[j]);cout << "Yes\n";for (int i = 1; i <= n; i++){cout << res[i] << " ";}cout << "\n";}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--){solve();}return 0;
}