frankchenfu 的博客

frankchenfu 的博客

题解 P5665 【划分】

posted on 2019-12-14 20:05:33 | under 题解 |

1. 题意简述

给定一个长度为 $n$ 的正整数序列 $\{a\}$ ,要求找出一种划分方式,使得当划分的断点在 $k_1,k_2,\ldots,k_p$ 时,满足以下条件:

$\bullet\ \displaystyle\sum_{i=1}^{k_1} a_i\le\displaystyle\sum_{i=k_1 + 1}^{k_2} a_i\le\ldots\le\displaystyle\sum_{i=k_p + 1}^{n} a_i $

$\bullet\ \left(\displaystyle\sum_{i=1}^{k_1} a_i \right)^2 +\left( \displaystyle\sum_{i=k_1 + 1}^{k_2} a_i\right )^2 + \cdots + \left(\displaystyle\sum_{i=k_p + 1}^{n} a_i\right)^2 $的值最小。

注意,这里的 $p$ 可以是任意值,即可以划分任意段数。特别地,所有的数可以全部划为一段。

2. 部分分算法

2.1 $12\text{pts}$ 做法

关键词:枚举,搜索

注意到 $n\le 10$ ,这也就意味着我们可以枚举两个数之间是否分开,最后统计一次答案取最优解。

由于每两个数之间会有一个空格,有分开和不分开两种情况,因此可以在 $\mathcal{O}(n\cdot 2^{n-1})$ 的时间内得出答案。

2.2 $24\text{pts}$ 做法

关键词:搜索,剪枝,搜索序

$n\le 50$,暴力无法通过。但是得到暴力算法之后,我们可以考虑优化搜索顺序和最优性剪枝。

显然地,根据 $(a+b)^2\le a^2+b^2$,我们可以知道划分的段数越多越好,但是单调递增的条件限制着我们。所以我们搜索的时候优先搜索划分多的方案,也就是能划尽量划;

另一方面,我们如果当前已经划的答案甚至大于最优解了,直接结束这部分“失败”的搜索。

综合以上优化,我们可以得到 $12\sim 24$ 分不等的部分分。

2.3 $36\text{pts}$ 做法

关键词:动态规划 $\cdot\ \alpha$

面对 $n\le 400$ 的范围,搜索无法承受,我们考虑动态规划算法。

我们设计一个状态 $f(j,i)$ 表示当前划分到 $i$ 并且决定在这里截断,上一次断点取在了 $j$ 的地方,那么我们就可以直接算出区间 $[j,i]$ 的贡献了。接下来,我们再枚举一维 $k$ 表示 $j$ 之前从哪一个断点转移过来,显然有转移方程 $f(j,i)=\min\left\{f(k,j-1)+\left(\displaystyle\sum_{x=j}^{i}a_x\right)^2\right\}$

状态是 $\mathcal{O}(n^2)$ 的,转移是 $\mathcal{O}(n)$ 的,总复杂度 $\mathcal{O}(n^3)$。

2.4 $64\text{pts}$ 做法

关键词:动态规划 $\cdot\ \beta$

在 $n\le 5000$ 的时候,上述动态规划难以进行直接的优化,我们需要发掘题目的性质。

重新考虑 $24\text{pts}$ 算法中关于搜索序优化的部分。

由于 $(a+b)^2=a^2+b^2+2ab>a^2+b^2$ ,我们得出的结论是段数要划分得越多越好;那么反过来,对于给定的一段 $i$,如果对于任意的位置 $j(1\le j<i)$ 之前的那一段总和值确定的,换句话说对于任意的 $j$都有 $\displaystyle\sum_{x=j}^{i}a_x$ 必须要大于的值只和 $j$ 有关并且是确定的,那么我们具体选择哪一个 $j$ 是不是也是确定的呢?

答案是肯定的。

假设我们发现了有 $j_1,j_2,\ldots(j_1<j_2<\ldots)$ 这些 $j$ 都是可以转移到 $i$ 的,也就是 $\displaystyle\sum_{x=j}^{i}a_x$ 都能保证使得到目前为止的序列是递增的,那么我们会选择哪一个呢?

显然选择最大的一个 $j$ 是最优的,这样分的段数会尽可能大。如果选择的不是最大的那个 $j$(记为 $j'$) ,那么肯定 $j'$ 前面能分的段数要大于 $j$ 前面的段数——可是我们可以和 $j'$ 的分法一模一样,然后把 $(j',j]$ 这个区间直接并进最后一段,这样总的段数至少不会变劣;由于 $(j',j]$ 内可能可以再分,因此可能更优。

这样,我们就证明了转移策略:每次必然是转移到能转移到的最靠后的点

既然转移是唯一的,那么我们自然可以记下分到 $i$ 的时候,以 $i$ 结尾的这一段总和是多少——这个是唯一确定的,记为 $g(i)$;继承 $f(i)$ 的定义,同时省略 $j$ 这一维,表示的就是到 $i$ 为止的最优解,则

$$f(i)=f(\text{argmax}(j))+\sum_{x=j}^i a_x$$

其中 $\text{argmax}(j)$ 表示的是 $j$ 能取的最大值。

这样一来,时间复杂度降到了 $\mathcal{O(n^2)}$,可以通过 $n\le 5000$ 的数据。

3. 标解算法

3.1 算法

从 $64\text{pts}$ 的做法开始考虑。我们每次都需要向前枚举,找到第一个能够转移的 $j$ ,这个看起来很可优化的样子。

如果有两个位置 $a,b$ ,满足$a>b$ 且 $f(a)\le f(b)$,这说明 $a$ 离得更近,并且连起来的代价还更小,那么我们肯定就不会选 $b$ 了;这个结论甚至与 $i$ 无关,也就是一旦出现了一个这样的 $a$ ,那么这个 $b$ 它就被永远地抛弃了。

这样,我们最后会留下来一串的数,它们一定是满足若 $a>b$ 则 $f(a)>f(b)$ ,换言之它们是单调的。

于是我们用一个单调队列维护所有可能的转移点。

然后每次 $i$ 向右移的时候需要判断队首是不是已经没有第二个优了,如果是,弹出队首。反复执行以上操作。

此时我们的 $f(i)$ 就是用队首来更新的。然后尝试加入 $i$ 这个决策点。

接下来我们看看原来的队尾是不是还不如 $i$ 这个点优,如果是,弹出队尾。最后加入 $i$。

这样,因为单调队列每个数至多进队一次,出队一次,复杂度是 $\mathcal{O}(n)$ 的,可以直接拿到 $88\text{pts}$。

3.2 优化

可是想要拿到 $100\text{pts}$ 可不是一件容易的事情。

3.2.1 输入

根据题目的要求,我们需要用一些奇怪的方法输入,这些按照题目的意思走即可——但是,如果直接开了long long以达到算出 $b_i$ 然后再取模得出 $a_i$ ,这可能导致超时——long long的乘法与取模运算非常慢!

但是我们可以使用 unsigned int 来存储这些数字。众所周知,unsigned int 在溢出的时候回舍弃高位而保留低位,而题目给出的模数是 $2^{30}$——恰好就是二进制位下的后 $30$ 位。于是我们大胆地让它自然溢出,然后取后 $30$ 位。效率显著提高。

Tips: 推荐使用fread快读。

3.2.2 状态存储

题目给出的数据范围非常大,最多情况下可能是 $(4\times 10^{7}\times 10^{9})^2=1.6\times 10^{33}$,此时 $64$ 位整数无法存下,需要使用高精度($4$位int)。

但是这样一来,我们相当于空间上直接乘上了 $4$ 的常数,加之 $n=4\times 10^7$ ,即使是 $1\text{G}$ 的内存也是不够用的,因此我们的 $f$ 数组需要作出改变:每次存它是从哪里转移过来的。显然转移点固定,这样就可以使用一个 int 存下所有的转移了。

可是这样最后的答案怎么计算?最后从 $n$ 倒推回去即可!反正前缀和是 long long范围的,最后只要开一个高精度数即可。空间省下来了!fread快读的空间开得下了!

3.2.3 高精度计算

你别以为省下空间就好了!高精度可慢了!

想一想常数那么大的乘法运算,动不动模一模除一除,两下子就Time Limit Exceeded了。

那么就把模运算和除法运算去掉吧!

首先,先把高精度数用 $2^{32}$ 进制存储,然后模运算就是 a&0x7fffffff 或是强制转换 unsigned int,除法运算就是 a>>32

然后正常地算高精度,由于是位运算,快得起飞。

然后最后还原一次答案,还原成 $10$ 进制即可。


这样一来,我们就解决了这道题的绝大多数问题,剩下的常数问题就各显神通了。

以下代码可以在洛谷的评测机上跑进1.2s

#include <cstdio>
#include <cstring>
#include <ctime>
const int MAXN=40000010;
const unsigned PMOD=(1<<30)-1;
const unsigned MOD=1e9;

long long _sum[MAXN],*sum=_sum+5,g[MAXN];
int q[MAXN],f[MAXN];
int p[100010],l[100010],r[100010];

char _B[1<<21],*_S=_B,*_T=_B;
#define getchar() (_S==_T&&(_T=(_S=_B)+fread(_B,1,1<<21,stdin),_S==_T)?EOF:*_S++)
inline int read(){
    register int res=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        res=(res<<3)+(res<<1)+(ch&15);
        ch=getchar();
    }
    return res;
}

int main(){
    int n=read(),type=read();
    if(type==0){
        for(int i=1;i<=n;i++){
            int x=read();
            sum[i]=sum[i-1]+x;
        }
    }
    else{
        register unsigned x,y,z,m;
        register unsigned s1,s2,s3,pos=1;
        x=read();y=read();z=read();s1=read();s2=read();m=read();
        for(register int i=1;i<=m;i++){
            register unsigned p=read(),l=read(),r=read(),len=r-l+1;
            for(;pos<=p;pos++){
                if(pos==1)
                    s3=s1;
                else if(pos==2)
                    s3=s2;
                else{
                    s3=(x*s2+y*s1+z)&PMOD;
                    s1=s2;s2=s3;
                }
                sum[pos]=sum[pos-1]+s3%len+l;
            }
        }
    }
    register int *hd=q+1,*tl=q+1;
    for(register int i=1;i<=n;i++){
        while(hd<tl&&sum[*hd]+g[*hd]<=sum[i])
            hd++;
        g[i]=sum[i]-sum[*(hd-1)];
//      f[i]=f[q[hd-1]]+g[i]*g[i];
        f[i]=*(hd-1);
        while(hd<tl&&sum[*(tl-1)]+g[*(tl-1)]>=sum[i]+g[i])
            tl--;
        *tl++=i;
    }
    register unsigned pos=n;
    register unsigned long long ans[3]={0,0,0};
    while(pos){
        register unsigned long long tmp1=g[pos]&PMOD,tmp2=g[pos]>>30;
        ans[2]+=tmp2*tmp2;
        ans[1]+=tmp1*tmp2<<1;
        ans[0]+=tmp1*tmp1;
        ans[1]+=ans[0]>>30;ans[0]&=PMOD;
        ans[2]+=ans[1]>>30;ans[1]&=PMOD;
        pos=f[pos];
    }
    register unsigned long long tmp[4]={ans[2],0,0,0};
    for(int i=1;~i;i--){
        for(int j=0;j<=3;j++)
            tmp[j]<<=30;
        tmp[0]+=ans[i];
        for(int j=0;j<=2;j++){
            tmp[j+1]+=tmp[j]/1000000000;
            tmp[j]%=1000000000;
        }
    }
    if(tmp[3])
        printf("%llu%09llu%09llu%09llu\n",tmp[3],tmp[2],tmp[1],tmp[0]);
    else if(tmp[2])
        printf("%llu%09llu%09llu\n",tmp[2],tmp[1],tmp[0]);
    else if(tmp[1])
        printf("%llu%09llu\n",tmp[1],tmp[0]);
    else
        printf("%llu\n",tmp[0]);
    return 0;
}