看心情填坑

AK了开心来写题解

A、B不讲

C：给出两个点，以这两个点分别以r₁,r₂为半径作两个圆，要求r₁²+r₂²最小并覆盖平面上其他几个点，求这个值。

把要覆盖的点按到第一个圆心的距离排序，然后扫一遍维护到第二个圆心的最大值。瓶颈在排序O(nlogn)然而只有2000所以暴力也行

#include<cstdio>
#include<algorithm>
using namespace std;
struct point{
	int x,y;
}p[2005],p1,p2;
int n;
long long now,ans;
long long dis(point k1,point k2){return 1LL*(k1.x-k2.x)*(k1.x-k2.x)+1LL*(k1.y-k2.y)*(k1.y-k2.y);}
bool cmp(point k1,point k2){return dis(k1,p1)<dis(k2,p1);}
int main(){
	scanf("%d%d%d%d%d",&n,&p1.x,&p1.y,&p2.x,&p2.y);
	for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
	p[0]=p1;
	sort(p+1,p+1+n,cmp);
	now=dis(p2,p[n]);
	ans=dis(p1,p[n]);
	for(int i=n;i;i--){
		if(dis(p2,p[i])>now)now=dis(p2,p[i]);
		if(now+dis(p[i-1],p1)<ans)ans=now+dis(p[i-1],p1);
	}
	printf("%I64d",ans);
}

D：给出平面上3个点，要你用一条折线经过这三个点，求折线最少要分几段（可以理解成最少折几次+1）

特判题_(:зゝ∠)_房间里两个插人狂魔丧心病狂像我从来不插人（其实是不知道怎么插）

具体看代码自己YY一下就好了

#include<cstdio>
using namespace std;
struct point{
	int x,y;
}p[3];
int main(){
	for(int i=0;i<3;i++)scanf("%d%d",&p[i].x,&p[i].y);
	if((p[0].x==p[1].x)&&(p[0].x==p[2].x)){
		printf("1");
		return 0;
	}
	if((p[0].y==p[1].y)&&(p[0].y==p[2].y)){
		printf("1");
		return 0;
	}
	if(p[0].x==p[1].x){
		if(p[0].y>p[1].y){
			point t=p[0];
			p[0]=p[1];
			p[1]=t;
		}
		if((p[2].y>p[0].y)&&(p[2].y<p[1].y))printf("3");
		else printf("2");
		return 0;
	}
	if(p[1].x==p[2].x){
		if(p[1].y>p[2].y){
			point t=p[1];
			p[1]=p[2];
			p[2]=t;
		}
		if((p[0].y>p[1].y)&&(p[0].y<p[2].y))printf("3");
		else printf("2");
		return 0;
	}
	if(p[0].x==p[2].x){
		if(p[0].y>p[2].y){
			point t=p[0];
			p[0]=p[2];
			p[2]=t;
		}
		if((p[1].y>p[0].y)&&(p[1].y<p[2].y))printf("3");
		else printf("2");
		return 0;
	}
	if(p[0].y==p[1].y){
		if(p[0].x>p[1].x){
			point t=p[0];
			p[0]=p[1];
			p[1]=t;
		}
		if((p[2].x>p[0].x)&&(p[2].x<p[1].x))printf("3");
		else printf("2");
		return 0;
	}
	if(p[1].y==p[2].y){
		if(p[1].x>p[2].x){
			point t=p[1];
			p[1]=p[2];
			p[2]=t;
		}
		if((p[0].x>p[1].x)&&(p[0].x<p[2].x))printf("3");
		else printf("2");
		return 0;
	}
	if(p[0].y==p[2].y){
		if(p[0].x>p[2].x){
			point t=p[0];
			p[0]=p[2];
			p[2]=t;
		}
		if((p[1].x>p[0].x)&&(p[1].x<p[2].x))printf("3");
		else printf("2");
		return 0;
	}
	printf("3");
}

E：给出n,m,k，n个数，和m个询问，每次询问询问区间内有多少组(i,j)满足区间[i,j]之间的数亦或起来等于k，n,m<=10W,k<=100W

看一眼非常流弊，看第二眼可以离线，10W估计标算是数据结构，不管了直接莫队上。本来想挂hash链的，一看k<=100W呵呵我才不会告诉你我数组真的开了100W然后RE一发呢

#include<cstdio>
#include<algorithm>
#define size 316
using namespace std;
int n,m,k,x,L,R;
int sum[2000001];
long long A[100005];
int s[100005];
long long ans;
struct query{
	int l,r,k;
}q[100005];
bool cmp(query q1,query q2){
	if(q1.l/size==q2.l/size)return q1.r<q2.r;
	else return q1.l/size<q2.l/size;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		s[i]=s[i-1]^x;
	}
	for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].k=i;
	for(int i=1;i<=m;i++)q[i].l--;
	sort(q+1,q+1+m,cmp);
	for(int i=q[1].l;i<=q[1].r;i++){
		ans+=sum[k^s[i]];
		sum[s[i]]++;
	}
	A[q[1].k]=ans;L=q[1].l;R=q[1].r;
	for(int i=2;i<=m;i++){
		while(L>q[i].l){
			L--;
			ans+=sum[k^s[L]];
			sum[s[L]]++;
		}
		while(R<q[i].r){
			R++;
			ans+=sum[k^s[R]];
			sum[s[R]]++;
		}
		while(L<q[i].l){
			sum[s[L]]--;
			ans-=sum[k^s[L]];
			L++;
		}
		while(R>q[i].r){
			sum[s[R]]--;
			ans-=sum[k^s[R]];
			R--;
		}
		A[q[i].k]=ans;
	}
	for(int i=1;i<=m;i++)printf("%I64d\n",A[i]);
}