T1魔法阵
当 n= \(8\),因为要考虑到所有点,所以要在 \(3\)~\(7\) 中找 \(8\) 的因数,因为只有 \(4\),所以只能变成正四边形,如图,只需要枚举两次,因为第三次之后就重复了。那么答案就是对这两种可能求和再取最大值。
//我这里对于a数组用了前缀和
for(int i=3;i<n;i++)
if(n%i==0)
for(int j=0;j<n/i;j++){
int res=0;
for(int p=j;p<n;p+=n/i)
res+=a[p];
ans=max(res,ans);
}
T2小biu放牛
我们要贪心把牛放在最前面,那么牛头的位置就是 \(i-t-x\) ;但是题目要求不能重叠,用 \(max\) 比较一下,确定牛头的位置在哪,这样保证了靠前。再用头部的位置,判断是否越界。最后还要判断一下尾部有没有越界(前面因为这个卡了好久)。
每次没必要一个一个贪心,可以通过二分优化
bool pd(int t){ //贪心
int head=0,tail=0;
for(int i=1;i<=n;i++){
head=max(tail,a[i]-t-x);
if(abs(head-a[i]+x)>t) return false;
tail=head+2*x;
if(tail>m) return false;
}
return true;
}