题解：P11007 『STA - R7』Odtlcsu

Acheron_RBM · 2024-08-26 21:25:23 · 题解

有个很显然的结论，题目中的 x 与 y 奇偶性相同。

有个更简单的证明，奇数的平方为奇数，偶数的平方为偶数，所以 x 与 y 奇偶性相同。

思路就显而易见了，考虑构造一个长度为 y 的序列，其中的每个数为 \pm1。答案就比较显然了，我们先假设有 y 个 1 考虑每将一个 1 修改成 -1 对 x 的贡献为 2。所以我们只需改 (y-x)\div2 个 -1 即可。

代码：

int main()
{
    int n,k;
    cin>>n>>k;
    cout<<k<<"\n";
    int cnt=abs(k-n)/2;
    for(int i=1;i<=cnt;i++)
    {
        cout<<"-1 ";
    }
    for(int i=1;i<=k-cnt;i++)
    {
        cout<<1<<" ";
    }
    return 0;
}