P5665 划分 题解

这是一个贪心题，首先说结论：最优情况是划分的最后一段最小。 我们来证明这个结论。 首先，设 $sum_i$ 表示前缀和，令 $j$ 为长度为 $i$ 的前缀最优情况下的最后一个划分点，令 $s_i=sum_i-sum_j$ 考虑归纳证明： 1. 长度为 $1$ 的前缀不需要划分，最后一段长度只能是 $1$，满足上面的条件。 2. 假设对于长度 $<i(i\ge 2)$ 的前缀，最优情况都是划分的最后一段最小，现在来说明长度为 $i$ 的前缀划分的最优情况也是划分的最后一段最小。 我们找到最大的 $j$，满足 $sum_i-sum_j\ge s_j$，此时前缀 $i$ 最后一个划分点可以是 $j$。 现在我们来说明对于其它满足 $sum_i-sum_k\ge s_k$ 且 $k<j$ 的 $k$，前缀 $i$ 以 $j$ 为最后一个划分点 一定不劣于 以 $k$ 为最后一个划分点。 我们分别考虑以 $j,k$ 为划分点时，整个前缀的所有划分点。 首先，下面这种情况是不存在的。  在这种情况下，因为 $B$ 可以作为前缀 $C$ 的划分点，所以 $sum_D-sum_B> sum_C-sum_B\ge s_B$，且 $sum_D-sum_B<sum_D-sum_A=s_D$，前后仍然满足，于是 $B$ 作为前缀 $D$ 的划分点一定可行，而由归纳假设，我们可以得到，$D$ 一定不会以 $A$ 为划分点。 于是最终一定是下面两种情况之一。   其中第一条红线为两种划分下的最后一个公共划分点(这里把 $0$ 也看成了划分点)。 两种情况的区别仅仅在于公共划分点之后的第一个划分点属于前一种划分还是后一种划分。 然后除了第一种划分中最后的若干个划分点，其它的划分点都满足交替出现。 注意到我们只需要先说明 $j$ 比 $l$ 优，再说明 $l$ 比 $k$ 优即可，所以现在只考虑下面这两种情况。   设前一种划分中公共划分点之后的每一段数字和为 $a_1,a_2,...,a_{n1}$，后一种划分为 $b_1,b_2,...,b_{n2}$ 现在我们不考虑原序列，只考虑这两个 $a,b$ 序列，我们要证明 $\sum_{i=1}^{n1} a_i^2\le \sum_{i=1}^{n2} b_i^2$ 我们来通过一些操作使 $a$ 和 $b$ 相同，并且要求对 $a$ 的操作不使 $a$ 更优，对 $b$ 的操作不使 $b$ 更劣，这样我们就可以推出 $a$ 不劣于 $b$ 了。 在两种情况中，如果 $b_1+1<b_{n2}$，那么我们找到最小 $l$ 满足 $b_l!=b_1$，找到最大的 $b_r$ 满足 $b_r!=b_{n2}$。 然后给 $b_{l-1}+1$，给 $b_{r+1}-1$，这样会使 $b$ 在满足 $b_i\le b_{i+1}$ 的同时变得更优。 如果这时存在 $b$ 序列的一个前缀和 $a$ 序列的一个前缀相等，我们就将 $a,b$ 从这个前缀的位置断开，分成两个子序列，将问题划分为两个子问题。可以看出，在子问题中，仍然满足划分点交替出现。我们一直进行这个操作，直到不能进行为止。 这时，我们有 $b_1=b_{n2}$ 或 $b_1=b_{n2}-1$ 由于 $a_{n1}<b_{n2}$，所以 $a_{n1}\le b_1$，所以 $\forall i\in[1,n1],a_i\le b_1$ 如果有 $n1=n2$，那么两个序列一定完全相同。 否则有 $n1=n2+1$，此时我们去掉 $a_1$，将 $a$ 重新编号，然后对于所有 $i\in[1,n2]$ 给 $a_i$ 加一个数，使之变为 $b_i$，则 $a$ 与 $b$ 相同了。注意到在这个过程中，我们使一个较小的数变小，较大的数变大，会使 $a$ 变得更劣。 于是，我们通过一些操作，使得 $a$ 与 $b$ 相同，并且所有对 $b$ 的操作都是使之更优，所有对 $a$ 的操作都是使之更劣，就可以得到 $a$ 不劣于 $b$。 这样就证明完了。 具体实现可以用单调队列，需要手写高精度。 复杂度 $O(n)$ 代码 ```cpp #include<cstdio> #include<cstring> #include<algorithm> #include<cassert> using namespace std; namespace io { const int N=1<<20; char buf[N],*t1=buf,*t2=buf; #define getc() t1==t2&&(t2=(t1=buf)+fread(buf,1,N,stdin),t1==t2)?EOF:*t1++ inline int read() { static int an;an=0; static char ch;ch=getc(); while(ch<48||ch>57)ch=getc(); while(ch>=48&&ch<=57)an=(an<<3)+(an<<1)+(ch^48),ch=getc(); return an; } } using io::read; int n,op,f[40000010]; long long sum[40000010]; namespace task1 { long long dp[51][50050]; void solve() { for(int i=1;i<=n;++i) { for(int j=0;j<=50000;++j)dp[i][j]=0x3f3f3f3f3f3f3f3fll; for(int k=0;k<i;++k)dp[i][sum[i]-sum[k]]=dp[k][sum[i]-sum[k]]+(sum[i]-sum[k])*(sum[i]-sum[k]); for(int j=1;j<=50000;++j)dp[i][j]=min(dp[i][j],dp[i][j-1]); } printf("%lld",dp[n][sum[n]]); } } int x,y,z,m,p[100010],l[100010],r[100010],b[40000010],pos=1; int rnd(int i) { if(i>2)b[i]=(b[i-1]*x+b[i-2]*y+z)&((1<<30)-1); if(i>p[pos])++pos; return b[i]%(r[pos]-l[pos]+1)+l[pos]; } int q[40000010],h,t; struct data { int a[4]; friend data operator * (data a,data b) { static long long C[4]; static data c; memset(C,0,sizeof(C)); for(int i=0;i<4;++i) for(int j=0;i+j<4;++j) C[i+j]+=1ll*a.a[i]*b.a[j]; for(int i=0;i<4;++i) if(C[i]>999999999) { C[i+1]+=C[i]/1000000000; C[i]%=1000000000; } for(int i=0;i<4;++i)c.a[i]=C[i]; return c; } friend data operator + (data a,data b) { static long long C[4]; static data c; memset(C,0,sizeof(C)); for(int i=0;i<4;++i)C[i]=a.a[i]+b.a[i]; for(int i=0;i<4;++i) if(C[i]>1000000000) { C[i+1]+=C[i]/1000000000; C[i]%=1000000000; } for(int i=0;i<4;++i)c.a[i]=C[i]; return c; } }cur,ans; void print(data x) { static int st[100],tp; for(int i=0;i<=3;++i) { int w=x.a[i]; for(int j=0;j<9;++j)st[++tp]=w%10,w/=10; } while(tp>1&&!st[tp])--tp; while(tp)putchar(st[tp]^48),--tp; } int main() { // freopen("partition.in","r",stdin); // freopen("partition.out","w",stdout); n=read(),op=read(); if(!op) { for(int i=1;i<=n;++i)sum[i]=read(); } else { x=read(),y=read(),z=read(),b[1]=read(),b[2]=read(),m=read(); for(int i=1;i<=m;++i)p[i]=read(),l[i]=read(),r[i]=read(); for(int i=1;i<=n;++i)sum[i]=rnd(i); } long long mx=0; for(int i=1;i<=n;++i)mx=max(mx,sum[i]),sum[i]+=sum[i-1]; if(n<=50&&mx<=1000) { task1::solve(); return 0; } h=0,t=0; for(int i=1;i<=n;++i) { while(h<t&&sum[q[h+1]]+sum[q[h+1]]-sum[f[q[h+1]]]<=sum[i])++h; f[i]=q[h]; while(h<=t&&sum[q[t]]+sum[q[t]]-sum[f[q[t]]]>=sum[i]+sum[i]-sum[f[i]])--t; q[++t]=i; } int x=n; while(x) { cur.a[0]=(sum[x]-sum[f[x]])%1000000000; cur.a[1]=(sum[x]-sum[f[x]])/1000000000; cur.a[2]=cur.a[3]=0; ans=ans+cur*cur; x=f[x]; } print(ans); return 0; } ```