CF 板刷计划

感觉最近需要提升一下思维水平，于是就准备刷CF的题目。
刷题内容：CF1300开始，评分大致在 \([1000,2200]\)。

为了防止代码过长代码只给出核心部分，缺省源和数组大小（maxn 和 maxm 的定义）请自行补上。

CF1300B（\(*1000\)）
不难发现，对于任意的一个 \(i\le n\)，能够作为匹配的 \(a_j-a_i\) 的 \(j\) 都大于 \(n+1\)，这样只需要将原序列排序，答案就为 \(a_{n+1}-a_n\)，算法复杂度 \(O\left(n\log n\right)\)，瓶颈在于排序。

int n,nn,a[maxn];
void work(){
	n=read(); nn=n<<1; int i,j; for(i=1;i<=nn;i++) a[i]=read(); sort(a+1,a+nn+1);
	print(a[n+1]-a[n]); pc('\n'); return;
}

CF1300C/CF1299A（\(*1500\)）
按位计算可以证明 (x|y)-y 和 x&(~y) 是等价的，所以只需要算出 ~a[i] 的前缀和和后缀和，扫一次求最大值就可以了，算法复杂度 \(\Theta\left(n\right)\)。

int n,a[maxn],pre[maxn],suf[maxn],maxx,ans;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(); int i; for(i=1;i<=n;i++) a[i]=read(); if(n==1){ print(a[1]); return 0; }
	pre[0]=~0; for(i=1;i<=n;i++) pre[i]=pre[i-1]&(~a[i]);
	suf[n+1]=~0; for(i=n;i>=1;i--) suf[i]=suf[i+1]&(~a[i]);
	maxx=-1; for(i=1;i<=n;i++) if((pre[i-1]&a[i]&suf[i+1])>maxx) maxx=pre[i-1]&a[i]&suf[i+1],ans=i;
	print(a[ans]); for(i=1;i<=n;i++) if(i^ans) pc(' '),print(a[i]); return 0;
}

CF1300D/CF1299B（\(*1800\)）
分析一下样例，不难发现就是判断所给出的多边形是否是中心对称即可。因此如果 \(n\) 为奇数，那么就显然不是，否则记 \(k=\frac{n}{2}\)，判断对于任意的 \(1\le i \le k\)，\(x_i+x_{i+k}\) 和 \(y_i+y_{i+k}\) 都是否为定值即可，算法复杂度 \(\Theta\left(n\right)\)。

int n,nn,x[maxn],y[maxn],sx,sy;
int check(){
	if(n&1) return 0; int i; nn=n>>=1; sx=x[1]+x[1+nn]; sy=y[1]+y[1+nn];
	for(i=2;i<=nn;i++) if(sx!=x[i]+x[i+nn]||sy!=y[i]+y[i+nn]) return 0;
	return 1;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(); int i; for(i=1;i<=n;i++) x[i]=read(),y[i]=read();
	if(check()) puts("YES"); else puts("NO"); return 0;
}

CF1300E/CF1299C（\(*2100\)）
观察样例三，不难发现答案单调不降（可以用反证法证明），因此使用单调栈维护。栈中存储一段元素的和与区间，如果栈顶区间的平均值比栈顶下面的元素小，那么就合并栈顶两个元素。最后输出即可，算法复杂度 \(\Theta\left(n\right)\)。
注意比较平均值的时候不要用来除（而是乘），还要开 long long。

int n,a[maxn];
struct JTZ{
	ll len,sum;
	bool operator < (const JTZ x) const { return this->sum*x.lenlen; }
	JTZ operator + (const JTZ x) const { return (JTZ){this->len+x.len,this->sum+x.sum}; }
}data[maxn]; int top; db ave;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(); int i,j; for(i=1;i<=n;i++) a[i]=read();
	for(i=1;i<=n;i++){
		top++; data[top].sum=a[i],data[top].len=1;
		while(top>=2&&data[top]

int n,maxd,a[maxn];
int check(int x){
	int kl=0,kr=1e9,i;
	for(i=1;i<=n;i++) if(a[i]==-1){
		if(a[i-1]!=-1&&i>1) kl=mmax(kl,a[i-1]-x),kr=mmin(kr,a[i-1]+x);
		if(a[i+1]!=-1&&i1) kl=mmax(kl,a[i-1]-x),kr=mmin(kr,a[i-1]+x);
		if(a[i+1]!=-1&&i>1; if(check(mid)) r=mid; else l=mid; }
	printans(r); return;
}

ll n,m,a,b,cnt1,cnt2;
void work(){
	n=read(); m=read(); a=(n-m)/(m+1); b=a+1; cnt2=(n-m)%(m+1); cnt1=m+1-cnt2;
	print(n*(n+1)/2-cnt1*a*(a+1)/2-cnt2*b*(b+1)/2),pc('\n');
}