智商训练中
缓慢更新中.jpg
J. Jealous Split
想不到的转化方式系列(
最优的划分方案一定是和的平方的和最小的子段划分方案
这东西直接$wqs$二分+斜率优化解决就行了
下面证明一下这个结论
考虑一个划分点$k$
不妨设将$k$右移到$k_1$之后,平方和会变小
也就是说,对于左侧来说,它增加了从$k$到$k_1$这一部分的和,而右边减小了这个和
设这段和为$s$
条件即转化为:$(s_1+s)^2 + (s_2-s)^2 <{s_1}^2 + {s_2}^2$
整理一下
$2*s(s1-s2)+2s^2<0$
$s1-s2+s<0$
然后我们再假设,第一种划分是合法的
于是有$(s_1-s_2)^2$ < $t^2$($t$是$max$)
接下来我们要证明第二种划分也是合法的
对于第二种划分方案来说:
左侧=$|s_1+s-(s_2-s)|=|s_1 - s_2 +2s|$
左侧的平方:
$(s_1 - s_2)^2 +4s^2+4s*(s_1 - s_2)$<$t^2$+$4s*(s+s_1 -s_2)$<$t^2$
也就是说新的这个划分也一定是合法的划分
决策点左移类似的证即可
也就是说我们证明了,如果让平方和更小,一定不会令答案更劣
于是也就是说,找平方和最小的答案即可。
瞎yy一下这玩意怎么想的(
考虑两个端点固定的进行一次划分
可以发现的是,要让$|s_1 - s_2|$尽可能地小
也就是说$|s_1|$ 和 $|s_2|$要尽可能地靠近
又有$|s_1| + |s_2|$是个定值
$s_1^{2} + s_2^{2} +2*(s_1*s_2)$是个定值
这时候要最小化$s_1^{2}+s_2^{2}-2*(s_1*s_2)$ 也就是$t-4*(s_1*s_2)$
也就是说,这个划分要让两边的乘积尽可能大
$s_1*s_2$认为是左侧的乘上右侧的,其实这个值就会是$sum^2$ - (左侧单独两两乘法) - (右侧单独两两乘法)
而$sum^2$固定,也就是让左侧单独两两乘法,右侧单独两两乘法的和最大。
这种两两乘法,常用套路就是考虑和的平方,然后就会考虑到让左侧和做个平方,右侧和做个平方,出现左侧单独两两乘法,右侧单独两两乘法的情况,因为要最大化这个东西,所以其实是要最小化左侧和的平方和右侧和的平方的和。
于是就转化到原结论上了
虽然有朝着这个方面想过但是变量太多了就寄了,呜呜
#include<bits/stdc++.h> using namespace std; inline void read(__int128 &X) { X = 0; int w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); if (w) X = -X; } void print(__int128 x) { if (!x) return ; if (x < 0) putchar('-'),x = -x; print(x / 10); putchar(x % 10 + '0'); } int N,M; int lst[100005]; __int128 ans,x[100005],Sum[100005],dp[100005],g[100005],mx[100005]; int que[100005]; __int128 Getx(int pos){ return Sum[pos]; } __int128 Gety(int pos){ return dp[pos]+Sum[pos]*Sum[pos]; } bool Check(__int128 mid){ //print(mid); //cout<<endl; for (int i=1;i<=N;i++) g[i]=mx[i]=0; int head=1,tail=1; que[1]=0; for (int i=1;i<=N;i++){ __int128 nn=2ll*Sum[i]; while (head<tail && nn*(Getx(que[head+1])-Getx(que[head])) > (Gety(que[head+1])-Gety(que[head]))) head++; dp[i]=dp[que[head]]+((Sum[i]-Sum[que[head]])*(Sum[i]-Sum[que[head]])+mid); g[i]=g[que[head]]+1; while (head<tail && (Gety(que[tail])-Gety(que[tail-1]))*(Getx(i)-Getx(que[tail-1])) > (Gety(i)-Gety(que[tail-1]))*(Getx(que[tail])-Getx(que[tail-1]))) tail--; que[++tail]=i; } if (g[N]<=M) return true; else return false; } int main(){ //freopen("data.in","r",stdin); //freopen("test1.out","w",stdout); scanf("%d%d",&N,&M); for (int i=1;i<=N;i++){ read(x[i]); Sum[i]=Sum[i-1]+x[i]; } __int128 l=0,r=1e20; while (l<=r){ __int128 mid=(l+r)>>1ll; if (Check(mid)) r=mid-1,ans=mid; else l=mid+1; } Check(ans); __int128 val=dp[N]-M*ans; vector<int> b; b.push_back(N); for (int i=N-1;i;i--){ __int128 nw=(Sum[b.back()]-Sum[i])*(Sum[b.back()]-Sum[i]); if (g[i]+1<=M && dp[i]-(M-1)*ans+nw==val) { b.push_back(i); --M; val-=nw; } } reverse(b.begin(),b.end()); printf("Yes\n"); for (auto xx:b) if (xx!=N) printf("%d ",xx); return 0; }