[Solution] CF1809C Sum on Subarrays
hy233
·
·
题解
题意简述
你需要构造一个长度为 n 的序列 a_i，满足下列要求：
-
- 有恰好 k 个连续子序列和为正数。
- 其余的 n\times (n+1)/2 个连续子序列和为负数。
## 题解
我们可以将一个长度为 $n$ 的序列转为长度为 $n+1$ 的前缀和序列 $s_i$， 一个连续子序列 $[l,r]$ 的和就可以转化为 $s_r-s_{l-1}$。因为 $s_i$ 两两不相等（子序列和非 $0$ ），我们很容易想到：排列。要求有 $k$ 个正数相当于有 $k$ 对 $(i,j)$ 使得 $i<j,s_i<s_j$，即构造一个**正序对**个数为 $k$ 的排列。我们想到冒泡排序的过程中每次将一个逆序对变为正序对，所以我们从排列 $n+1,n,\cdots,1$ 开始，交换 $k$ 次即可。最后输出该排列的差分即为答案。
## 代码
```cpp
int a[N];
int main()
{
int t=rd();
while(t--)
{
int n=rd(),k=rd();
for(int i=0;i<=n;i++)
a[i]=n-i+1;
for(int i=0;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(k>0)
{
k--;
swap(a[i],a[j]);
}
}
for(int i=1;i<=n;i++)
cout<<a[i]-a[i-1]<<' ';
cout<<endl;
}
return 0;
}
```