T1 LOJ#2549. 「JSOI2018」战争
考试的时候打了个期望70分的半平面交,无奈学校的OJ跑的实在太慢了一直是40(LOJ和本机最慢的点都只要0.7s),非常气愤!
正解又是比较偏门的知识点,Minkowski addition (闵可夫斯基和),中文资料好像比较少,个人认为Wikipedia上说的基本上够用了。
我们观察这玩意的定义式,如果我们把B集合的所有向量都取负,再分别叠加到A集合中,可以得到O(n^2)个向量,那么这些向量会构成一个点集,我们对这个点集求凸包,那么,只要我们的方向向量的终点落在这个凸包中,则在该方向向量作用下进行平移,能保证两个集合有交集。
这刚好符合“闵可夫斯基和”的定义,而对于两个凸包,我们可以用线性时间复杂度求出他们的闵可夫斯基和。具体做法就是把凸包差分成自由向量,之后将这些向量首尾相接,即按照极角序直接归并起来,最后求出第一个点的真实坐标(就是两个凸包中第一个点向量和),然后整个凸包就可以求出来了。
最后,问题就转化为了判断一个点是否在多边形内部,我们可以二分出一个三角形,卡出这个点的范围,之后叉积判断方向就做完了。
知识点偏门,还卡暴力算法常数,真是一道好(毒)题(瘤)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#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的还好写,我们只要判断当前区间是否完全合法就好了,如果完全合法就去右儿子,同时统计当前左儿子的答案,否则继续去左儿子,最后判一下叶子节点就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#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)); } } |
叨叨几句... NOTHING