相信并抓住那些源于热爱,忠于自我的每一个可能性

题解 P5665 【划分】

2019-12-01 10:09:01


UPD:官方数据出来,原题解无法通过。现在已经常数优化,保险起见,评测请开启O2

既当作是一个赛场自己没做出来的总结,也给那些不愿使用 __int128 的同学们一篇可以参考的题解吧

首先由 完全平方公式 ,可以得到 $(a + b)^2 > a^2 + b^ 2$

所以,我们要尽可能 多分段

观察这个图:

如果此时, $sum_L + x \le sum_R$ ,那么 $x$ 这个数应该分到那一边呢?

显然, $sum_L \le sum_R$ , $x$ 加到 $side$ 那边 将会产生 $2x\cdot sum_{side}$ 的代价

为了使得总代价最小,我们当然把 $x$ 加到 $sum_L$ 那一边啦!

综上所述,对于某一段,我们贪心的在最靠后的可行位置划分,也就是使得最后一段最小,答案必然最优


64pts的做法是贪心的记录这一段的值,枚举 上一段的终点

大概就是这样:

for(int i = 2; i <= n; ++i)
    for(int j = 1; j < i; ++j)
        if(sum[i] - sum[j] >= last[j] && f[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) < f[i])
            f[i] = f[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]), last[i] = sum[i] - sum[j];

$last_i$ 表示以 $i$ 结尾的那一段的和, $f_n$ 即为答案


那100pts的做法呢?

用 $g_i$ 表示现在划分段的末尾为 $i$ ,上一段的末尾

用 $s_i$ 表示 $\sum_{k = 1}^{i} a_k$ (前缀和)

换言之, $g_i = \max pos\ s.t. \ s_i - s_{pos} \ge s_{pos} - s_{g_{pos}}$

移项得到, $g_i = \max pos\ s.t. \ s_i \ge 2s_{pos} - s_{g_{pos}}$

令 $ val(x) = 2 s_x-s_{g_x} $ ,则 $g_i = \max pos\ s.t. \ s_i \ge val(pos)$ ,有结论:

如果 $x, y$ 都是当前位置 $i$ 的合法来源,即 $s_i \ge val(x), val(y)$ ,而且 $x<y$ ,则 $x$ 必然 无法成为 $g_i$

由此,当求 $g_i$ 时,先把单调队列中所有队首的过时决策弹出(如果队列中的下一个数的 $val$ 都 $\le s_i $ 的话,这个决策就被弹出)

$g_i$ 就是 新的队首 ,然后把 $i$ 加入决策时,要把队尾所有 $val \ge val(i)$ 的弹出(因为 $i$ 在它们 后面 , $val$ 还比它们 ,那它们必然 不会成为 任何一个位置的 $g$ 了)

最后一段的末端点是 $n$ ,所以让 $p = n$ ,不断的朝 $g_p$ 追溯,并统计答案

注意时间优化,空间优化,高精度,时间复杂度 $O(n)$

前缀和不用平方,不要开 高精度数组

代码如下:

#include <bits/stdc++.h>
#define val(x) (s[x] << 1) - s[g[x]]
using namespace std;
typedef long long LL;
const int MOD = (1 << 30) - 1, N = 4e7 + 5, M = 1e5 + 5;
int type, g[N], a, n, b[N], l[M], r[M], p[M];
LL s[N];

// ========== 高精度 =============
struct bigint
{
    static const unsigned long long BASE = 1000000000ULL, WIDTH = 9; // 压位高精度
    unsigned long long len, num[20];
    bigint() { len = 0; memset(num, 0, sizeof num); }
    bigint operator = (LL oth)
    {
        len = 0;
        while(oth) { num[++len] = oth % BASE; oth /= BASE; }
        return *this;
    }
    bigint operator + (const bigint &oth)
    {
        bigint res; res.len = max(len, oth.len); int p = 0;
        for(register int i = 1; i <= res.len; i++) 
        {
            res.num[i] = num[i] + oth.num[i] + p;
            p = res.num[i] / BASE;
            res.num[i] %= BASE;
        }
        if(p) res.num[++res.len] = p;
        return res;
    }
    inline bigint square() // 高精度平方 
    {
        bigint res; res.len = (len << 1) - 1; int p = 0;
        for(register int i = 1; i <= len; i++) for(register int j = 1; j <= len; j++)
            res.num[i + j - 1] += num[i] * num[j];
        for(register int i = 1; i <= res.len; i++)
        {
            res.num[i] += p;
            p = res.num[i] / BASE;
            res.num[i] %= BASE;
        }
        while(p) { res.num[++res.len] = p % BASE; p /= BASE; }
        return res;
    }
    void print() { printf("%llu", num[len]); for(register int i = len - 1; i; i--) printf("%09llu", num[i]); }
} ans; 

// ============ 快读 ============== 
inline LL read()
{
    register LL vl = 0;
    register char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') {vl = (vl << 3) + (vl << 1) + (c ^ 48); c = getchar();}
    return vl;
}

// ============ 单调队列 ============== 
struct my_deque
{
    int q[N], head, tail;
    my_deque() { head = 1; tail = 1; }
    inline int front() { return q[head]; }
    inline int nxt() { return q[head + 1]; } // 第 2 个元素 
    inline int back() { return q[tail]; }
    inline void push(const int &val) { q[++tail] = val; }
    inline void pop_front() { head++; }
    inline void pop_back() { tail--; }
    inline bool have_nxt() { return head < tail; } // 队列的 size 是否 >= 2 
    inline bool empty() { return head > tail; }
} deq;

// ============ 读入数据 ============== 
inline void input()
{
    if(type)
    {
        register int x, y, z, m;
        x = read(); y = read(); z = read(); b[1] = read(); b[2] = read(); m = read();
        for(register int i = 1; i <= m; i++) { p[i] = read(); l[i] = read(); r[i] = read(); }
        for(register int i = 3; i <= n; i++) b[i] = (1LL * x * b[i - 1] & MOD) + (1LL * y * b[i - 2] & MOD) + z & MOD;
        for(register int j = 1; j <= m; j++)
            for(register int i = p[j - 1] + 1; i <= p[j]; s[i] = s[i - 1] + a, i++)
                a = b[i] % (r[j] - l[j] + 1) + l[j];
    }
    else for(register int i = 1; i <= n; s[i] = s[i - 1] + a, i++) a = read();
}
int main()
{
    n = read(); type = read();
    input();

    // 单调队列优化 DP 求 g[]  
    for(register int i = 1; i <= n; i++)
    {
        while(deq.have_nxt() && val(deq.nxt()) <= s[i]) deq.pop_front();
        g[i] = deq.front();
        while(!deq.empty() && val(deq.back()) >= val(i)) deq.pop_back();
        deq.push(i);
    }

    // 统计答案 
    for(register int i = n; i; i = g[i])
    {
        bigint tmp; tmp = s[i] - s[g[i]];
        ans = ans + tmp.square();
    }

    ans.print();
    return 0;
}