我想注册网站怎么做,定制高端网站建设报价,the word 和 wordpress,大型网站开发基本流程[ABC102D] Equal Cut - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:找在区间[2,n-1]中找到i,j,k三个点,把序列分割成4个区间:[1,i],[i1,j],[j1,k],[k1,n] 暴力的做法是枚举i,j,k加上前缀和是o(n^3)的 key:考虑枚举处于中间的j#xff0c;然后用i平衡左两个区间,…[ABC102D] Equal Cut - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:找在区间[2,n-1]中找到i,j,k三个点,把序列分割成4个区间:[1,i],[i1,j],[j1,k],[k1,n] 暴力的做法是枚举i,j,k加上前缀和是o(n^3)的 key:考虑枚举处于中间的j然后用i平衡左两个区间,用k右两个区间 如果想四个区间总和的极差最小,那么i和k肯定是处于平衡点中.i尽量平衡左两个区间,k尽量平衡右两个区间. 因为在枚举j,第二个区间是增长的,第一个区间是不变的那么i需要往右靠 类似的,那么第三个区间是减少的,第四个区间是不变的那么k也需要往右靠 i和k都要根据每次j的移动找到平衡点.而新的平衡点肯定是在原本的基础上往右移动或不动.!
int n;
int pre[200005];
题意:把序列分为四个连续的区间使得max(sum1,sum2,sum3,sum4)-min(sum1,sum2,sum3,sum4)最小
思路:找在区间[2,n-1]中找到i,j,k三个点,把序列分割成4个区间:[1,i],[i1,j],[j1,k],[k1,n]
暴力的做法是枚举i,j,k加上前缀和是o(n^3)的
key:考虑枚举处于中间的j然后用i平衡左两个区间,用k右两个区间
如果想四个区间总和的极差最小,那么i和k肯定是处于平衡点中.i尽量平衡左两个区间,k尽量平衡右两个区间.
因为在枚举j,第二个区间是增长的,第一个区间是不变的那么i需要往右靠
类似的,那么第三个区间是减少的,第四个区间是不变的那么k也需要往右靠
i和k都要根据每次j的移动找到平衡点.而新的平衡点肯定是在原本的基础上往右移动或不动.!
[ABC102D] Equal Cut
https://www.luogu.com.cn/problem/AT_arc100_b
void solve(){ D 区间..补题补题cinn;for(int i1;in;i) {cinpre[i];pre[i]pre[i-1];}int ans1e15;int i1,j2,k3;while(jn-1){ jn-1这里是前两个区间在作差,如果i移动前的区间差值比i移动后的区间差值大那么i进行移动两个区间的差值便缩小了i往右移动时,区间一在递增区间二在递减这样总会存在一个最小的区间差值.后两个区间同理.while(i1jabs(pre[j]-pre[i]-pre[i])abs(pre[j]-pre[i1]-pre[i1])) i; 加绝对值while(k1nabs(pre[n]-pre[k]-(pre[k]-pre[j]))abs(pre[n]-pre[k1]-(pre[k1]-pre[j]))) k;ansmin(ans,max({pre[i],pre[j]-pre[i],pre[k]-pre[j],pre[n]-pre[k]})-min({pre[i],pre[j]-pre[i],pre[k]-pre[j],pre[n]-pre[k]}));j;}coutans;
}
还没补出来的题:
Unlucky Numbers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--数位dp
[ABC297G] Constrained Nim 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)--sg函数
[ABC108D] All Your Paths are Different Lengths - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)-紫
