Solution. CF1129B Wrong Answer

Description

给定一个序列 $a$，有 $n$ 个元素，编号从 $0$ 到 $n-1$。求 $\max\limits_{0 \leq l \leq r \leq n-1} \sum\limits_{l \leq i \leq r} (r-l+1) \cdot a_i$。

Alice 的解法是令 $[l,r]$ 为序列 $a$ 权值和最大的子段。

请你给出一组 Hack 数据，使得 Alice 给出的答案与正确答案的差为 $k$。

$n\le2000,|a_i|\le10^6,k\le10^9$

Solution

已有的三篇题解给出了三个一样的构造方法，同时，从我个人角度来看，令 $a_{1\dots1998}=0$ 这种构造方式并不是很符合直觉。

实际上这是一道难度不高且方法较多的构造题。

首先，想要 Hack Alice 的解法非常简单，Alice 忽略了子段长度对答案的影响，随便用负数就能卡掉。

延续样例的思路，我最开始给出的构造是 $1,-2,a_1,a_2,a_3,\dots,a_y$，这样，令 $x=\sum a_i$，Alice 的答案会是 $xy$，实际上期望的答案是加入 1 与 -2，即 $(x-1)(y+2)$。

Alice 答案与正确答案的差我们记作 $\Delta=(x-1)(y+2)-xy=2x-y-2$，我们希望 $\Delta=k$。

接下来，我们考虑一个向序列末尾动态加数的过程，初始时序列为 $1,-2$，$x=y=0$，$\Delta=-2$，每当我们像序列末尾添加一个数 $t$，其对 $\Delta$ 的贡献为 $2t-1$，需要注意的是 $t$ 有一个 $10^6$ 的上界，不断加数使得 $\Delta=k$ 即可。

$O(n)$ 模拟这一过程就能构造出一个合法的序列。

另外还有一种更加简洁的构造，让序列由 $-1,1$ 开头，类似上文，我们可以求出 $\Delta=x-y$，这样一个新数 $t$ 对 $\Delta$ 的贡献为 $t-1$。

Code

给出第一种构造的代码。

namespace Main{
    const int N = 2005;
    int k, n, a[N];
    void Main(){
        input(k);
        n = 2;
        a[0] = 1, a[1] = -2;
        k += 2;
        while(k) a[n] = min(1000000, (k + 1) / 2), k -= 2 * a[n++] - 1;
        cout << n << endl;
        for(ri i = 0; i < n; i++) cout << a[i] << ' ';
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。