1978 C. Manhattan Permutations
https://codeforces.com/problemset/problem/1978/C
证明一
证: 一个序列里数字进行相加减,其奇偶性和该序列的奇数个数相一致的。
奇数±偶数=奇数
偶数±偶数=偶数
如果m个偶数相加减
∑ i n e v e n i = e v e n (1) \sum_i^{n} even_i = even \tag{1} i∑neveni=even(1)
假设序列有 n , m n,m n,m个奇数和偶数
根据加减法的交换性质,把奇数(odd)都移动到最前面
[ o d d 1 , ⋯ , o d d n , e v e n 1 , ⋯ , e v e n m ] [odd_1,\cdots,odd_n, even_1, \cdots, even_m] [odd1,⋯,oddn,even1,⋯,evenm]
由(1)式得
[ o d d 1 , ⋯ , o d d n , e v e n ] [odd_1,\cdots,odd_n, even] [odd1,⋯,oddn,even]
相似的,减法也依旧成立。
最终相加减的结果和序列的奇偶性相关
题解
由证明一得到,因为最终结果是偶数个奇数,所以我们序列最后的结果一定是偶数。
因此,当 k % 2 = = 0 k\%2==0 k%2==0,结果一定不存在。
我们接着考虑最大值,最大排序一定是倒序,得到的值 m a x max max, 该证明省略,比较直觉。
第一轮,通过交换1和
x
(
1
<
=
x
<
=
n
)
x(1<=x<=n)
x(1<=x<=n),能够构造出
[
0
,
2
⋅
(
n
−
1
)
]
[0,2\cdot (n-1)]
[0,2⋅(n−1)]之间的收益
第二轮,我们能得到的收益是,
[
2
⋅
(
n
−
1
)
,
2
⋅
(
n
−
1
)
+
2
⋅
(
n
−
3
)
]
[2\cdot (n-1) ,2\cdot (n-1) +2\cdot (n-3)]
[2⋅(n−1),2⋅(n−1)+2⋅(n−3)], 通过交换
2
和
x
(
2
<
=
x
<
=
n
−
2
)
2和x(2<=x<=n-2)
2和x(2<=x<=n−2)
通过递推维护,我们能得到的收益就能均匀的出现分布在
[
0
,
m
a
x
]
[0,max]
[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;
}
原文地址:https://blog.csdn.net/TKKDOUZI/article/details/142703516
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!