JSOI2018 Day2 部分题解

T1 LOJ#2549. 「JSOI2018」战争

考试的时候打了个期望70分的半平面交，无奈学校的OJ跑的实在太慢了一直是40（LOJ和本机最慢的点都只要0.7s），非常气愤！

正解又是比较偏门的知识点，Minkowski addition （闵可夫斯基和），中文资料好像比较少，个人认为Wikipedia上说的基本上够用了。

我们观察这玩意的定义式，如果我们把B集合的所有向量都取负，再分别叠加到A集合中，可以得到O(n^2)个向量，那么这些向量会构成一个点集，我们对这个点集求凸包，那么，只要我们的方向向量的终点落在这个凸包中，则在该方向向量作用下进行平移，能保证两个集合有交集。

这刚好符合“闵可夫斯基和”的定义，而对于两个凸包，我们可以用线性时间复杂度求出他们的闵可夫斯基和。具体做法就是把凸包差分成自由向量，之后将这些向量首尾相接，即按照极角序直接归并起来，最后求出第一个点的真实坐标（就是两个凸包中第一个点向量和），然后整个凸包就可以求出来了。

最后，问题就转化为了判断一个点是否在多边形内部，我们可以二分出一个三角形，卡出这个点的范围，之后叉积判断方向就做完了。

知识点偏门，还卡暴力算法常数，真是一道好(毒)题(瘤)。

#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
#define mxn 100005
#define ll long long
using namespace std;
char ibuf[65536],*ih,*it,outp[3*mxn];
#define getc() ((ih==it&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it))?0:*ih++)
inline int read(){
	int s=0,f=1; char ch=getc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc();
	return s*f;
}
struct pnt{int x,y;};
inline pnt operator + (pnt a,pnt b){return (pnt){a.x+b.x,a.y+b.y};}
inline pnt operator - (pnt a,pnt b){return (pnt){a.x-b.x,a.y-b.y};}
inline ll operator * (pnt a,pnt b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
inline bool operator < (const pnt &a,const pnt &b) {return a.x==b.x?a.y<b.y:a.x<b.x;}
inline bool operator == (const pnt &a,const pnt &b){return a.x==b.x&&a.y==b.y;}
int qh,qt;
inline int ConvexHull(pnt *pt,pnt *cv,pnt *q,int cnt){
	q[qt=1]=pt[1];
	for(int i=2;i<=cnt;++i){
		while(qt>1&&(pt[i]-q[qt-1])*(q[qt]-q[qt-1])<=0) --qt;
		q[++qt]=pt[i];
	}
	int ret=0;
	for(int i=1;i<=qt;++i) cv[++ret]=q[i];
	q[qt=1]=pt[cnt];
	for(int i=cnt-1;i>=1;--i){
		while(qt>1&&(pt[i]-q[qt-1])*(q[qt]-q[qt-1])<=0) --qt;
		q[++qt]=pt[i];
	}
	for(int i=2;i<qt;++i) cv[++ret]=q[i];
	return ret;
}
pnt p1[mxn],p2[mxn],tmp[mxn],tmp2[mxn];
pnt q1[mxn],q2[mxn],cc[mxn],c[mxn];
int n,m,tot,cas;
inline bool judge(pnt x){
	if(((x-c[1])*(c[2]-c[1])<0)||(c[tot]-c[1])*(x-c[1])<0) return 0;
	int L=1,M,R=tot;
	while(R>L){
		M=L+R>>1;
		if((x-c[1])*(c[M]-c[1])<=0) R=M;
		else L=M+1;
	}
	if((c[R]-c[R-1])*(x-c[R-1])<=0) return 1;
	else return 0;
}
int main(){
	n=read(),m=read(),cas=read();
	for(int i=1;i<=n;++i) p1[i].x=read(),p1[i].y=read();
	for(int i=1;i<=m;++i) p2[i].x=-read(),p2[i].y=-read();
	sort(&p1[1],&p1[n+1]),sort(&p2[1],&p2[m+1]);
	n=ConvexHull(p1,tmp,tmp2,n);
	for(int i=1;i<=n;++i) p1[i]=tmp[i];
	m=ConvexHull(p2,tmp,tmp2,m);
	for(int i=1;i<=m;++i) p2[i]=tmp[i];
	p1[n+1]=p1[1],p2[m+1]=p2[1];
	for(int i=1;i<=n;++i) q1[i]=p1[i+1]-p1[i];
	for(int i=1;i<=m;++i) q2[i]=p2[i+1]-p2[i];
	int pt1=1,pt2=1;
	while(pt1<=n&&pt2<=m){
		if(q1[pt1]*q2[pt2]<=0) cc[++tot]=q1[pt1++];
		else cc[++tot]=q2[pt2++];
	}
	while(pt1<=n) cc[++tot]=q1[pt1++];
	while(pt2<=m) cc[++tot]=q2[pt2++];
	c[1]=p1[1]+p2[1];
	++tot;
	for(int i=2;i<=tot;++i) c[i]=c[i-1]+cc[i-1];
	sort(&c[1],&c[tot+1]),tot=unique(&c[1],&c[tot+1])-c-1;
	tot=ConvexHull(c,tmp,tmp2,tot);
	for(int i=1;i<=tot;++i) c[i]=tmp[i];
	pnt ask;
	int po=0;
	while(cas--){
		ask.x=read(),ask.y=read();
		outp[po++]=judge(ask)+'0';
		if(cas)outp[po++]='\n';
	}
	puts(outp);
}

#pragma GCC optimize("-O3")

#include <bits/stdc++.h>

#define mxn 100005

#define ll long long

using namespace std;

char ibuf[65536],*ih,*it,outp[3*mxn];

#define getc() ((ih==it&&((it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it))?0:*ih++)

inline int read(){

int s=0,f=1; char ch=getc();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();}

while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc();

return s*f;

}

struct pnt{int x,y;};

inline pnt operator + (pnt a,pnt b){return (pnt){a.x+b.x,a.y+b.y};}

inline pnt operator - (pnt a,pnt b){return (pnt){a.x-b.x,a.y-b.y};}

inline ll operator * (pnt a,pnt b){return 1ll*a.x*b.y-1ll*a.y*b.x;}

inline bool operator < (const pnt &a,const pnt &b) {return a.x==b.x?a.y<b.y:a.x<b.x;}

inline bool operator == (const pnt &a,const pnt &b){return a.x==b.x&&a.y==b.y;}

int qh,qt;

inline int ConvexHull(pnt *pt,pnt *cv,pnt *q,int cnt){

q[qt=1]=pt[1];

for(int i=2;i<=cnt;++i){

while(qt>1&&(pt[i]-q[qt-1])*(q[qt]-q[qt-1])<=0) --qt;

q[++qt]=pt[i];

}

int ret=0;

for(int i=1;i<=qt;++i) cv[++ret]=q[i];

q[qt=1]=pt[cnt];

for(int i=cnt-1;i>=1;--i){

while(qt>1&&(pt[i]-q[qt-1])*(q[qt]-q[qt-1])<=0) --qt;

q[++qt]=pt[i];

}

for(int i=2;i<qt;++i) cv[++ret]=q[i];

return ret;

}

pnt p1[mxn],p2[mxn],tmp[mxn],tmp2[mxn];

pnt q1[mxn],q2[mxn],cc[mxn],c[mxn];

int n,m,tot,cas;

inline bool judge(pnt x){

if(((x-c[1])*(c[2]-c[1])<0)||(c[tot]-c[1])*(x-c[1])<0) return 0;

int L=1,M,R=tot;

while(R>L){

M=L+R>>1;

if((x-c[1])*(c[M]-c[1])<=0) R=M;

else L=M+1;

}

if((c[R]-c[R-1])*(x-c[R-1])<=0) return 1;

else return 0;

}

int main(){

n=read(),m=read(),cas=read();

for(int i=1;i<=n;++i) p1[i].x=read(),p1[i].y=read();

for(int i=1;i<=m;++i) p2[i].x=-read(),p2[i].y=-read();

sort(&p1[1],&p1[n+1]),sort(&p2[1],&p2[m+1]);

n=ConvexHull(p1,tmp,tmp2,n);

for(int i=1;i<=n;++i) p1[i]=tmp[i];

m=ConvexHull(p2,tmp,tmp2,m);

for(int i=1;i<=m;++i) p2[i]=tmp[i];

p1[n+1]=p1[1],p2[m+1]=p2[1];

for(int i=1;i<=n;++i) q1[i]=p1[i+1]-p1[i];

for(int i=1;i<=m;++i) q2[i]=p2[i+1]-p2[i];

int pt1=1,pt2=1;

while(pt1<=n&&pt2<=m){

if(q1[pt1]*q2[pt2]<=0) cc[++tot]=q1[pt1++];

else cc[++tot]=q2[pt2++];

}

while(pt1<=n) cc[++tot]=q1[pt1++];

while(pt2<=m) cc[++tot]=q2[pt2++];

c[1]=p1[1]+p2[1];

++tot;

for(int i=2;i<=tot;++i) c[i]=c[i-1]+cc[i-1];

sort(&c[1],&c[tot+1]),tot=unique(&c[1],&c[tot+1])-c-1;

tot=ConvexHull(c,tmp,tmp2,tot);

for(int i=1;i<=tot;++i) c[i]=tmp[i];

pnt ask;

int po=0;

while(cas--){

ask.x=read(),ask.y=read();

outp[po++]=judge(ask)+'0';

if(cas)outp[po++]='\n';

}

puts(outp);

}

T2 LOJ#2550. 「JSOI2018」机器人

太(我)毒(不)了(会)= =

T3 LOJ#2551. 「JSOI2018」列队

清真的数据结构，考场上不太想调一个log的了，于是码完两个log的就放弃了梦想。事实证明一个log的比两个log的还好写，我们只要判断当前区间是否完全合法就好了，如果完全合法就去右儿子，同时统计当前左儿子的答案，否则继续去左儿子，最后判一下叶子节点就好了。

#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
#define mxn 500005
#define ll long long
using namespace std;
char ibuf[65536],*ih,*it;
#define getc() ((ih==it&&(it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it)?0:*ih++)
inline int read(){
	int s=0,f=1; char ch=getc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc();
	return s*f;
}
int n,q,s[mxn];
struct node *null;
struct node{
	node *l,*r;
	int v;
	ll sum;
}*scur,*stot,*rt[mxn];
inline void init(){
	rt[0]=null=new node;
	null->l=null->r=null;
	null->v=null->sum=0;
}
inline node* newnode(node *x=null){
	if(scur==stot) scur=new node[1<<14],stot=scur+(1<<14);
	node *ret=scur++;
	ret->l=x->l,ret->r=x->r,ret->v=x->v,ret->sum=x->sum;
	return ret;
}
int pos;
inline node* update(node *p,int l,int r){
	node *o=newnode(p);
	if(l==r) ++o->v,o->sum+=l;
	else {
		int m=l+r>>1;
		if(pos<=m) o->l=update(p->l,l,m);
		else o->r=update(p->r,m+1,r);
		++o->v,o->sum+=pos;
	}
	return o;
}
int lim,res1;
ll sum[mxn],res2;
inline ll query(int l,int r,int p){
	int L=1,M,R=lim;
	node *r1=rt[l-1],*r2=rt[r];
	res1=res2=0;
	bool dir;
	while(R>L){
		M=L+R>>1;
		if(res1+r2->l->v-r1->l->v+p<=M){
			R=M;
			r1=r1->l,r2=r2->l;
			dir=0;
		}
		else{
			L=M+1,res1+=r2->l->v-r1->l->v,res2+=r2->l->sum-r1->l->sum;
			r1=r1->r,r2=r2->r;
			dir=1;
		}
	}
	if(p+r2->v-r1->v+res1>=L) res1+=r2->v-r1->v,res2+=r2->sum-r1->sum;
	R=res1;
	ll all=1ll*(p+p+r-l)*(r-l+1)/2,ret=(1ll*(p+p+R-1)*R/2-res2)+((sum[r]-sum[l-1])-res2)-(all-1ll*(p+p+R-1)*R/2);
	return ret;
}

int main(){
	n=read(),q=read();
	for(int i=1;i<=n;++i) s[i]=read(),sum[i]=sum[i-1]+s[i];
	init();
	for(int i=1;i<=n;++i) if(lim<s[i]) lim=s[i];
	for(int i=1;i<=n;++i) pos=s[i],rt[i]=update(rt[i-1],1,lim);
	register int l,r,p;
	while(q--){
		l=read(),r=read(),p=read();
		printf("%lld\n",query(l,r,p));
	}
}

#pragma GCC optimize("-O3")

#include <bits/stdc++.h>

#define mxn 500005

#define ll long long

using namespace std;

char ibuf[65536],*ih,*it;

#define getc() ((ih==it&&(it=(ih=ibuf)+fread(ibuf,1,65536,stdin)),ih==it)?0:*ih++)

inline int read(){

int s=0,f=1; char ch=getc();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getc();}

while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getc();

return s*f;

}

int n,q,s[mxn];

struct node *null;

struct node{

node *l,*r;

int v;

ll sum;

}*scur,*stot,*rt[mxn];

inline void init(){

rt[0]=null=new node;

null->l=null->r=null;

null->v=null->sum=0;

}

inline node* newnode(node *x=null){

if(scur==stot) scur=new node[1<<14],stot=scur+(1<<14);

node *ret=scur++;

ret->l=x->l,ret->r=x->r,ret->v=x->v,ret->sum=x->sum;

return ret;

}

int pos;

inline node* update(node *p,int l,int r){

node *o=newnode(p);

if(l==r) ++o->v,o->sum+=l;

else {

int m=l+r>>1;

if(pos<=m) o->l=update(p->l,l,m);

else o->r=update(p->r,m+1,r);

++o->v,o->sum+=pos;

}

return o;

}

int lim,res1;

ll sum[mxn],res2;

inline ll query(int l,int r,int p){

int L=1,M,R=lim;

node *r1=rt[l-1],*r2=rt[r];

res1=res2=0;

bool dir;

while(R>L){

M=L+R>>1;

if(res1+r2->l->v-r1->l->v+p<=M){

R=M;

r1=r1->l,r2=r2->l;

dir=0;

}

else{

L=M+1,res1+=r2->l->v-r1->l->v,res2+=r2->l->sum-r1->l->sum;

r1=r1->r,r2=r2->r;

dir=1;

}

if(p+r2->v-r1->v+res1>=L) res1+=r2->v-r1->v,res2+=r2->sum-r1->sum;

R=res1;

ll all=1ll*(p+p+r-l)*(r-l+1)/2,ret=(1ll*(p+p+R-1)*R/2-res2)+((sum[r]-sum[l-1])-res2)-(all-1ll*(p+p+R-1)*R/2);

return ret;

}

int main(){

n=read(),q=read();

for(int i=1;i<=n;++i) s[i]=read(),sum[i]=sum[i-1]+s[i];

init();

for(int i=1;i<=n;++i) if(lim<s[i]) lim=s[i];

for(int i=1;i<=n;++i) pos=s[i],rt[i]=update(rt[i-1],1,lim);

while(q--){

l=read(),r=read(),p=read();

printf("%lld\n",query(l,r,p));

}

Narcissus' Blog

一道图论计数好题：《两弹一星》

16.5.18 考试小记

Scott

叨叨几句... NOTHING

取消回复

Narcissus' Blog