2023.5.16练习赛总结

发布时间 2023-05-16 16:40:33作者: hn小曜仔

T1魔法阵

image

当 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;
}