B.切切切

题目描述

小胖有一个长度为 $n+1$ 的数组 $f$，数组下标为 $[-2^n, 2^n]$。

定义一个数组的权值： $val(f) = \sum_{i=0}^{2^n} \bigl\lvert f_i\bigr\rvert - \bigl\lvert f_{-i}\bigr\rvert$

小胖可以将数组 $f$ 切割成任意数量的 $m$ 个一维数组 $A_1, \dots, A_m$，并满足以下要求：

• 对于任意的下标 $k$，都有：$\sum_{i=1}^{m} A_{i,k} = f_k$
• 我们的目标是使得下式的值最小：$\sum_{i=1}^{m} val(A_i) + (n+1)\times(m-1)$

其中，所有 $A_i$ 中的元素均为整数。

你需要构造出一种划分方案，输出最小值及划分后的数组。

输入格式

• 第一行一个整数 $p$，表示 $n+1$ 的值。
• 接下来一行包含 $p$ 个整数，分别表示数组 $f$ 中从下标 $-\lfloor p/2\rfloor$ 到 $\lfloor p/2\rfloor$ 的元素。

保证：

• $3 \le p \le 2\times10^5$
• $0 \le \lvert f_i\rvert \le 10^9$
• $p$ 为奇数

输出格式

• 第一行两个整数：
  1. 划分的数组个数 $m$
  2. 最小值：$\sum_{i=1}^{m} val(A_i) + (n+1)\times(m-1)$
• 接下来输出 $m$ 行，每行 $p$ 个整数，表示每个 $A_i$ 数组的值。

样例输入

5
0 1 3 0 7

样例输出

2 7
3 0 0 0 3
-3 1 3 0 4

这个题略考思维，
Fact：任何函数定义域关于原点对称的函数都可以分为一个奇函数和一个偶函数的和
需要我们使用数学的思维来解题

核心代码

int a[N], b[N], c[N];

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans1 = 0;
    for (int i = 1; i <= n / 2; i++)
        ans1 += abs(abs(a[i]) - abs(a[n - i + 1]));
    for (int i = 1; i <= n / 2; i++)
    {
        b[n/2+1 - i] = (a[n/2+1 - i] + a[n/2+1 + i]) / 2;
        b[n/2+1 + i] = (a[n/2+1 - i] + a[n/2+1 + i]) / 2;
    }
    int ans2 = n;
    for (int i = 1; i <= n; i++) c[i] = a[i] - b[i];
    for (int i = 1; i <= n / 2; i++)
        ans2 += abs(abs(c[i]) - abs(c[n - i + 1]));
    if (ans1 < ans2)
    {
        cout << 1 << ' ' << ans1 << endl;
        for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    }
    else
    {
        cout << 2 << ' ' << ans2 << endl;
        for (int i = 1; i <= n; i++) cout << b[i] << ' ';
        cout << endl;
        for (int i = 1; i <= n; i++) cout << c[i] << ' ';
    }
}

我们还需要考虑原本就是最优的情况