计算几何
又开了一个坑= =
首先是tsinsen的A1420 裸的动态凸包
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> #include <set> using namespace std; #define eps 1e-8 struct Point { double a1,a2; } t; bool operator< (const Point &x,const Point &y) { double d=atan2(x.a2-t.a2,x.a1-t.a1),f=atan2(y.a2-t.a2,y.a1-t.a1), o=(x.a1-t.a1)*(x.a1*t.a1)+(x.a2-t.a2)*(x.a2*t.a2), p=(y.a1-t.a1)*(y.a1*t.a1)+(y.a2-t.a2)*(y.a2*t.a2); return d+eps<f||fabs(d-f)<eps&&o<p;} multiset <Point> li; set <Point> :: iterator it,ti; int n,m; inline int Read() { int x=0;char y;bool z=0; do y=getchar(),z|=y=='-'; while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return z?-x:x; } void Set_up() { Point a[4];double q=0,w=0,e,k;int i,j,l; for (int i=1;i<=3;i++) Read(),k=Read(),e=Read(),a[i].a1=k,a[i].a2=e,q+=k,w+=e; t.a1=q/3;t.a2=w/3; for (int i=1;i<=3;i++) li.insert(a[i]); return; } inline double Cha(Point x,Point y,Point z) { return ((y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1)); } void Insert(Point x) { int i,j,k,l;Point q,w,e; it=li.lower_bound(x); if (it==li.end()||it==li.begin()) it=li.end(),q=*(--it),w=*(li.begin());else w=*(it--),q=*it;ti=it; if (Cha(q,x,w)<=eps) return; while (li.size()>2) { if (it==li.begin()) it=li.end(); e=*(--it); if (Cha(e,q,x)<=eps) li.erase(ti);else break; ti=it;q=e; } it=ti=li.lower_bound(w); while (li.size()>2) { it++;if (it==li.end()) it=li.begin(); e=*(it); if (Cha(x,w,e)<=eps) li.erase(ti);else break; ti=it;w=e; } li.insert(x); return; } bool Check(Point x) { int i,j,k,l;Point q,w,e; if (x.a1==t.a1&&x.a2==t.a2) return 1; it=li.lower_bound(x); if (it==li.end()) it=li.begin(); ti=it==li.begin()?li.end():it;ti--; return Cha(*ti,x,*it)<=eps; } int main() { int i,j,q,w,e;Point k,l; scanf("%d",&n); li.clear(); Set_up(); for (i=4;i<=n;i++) { m=i; q=Read();k.a1=Read();k.a2=Read(); if (q==1) Insert(k);else if (Check(k)) printf("YES\n");else printf("NO\n"); } return 0; }
然后是BZOJ1069,凸包+单调性乱搞
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 4050 #define eps 1e-8 #define INF 0x7f7f7f7f struct Point { double a1,a2; } a[N],mi; int n,m,li[N],ri; double ans=0; bool operator== (const Point &x,const Point &y) {return fabs(x.a1-y.a1)<eps&&fabs(x.a2-y.a2)<eps;} bool operator!= (const Point &x,const Point &y) {return fabs(x.a1-y.a1)>eps||fabs(x.a2-y.a2)>eps;} inline double Cha(Point x,Point y,Point z) {return ((y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1));} inline double sqr(double x) {return x*x;} inline double dis(Point x,Point y) {return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));} inline double max(double x,double y) {return x<y?y:x;} inline double Square(Point x,Point y,Point z) { return fabs((y.a1-x.a1)*(z.a2-x.a2)-(y.a2-x.a2)*(z.a1-x.a1))/2; } inline bool cmp(Point x,Point y) { double i=atan2(x.a2-a[n].a2,x.a1-a[n].a1), j=atan2(y.a2-a[n].a2,y.a1-a[n].a1); return i+eps<j||(fabs(i-j)<eps&&dis(x,a[n])+eps<dis(y,a[n])); } void Init() { int i,k; memset(li,0,sizeof(li)); scanf("%d",&n); mi.a1=mi.a2=INF; for (i=1;i<=n;i++) { scanf("%lf%lf",&a[i].a1,&a[i].a2); if (a[i].a1<mi.a1||(a[i].a1==mi.a1&&a[i].a2<mi.a2)) mi=a[k=i]; } swap(a[k],a[n]); return; } void Graham() { li[1]=n;li[ri=2]=1; while (a[li[2]]==a[li[1]]&&li[2]<n) li[2]++; if (li[2]==n) {ri--;return;} for (int i=li[2]+1;i<n;i++) if (a[i]!=a[li[ri]]) { while (ri-1&&Cha(a[li[ri-1]],a[li[ri]],a[i])+eps<0) ri--; li[++ri]=i; } while (ri-2&&Cha(a[li[ri-1]],a[li[ri]],a[1])+eps<0) ri--; return; } void Solve() { int i,j,k,l;double q,w,e; for (i=1;i<=ri;i++) li[i+ri]=li[i]; for (i=1;i<ri;i++) { k=0;j=i+1;q=0;w; for (l=1;l<=ri;l++) if ((w=Square(a[li[i]],a[li[l]],a[li[j]]))>q) k=l,q=w; l=i+1; for (;j<=ri;j++) { while (Square(a[li[i]],a[li[j]],a[li[k+1]])> Square(a[li[i]],a[li[j]],a[li[k]])) k++; while (l<j&&Square(a[li[i]],a[li[j]],a[li[l+1]])> Square(a[li[i]],a[li[j]],a[li[l]])) l++; q=Square(a[li[i]],a[li[j]],a[li[l]]); if (k!=l) q+=Square(a[li[i]],a[li[j]],a[li[k]]); ans=max(ans,q); } } return; } int main() { Init(); sort(a+1,a+n,cmp); Graham(); Solve(); printf("%.3lf\n",ans); return 0; }
BZOJ1043 裸的求圆交点
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 1050 #define eps 1e-8 const double pi=acos(-1.0); struct Point { double a1,a2; } a[N],b[N]; double r[N],ans=0; int n,m,ri; inline double min(double x,double y) {return x<y?x:y;} inline double max(double x,double y) {return x>y?x:y;} inline double sqr(double x) {return x*x;} inline double dis(Point x,Point y) {return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));} inline double cmp(Point x,Point y) {return x.a1+eps<y.a1||(fabs(x.a1-y.a1)<eps&&x.a2<y.a2);} inline bool Intersect(int x,int y) { int i,j,k,l;double q=dis(a[x],a[y]),w,e; if (q+eps>=r[x]+r[y]||(r[y]>r[x]&&r[y]-r[x]+eps>=q)) return 0; if (q<=r[x]-r[y]+eps) return 1; w=atan2(a[x].a2-a[y].a2,a[x].a1-a[y].a1); e=acos((sqr(r[y])+sqr(q)-sqr(r[x]))/(2*r[y]*q)); b[ri].a1=w-e;b[ri].a2=w+e; if (b[ri].a1+eps<-pi) b[++ri].a1=b[ri-1].a1+2*pi,b[ri].a2=pi,b[ri-1].a1=-pi;else if (b[ri].a2>pi+eps) b[++ri].a2=b[ri-1].a2-2*pi,b[ri].a1=-pi,b[ri-1].a2=pi; ri++; return 0; } double Solve(int x) { int i,j,k,l;double q=0,w,e;ri=1; for (i=1;i<x;i++) if (Intersect(i,x)) return 0; sort(b+1,b+ri,cmp); for (i=2;i<ri;i++) if (b[i].a1+eps<=b[i-1].a2) b[i].a1=min(b[i].a1,b[i-1].a1), b[i].a2=max(b[i].a2,b[i-1].a2), b[i-1].a1=b[i-1].a2=0; for (i=1;i<ri;i++) q+=(b[i].a2-b[i].a1)*r[x]; return 2*pi*r[x]-q; } int main() { int i,j,k,l,q,w,e; memset(r,0,sizeof(r)); scanf("%d",&n); for (i=n;i>=1;i--) scanf("%lf%lf%lf",&r[i],&a[i].a1,&a[i].a2); for (i=1;i<=n;i++) ans+=Solve(i); printf("%.3lf\n",ans); return 0; }
BZOJ2300:看一眼吓傻,完全不知道有删点的动态凸包怎么做= =只记得好像有论文上面提到过,感觉巨神于是没管了= =后来发现没有加点操作,就是倒着搞的SB题了= =。然后因为某些细节一直没调出来,后来坑到了数据才过了= =。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; #define N 200050 #define eps 1e-9 struct Point { double a1,a2; } a[N]; set <Point> li; set <Point> :: iterator it,ti; int n,m,qu[N][2];double ans=0,cnt[N];bool b[N]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline double sqr(double x) {return x*x;} inline double dis(Point x,Point y) {return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));} inline double Cha(Point x,Point y,Point z) {return (y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1);} bool operator< (const Point &x,const Point &y) { double q=atan2(x.a2,x.a1),w=atan2(y.a2,y.a1); return q+eps<w||(fabs(q-w)<eps&&x.a1*x.a1+x.a2*x.a2< y.a1*y.a1+y.a2*y.a2);} void Set_up() { int i,j;Point k,l;double q=Read(),w=Read(),e=Read(); li.insert(k=(Point){q,0});li.insert(l=(Point){w,e}); li.insert((Point){0,eps}); ans=dis((Point){0,0},l)+dis(l,k); return; } inline void Insert(Point x) { int i,j;Point k,l;double q,w,e; it=li.lower_bound(x);ti=it;ti--;k=*it;l=*ti; if (Cha(l,x,k)<=eps) return; ans=ans-dis(k,l); do { ti=it;++it; if (it==li.end()||Cha(x,*ti,*it)>eps) break; ans=ans-dis(*ti,*it); li.erase(ti); } while (1); ans+=dis(x,*ti); it=li.lower_bound(l); do { ti=it;--it; if (ti==li.begin()||Cha(*it,*ti,x)>eps) break; ans=ans-dis(*ti,*it); li.erase(ti); } while (1); ans+=dis(x,*ti);li.insert(x); return; } void Solve() { for (int i=1;i<=m;i++) if (qu[i][0]==1) b[qu[i][1]]=1; for (int i=1;i<=n;i++) if (!b[qu[i][0]]) Insert(a[i]); for (int i=m;i>=1;i--) if (qu[i][0]==2) cnt[i]=ans;else Insert(a[qu[i][1]]); for (int i=1;i<=m;i++) if (qu[i][0]==2) printf("%.2lf\n",cnt[i]); return; } int main() { int i,j,k,l,q,w,e; memset(qu,0,sizeof(qu));memset(b,0,sizeof(b)); memset(cnt,0,sizeof(cnt)); Set_up();n=Read(); for (i=1;i<=n;i++) a[i].a1=Read(),a[i].a2=Read(); m=Read(); for (i=1;i<=m;i++) { qu[i][0]=Read(); if (qu[i][0]==1) qu[i][1]=Read(); } Solve(); return 0; }
maya颓了好久终于把这个鬼畜半平面交搞出来了,要注意的是跟前面一样,“孩子cmp函数写挫了你就废了”,被一堆细节wa了n次= =
BZOJ2618:裸半平面交,坑比的是在BZOJ上过得了在codevs上怎么都过不了= =本来以为是有什么猥琐的细节,但是换了4个其他程序用出错的数据拍了n久硬是没发现问题。话说这个感觉还是写的好丑【捂脸贼】
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 1050 #define eps 1e-8 const double pi=acos(-1.0); struct Point { double x,y; } b[N]; struct Line { Point x,y;double v; } a[N]; int n=0,m,t,ri,li[N],le=1;double ans=0; Point operator+ (const Point &x,const Point &y) {return (Point){x.x+y.x,x.y+y.y};} Point operator- (const Point &x,const Point &y) {return (Point){x.x-y.x,x.y-y.y};} double operator* (const Point &x,const Point &y) {return x.x*y.y-x.y*y.x;} inline bool cmp(Line x,Line y) { if (x.v!=y.v) return x.v<y.v; return (x.y-x.x)*(y.y-x.x)>0; } inline int Read() { int x=0;char y;bool z=0; do y=getchar(),z|=y=='-'; while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return z?-x:x; } inline Point Intersect(Line x,Line y) { double k=(y.x-x.x)*(y.y-x.x),l=(y.y-x.y)*(y.x-x.y); double q=k/(k+l);Point p;p=x.y-x.x; p.x=x.x.x+p.x*q;p.y=x.x.y+p.y*q; return p; } inline bool Cao(Line x,Line y,Line z) { Point k=Intersect(x,y); return (k-z.x)*(k-z.y)<=eps; } void Solve() { int i,j;Point k,l;double q,w,e;int tot=0; sort(a+1,a+n+1,cmp); a[n+1].v=-2*pi; for (i=1;i<=n;i++) { if (a[i].v!=a[i-1].v) tot++; a[tot]=a[i]; } li[ri=1]=1;le=1;li[ri=2]=2;n=tot; for (i=3;i<=n;i++) { while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--; while (ri-le&&Cao(a[li[le+1]],a[li[le]],a[i])) le++; li[++ri]=i; } while (ri-le&&Cao(a[li[ri]],a[li[le]],a[li[le+1]])) le++; while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--; for (i=le;i<ri;i++) b[i-le+1]=Intersect(a[li[i]],a[li[i+1]]); b[ri-le+1]=Intersect(a[li[ri]],a[li[le]]); if (ri-le+1<3) return; for (i=1,ri=ri-le+1;i<ri;i++) ans+=b[i]*b[i+1]; ans+=b[ri]*b[1]; return; } int main() { t=Read(); for (int i=1;i<=t;i++) { Point q,w,e; m=Read();q.x=Read(),q.y=Read();w=q; for (int j=2;j<=m;j++) e.x=Read(),e.y=Read(),a[++n]=(Line){w,e, atan2(e.y-w.y,e.x-w.x)},w=e; a[++n]=(Line){w,q,atan2(q.y-w.y,q.x-w.x)}; } Solve(); printf("%.3lf\n",ans/2); return 0; }
BZOJ1038瞭望塔:又是一个半平面交的裸题,又被细节坑了好久= =
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 1050 #define M 1e12 #define eps 1e-8 const double pi=acos(-1.0); struct Point { double x,y; } b[N],c[N]; struct Line { Point x,y;double v; } a[N]; int n=0,m=0,li[N]; double ans=2*M; Point operator+ (const Point &x,const Point &y) {return (Point){x.x+y.x,x.y+y.y};} Point operator- (const Point &x,const Point &y) {return (Point){x.x-y.x,x.y-y.y};} double operator* (const Point &x,const Point &y) {return x.x*y.y-x.y*y.x;} bool operator< (const Line &x,const Line &y) {return x.v!=y.v?x.v<y.v:(x.y-x.x)*(y.y-x.x)>0;} inline double min(double x,double y) {return x<y?x:y;} inline double sqr(double x) {return x*x;} inline double dis(Point x,Point y) {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));} inline int Read() { int x=0;char y;bool z=0; do y=getchar(),z|=y=='-'; while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return z?-x:x; } inline Point Intersect(Line x,Line y) { double q=(y.x-x.x)*(y.y-x.x),w=(y.y-x.y)*(y.x-x.y); w=q/(w+q);Point e=x.y-x.x;e.x=x.x.x+e.x*w; e.y=x.x.y+e.y*w;return e; } inline bool Cao(Line x,Line y,Line z) {Point k=Intersect(x,y);return (k-z.x)*(k-z.y)<=eps;} void Set_up() { int i,j;Point k,l,q,w,e; n=Read(); for (i=1;i<=n;i++) b[i].x=Read(); for (i=1;i<=n;i++) b[i].y=Read(); m=n-1; for (i=1;i<=m;i++) a[i].x=b[i],a[i].y=b[i+1], a[i].v=atan2(b[i+1].y-b[i].y,b[i+1].x-b[i].x); k.x=k.y=l.x=w.y=-M;q.x=q.y=l.y=w.x=M; a[++m].x=w;a[m].y=q;a[m].v=pi/2; a[++m].x=q;a[m].y=l;a[m].v=pi; a[++m].x=l;a[m].y=k;a[m].v=-pi/2; a[++m].x=k;a[m].y=w;a[m].v=0; return; } void Half_Inter() { int i,j,tot=0,le,ri;Point k,l;double q,w,e; sort(a+1,a+m+1); for (i=1;i<=m;i++) { if (a[i].v!=a[i-1].v) tot++; a[tot]=a[i]; } le=1;ri=2;li[1]=1;li[2]=2; for (i=3;i<=tot;i++) { while (ri-le&&Cao(a[li[le]],a[li[le+1]],a[i])) le++; while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--; li[++ri]=i; } while (ri-le&&Cao(a[li[ri]],a[li[le]],a[li[le+1]])) le++; while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--; for (i=le,ri=m=ri-le+1;i<le+ri-1;i++) c[i-le+1]=Intersect(a[li[i]],a[li[i+1]]); c[ri]=Intersect(a[li[le]],a[li[le+ri-1]]); return; } inline void Check(Point x) { Line q;int i;q.x=q.y=x;q.y.y=M+1; if (x.x<b[1].x||x.x>b[n].x) return; for (int i=1;i<n;i++) if (x.x>=b[i].x&&x.x<=b[i+1].x) ans=min(ans,dis(Intersect(q,(Line){b[i],b[i+1],0}),x)); return; } inline void cHeck(Point x) { Line q;int i;q.x=q.y=x;q.y.y=-M-1; for (int i=1;i<m;i++) if ((x.x>=c[i].x)^(x.x>c[i+1].x)) ans=min(ans,dis(Intersect(q,(Line){c[i],c[i+1],0}),x)); return; } int main() { memset(li,0,sizeof(li)); Set_up(); Half_Inter(); for (int i=1;i<=m;i++) Check(c[i]); for (int i=1;i<=n;i++) cHeck(b[i]); printf("%.3lf\n",ans); return 0; }
BZOJ3190赛车:也是裸半平面交,真是一路wa。TATQAQ2333改完细节之后代码好丑= =
#include <iostream> #include <cmath> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; #define N 10050 #define eps 1e-8 const double pi=acos(-1.0); struct Point { double x,y; }; struct Line { Point x,y;double v;int sg; } a[N]; int n,m,s=0,li[N],le,ri;bool c[N]; Point operator+ (const Point &x,const Point &y) {return (Point){x.x+y.x,x.y+y.y};} Point operator- (const Point &x,const Point &y) {return (Point){x.x-y.x,x.y-y.y};} double operator* (const Point &x,const Point &y) {return x.x*y.y-x.y*y.x;} bool operator< (const Line &x,const Line &y) {return (x.v<y.v)||(x.v==y.v&&(x.y-x.x)*(y.y-x.x)>eps);} bool operator!= (const Point &x,const Point &y) {return x.x!=y.x||x.y!=y.y;} bool operator!= (const Line &x,const Line &y) {return x.v!=y.v||x.x!=y.x;} inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline Point Intersect(Line x,Line y) { Point e;double q=(y.x-x.x)*(y.y-x.x),w=(y.y-x.y)*(y.x-x.y); w=q/(q+w);e=x.y-x.x;e.x=x.x.x+e.x*w;e.y=x.x.y+e.y*w; return e; } inline bool Cao(Line x,Line y,Line z) {Point k=Intersect(x,y);return (k-z.x)*(k-z.y)<-eps;} void Half_Inter() { int i,j,tot=0;Point k,l,q,w,e; sort(a+1,a+n+1);i=1;k.x=0; while (i<n) {if (a[i]!=a[i+1]) k=Intersect(a[i],a[i+1]);if (k.x>-eps) break;i++;} li[1]=i;li[2]=i+1;le=1;ri=2; if (i==n) ri--; for (i+=2;i<=n;i++) { while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--; li[++ri]=i; } while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--; while (ri-le) { i=le;while (i<ri&&!(a[li[i]]!=a[li[i+1]])) i++; if (i==ri) break; k=Intersect(a[li[i]],a[li[i+1]]); if (k.x>-eps) break;le=i+1; } return; } int main() { int j; memset(li,0,sizeof(li));memset(c,0,sizeof(c)); scanf("%d",&n); for (int i=1;i<=n;i++) a[i].x.y=a[i].y.y=Read(); for (int i=1;i<=n;i++) a[i].y.y+=(a[i].v=Read()), a[i].y.x=1,a[i].sg=i; Half_Inter(); printf("%d\n",ri-le+1); for (int i=le;i<=ri;i++) c[a[li[i]].sg]=1; for (j=1;j<=n;j++) { if (c[j]) { if (ri-le) printf("%d ",j);else printf("%d\n",j); le++; } } return 0; }
BZOJ1027合金:看上去是三维球面上面的问题,实际上因为是球面,所以投影到坐标系平面上面问题还是等价的。然后就暴力建边跑floyd(之前一直以为n^3会比较有危险,而且还是这种时限四秒题,总觉得还有其它方法,真是naive!)。还有要注意题目里面的细节比如答案为1或2的时候要做讨论,真心被坑wa了n次
话说为毛每次我的笔记作了20页就会丢,真是丧心= =
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 550 #define eps 1e-8 #define INF 0x3f3f3f3f struct Point { double x,y; } a[N],b[N]; Point operator- (const Point &x,const Point &y) {return (Point){x.x-y.x,x.y-y.y};} double operator* (const Point &x,const Point &y) {return x.x*y.y-x.y*y.x;} bool operator== (const Point &x,const Point &y) {return fabs(x.x-y.x)<eps&&fabs(x.y-y.y)<eps;} int n,m,ss,h[N][N],tot=0,ans=INF; inline int Calc(Point x,Point y) { for (int i=1;i<=m;i++) { double q=(y-x)*(b[i]-x); if (fabs(q)>eps&&q<0) return INF; if (fabs(q)<eps&&((b[i].x-y.x)*(y.x-x.x)>eps|| (b[i].y-y.y)*(y.y-x.y)>eps)) return INF; if (fabs(q)<eps&&((b[i].x-x.x)*(x.x-y.x)>eps|| (b[i].y-x.y)*(x.y-y.y)>eps)) return INF; } return 1; } bool Check() { if (m==1) for (int i=1;i<=n;i++) if (a[i]==b[1]) { printf("1\n");return 1; } for (int i=3;i<=m;i++) if (fabs((b[i]-b[1])*(b[2]-b[1]))>eps) return 0; if (m==1) b[2]=b[1]; for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) if (fabs((a[j]-a[i])*(b[2]-b[1]))<eps) for (int k=1;k<=m;k++) { double l=b[k].x-a[i].x,q=b[k].x-a[j].x, w=b[k].y-a[i].y,e=b[k].y-a[j].y; if (fabs((a[i]-b[k])*(a[j]-b[k]))>eps) continue; if ((fabs(l)>eps&&fabs(q)>eps&&l*q>0)|| (fabs(w)>eps&&fabs(e)>eps&&w*e>0)) continue; printf("2\n");return 1; } return 0; } int main() { memset(h,0,sizeof(h)); scanf("%d%d",&n,&m);a[0].x=b[0].x=-1; for (int i=1;i<=n;i++) { scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[0].y); if (a[i].x!=a[i-1].x||a[i].y!=a[i-1].y) tot++; a[tot]=a[i]; } n=tot;tot=0; for (int i=1;i<=m;i++) { scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[0].y); if (b[i].x!=b[i-1].x||b[i].y!=b[i-1].y) tot++; b[tot]=b[i]; } m=tot;if (Check()) return 0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) h[i][j]=i!=j?Calc(a[i],a[j]):INF; for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) h[i][j]=min(h[i][j],h[i][k]+h[k][j]); for (int i=1;i<=n;i++) ans=min(ans,h[i][i]); printf("%d\n",ans==INF?-1:ans); return 0; }
颓颓颓!
madan最近好摆,感觉有很多事情要做但是没什么动力,还是很容易弃疗。
还是给自己来点硬性计划比较好
先是跟着yali的进度做点NOI前几年的题目,然后完成计算几何专题,之后就是做点数据结构题,前两项要在下周之内完成,毕竟没什么时间了。然后后面就是补一点XJOI的题目什么的,或者有雅兴开启BZOJ乱做模式。还有就是可以打比赛了吧。
感觉现在最需要的就是代码能力还有信心。前者就最近多找找时间练上去,感觉最近这段时间心态还不错,就希望能保持吧。
机会毕竟不多了,希望这次能好好把握吧。
匹配相关
还差一个一般图最大权匹配貌似就差不多了= =
匹配题目做得少,只好意思贴贴模板= =
Hungary(貌似没有网络流跑得快):
#include <iostream> #include <string.h> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 505 int a[N][N],c[N],n,m,s; bool b[N]; inline bool aa(int x) { int i; for (i=1;i<=n;i++) if (a[x][i] && !b[i]) { b[i]=1; if (!c[i] || aa(c[i])) { c[i]=x; return 1; } } return 0; } int main() { int i,j,k,l,q,w,e=0; memset(a,0,sizeof(a));memset(c,0,sizeof(c)); scanf("%d%d%d",&n,&m,&s); for (i=1;i<=s;i++) { scanf("%d%d",&k,&l); a[l][k]=1; } for (i=1;i<=m;i++) { memset(b,0,sizeof(b)); e+=aa(i); } printf("%d\n",e); for (i=1;i<=n;i++) printf("%d ",c[i]); printf("\n"); return 0; }
KM:
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <queue> using namespace std; #define N 1005 #define INF 0x3f7f7f7f #define ll long long struct Point { int a1;ll a2; bool operator < (const Point &x) const { return a2<x.a2||(a2==x.a2&&a1<x.a1); } }; set <Point> mi; set <Point> :: iterator it; ll s[N],v[N][2],h[N][N],ans=0; int p[N][2],la[N],n,m,nm; bool b[N][2]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } void DFS(int x) { int i=p[la[x]][0]; if (!x) return; p[x][1]=la[x];p[la[x]][0]=x; DFS(i); return; } void Solve(int x) { int i,j;ll q,w,e=0;Point k,l; while (!mi.empty()) { it=mi.begin();mi.erase(it);k=*it;k.a2+=e; if (k.a2) { e-=k.a2; for (i=1;i<=nm;i++) if (b[i][0]) v[i][0]-=k.a2; for (i=1;i<=nm;i++) if (b[i][1]) v[i][1]+=k.a2; } for (i=1;i<=nm;i++) if (b[i][0]&&v[i][0]+v[k.a1][1]==h[i][k.a1]) {la[k.a1]=i;break;} if (p[k.a1][1]) { b[k.a1][1]=b[p[k.a1][1]][0]=1; for (i=1;i<=nm;i++) if (!b[i][1]&&s[i]+e>v[i][1]+v[p[k.a1][1]][0]-h[p[k.a1][1]][i]) { l.a1=i;l.a2=s[i];it=mi.lower_bound(l);mi.erase(it); l.a2=s[i]=v[i][1]+v[p[k.a1][1]][0]-h[p[k.a1][1]][i]-e; mi.insert(l); } }else { DFS(k.a1);return; } } return; } int main() { int i,j,q,w,e;ll k,l; memset(s,0,sizeof(s));memset(v,0,sizeof(v)); memset(h,0,sizeof(h));memset(la,0,sizeof(la)); memset(p,0,sizeof(p));memset(b,0,sizeof(b)); scanf("%d%d%d",&n,&m,&e);nm=max(n,m); for (i=1;i<=e;i++) h[k=Read()][Read()]=Read(); for (i=1;i<=nm;i++) for (j=1;j<=nm;j++) v[i][0]=max(v[i][0],h[i][j]); for (i=1;i<=nm;i++) { memset(s,0,sizeof(s));memset(b,0,sizeof(b)); mi.clear();b[i][0]=1; for (j=1;j<=nm;j++) s[j]=v[j][1]+v[i][0]-h[i][j],la[j]=i, mi.insert((Point){j,s[j]}); Solve(i); } for (i=1;i<=n;i++) ans+=p[i][0]<=m?h[i][p[i][0]]:0; printf("%lld\n",ans); for (i=1;i<=n;i++) printf("%d ",p[i][0]>m||!h[i][p[i][0]]?0:p[i][0]); printf("\n"); return 0; }
带花树:
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 505 #define M 500050 #define INF 0x7f7f7f7f int p[N],pre[N],c[M][2],ss=1,vis[N],sta[N],n,m,st=0,li[M]; int fi[N],ri,fa[N],ans=0; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline void Line (int x,int y) { c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss; return; } int Find(int x) { return fa[x]==x?x:(fa[x]=Find(fa[x])); } int LCA(int x,int y) { for (x=Find(x),y=Find(y),st++;;swap(x,y)) if (x) { if (vis[x]==st) return x; vis[x]=st;x=Find(pre[p[x]]); } } void Blossom(int x,int y,int z) { while (Find(x)!=z) { pre[x]=y; if (sta[p[x]]==2) sta[li[++ri]=p[x]]=1; if (fa[x]==x) fa[x]=z; if (fa[p[x]]==p[x]) fa[p[x]]=z; x=pre[y=p[x]]; } return; } int Solve(int x) { int i,j,k,l,q,w,e,le=1; memset(pre,0,sizeof(pre));memset(vis,0,sizeof(vis)); memset(sta,0,sizeof(sta)); for (i=1;i<=n;i++) fa[i]=i;li[ri=sta[x]=1]=x; for (;le<=ri;le++) for (i=fi[li[le]];i;i=c[i][1]) if (!sta[c[i][0]]) { sta[c[i][0]]=2;pre[c[i][0]]=li[le]; if (!p[c[i][0]]) { for (k=c[i][0];k;) l=p[pre[k]],p[k]=pre[k],p[p[k]]=k,k=l; return 1; } sta[li[++ri]=p[c[i][0]]]=1; }else if (sta[c[i][0]]==1&&Find(c[i][0])!=Find(li[le])) j=LCA(li[le],c[i][0]),Blossom(li[le],c[i][0],j), Blossom(c[i][0],li[le],j); return 0; } int main() { int i,j,k,l,q,w,e; scanf("%d%d",&n,&m); for (i=1;i<=m;i++) Line(Read(),Read()); for (i=1;i<=n;i++) if (!p[i]) ans+=Solve(i); printf("%d\n",ans); for (i=1;i<=n;i++) printf("%d ",p[i]); printf("\n"); return 0; }
这些都可以在UOJ模板题库里面找到。
FFT
其实早在年初就学过几次FFT了,算导也翻过两遍,就是从没写过。
昨天做题目异常烦躁,于是滚去背了下FFT模板(本来是准备早自习抽个时间背的,但是发现这个还是蛮好背的,毕竟带花树都背下来了= =),然后水了两道题。
UOJ#34
贴个模板= =,其实我是从耗时少的里面随便找了一个@kiana的背的,虽然还没看懂这个非递归版本是怎么搞的(其实是不想去认真看了= =),反正感觉也够用了。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 300050 const double pi=acos(-1.0); struct complex { double r,i; complex (){} complex (double _r,double _i) {r=_r;i=_i;} } a[N],b[N],c[N]; complex operator+(const complex &A,const complex &B) {return complex(A.r+B.r,A.i+B.i);} complex operator-(const complex &A,const complex &B) {return complex(A.r-B.r,A.i-B.i);} complex operator*(const complex &A,const complex &B) {return complex(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);} int n,m,k,len,bit,rev[N]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } void FFT(complex* a,int n,int f) { for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int p=1;p<n;p <<= 1) { complex wn(cos(pi/p),sin(pi/p)*f); for (int i=0;i<n;i+=(p << 1)) { complex e(1,0); for (int j=0;j<p;j++,e=e*wn) { complex x=a[i+j],y=e*a[i+j+p]; a[i+j]=x+y;a[i+j+p]=x-y; } } } if (f!=1) for (int i=0;i<n;i++) a[i].r/=n; return; } int main() { n=Read()+1;m=Read()+1;k=n+m-1;len=1;bit=0; while (len<k) len <<= 1,bit++; for (int i=0;i<n;i++) a[i].r=Read(); for (int i=0;i<m;i++) b[i].r=Read(); for (int i=1;i<len;i++) rev[i]=(rev[i >> 1] >> 1)|((i&1) << (bit-1)); FFT(a,len,1);FFT(b,len,1); for (int i=0;i<len;i++) c[i]=a[i]*b[i]; FFT(c,len,-1); for (int i=0;i<k;i++) printf("%d ",(int)(c[i].r+0.5)); printf("\n"); return 0; }
BZOJ3527万径人踪灭:
其实就是统计回文子序列个数-回文子串个数,后者直接上manacher,前者就可以直接枚举字符直接套FFT算了。
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 300050 #define M 1000000007 #define eps 1e-2 #define ll long long const double pi=acos(-1.0); struct complex { double r,i; complex(){} complex(double _r,double _i) {r=_r;i=_i;} } a[N],b[N],c[N]; complex operator+(const complex &A,const complex &B) {return complex(A.r+B.r,A.i+B.i);} complex operator-(const complex &A,const complex &B) {return complex(A.r-B.r,A.i-B.i);} complex operator*(const complex &A,const complex &B) {return complex(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);} int n,m,len,bit,rev[N],ss,d[N],ft[N]; ll ans; void TAT(complex* a,int n,int f) { for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int p=1;p<n;p <<= 1) { complex wn(cos(pi/p),sin(pi/p)*f); for (int i=0;i<n;i+=(p << 1)) { complex e(1,0); for (int j=0;j<p;j++,e=e*wn) { complex x=a[i+j],y=e*a[i+j+p]; a[i+j]=x+y;a[i+j+p]=x-y; } } } if (f!=1) for (int i=0;i<n;i++) a[i].r/=n; return; } void QAQ() { int i,j,k,l,q,w,e; len=1;bit=0; while (ss>len) len <<= 1,bit++; for (i=1;i<len;i++) rev[i]=(rev[i >> 1] >> 1)|((i&1) << (bit-1)); TAT(a,len,1);TAT(b,len,1); for (i=0;i<len;i++) c[i]=a[i]*b[i]; TAT(c,len,-1); return; } ll Manacher() { int i,j,k,l,q,w,e;ll s; memset(ft,0,sizeof(ft)); q=s=0;e=-1; for (i=0;i<=ss;i++) { ft[i]=i>e?1:min(ft[2*q-i],e-i+1); while (i-ft[i]>=0&&i+ft[i]<=ss&&d[i-ft[i]]==d[i+ft[i]]) ft[i]++; if (i+ft[i]-1>e) { e=i+ft[i]-1;q=i; } s+=ft[i]/2; } return s%M; } inline ll Quick_mi(ll x,int y) { ll z=1; while (y) { if (y&1) z=(z*x)%M; x=(x*x)%M; y >>= 1; } return z; } int main() { int i,j,k,l,q,w,e,g[N];char f[N]; memset(d,0,sizeof(d));memset(rev,0,sizeof(rev)); scanf("%s",f);n=strlen(f); for (i=0;i<n;i++) d[i*2+1]=int(f[i]); ss=n*2;ans=(M-Manacher())%M;ss--; for (i=0;i<n;i++) a[i].r=b[i].r=f[i]=='a'; QAQ(); for (i=0;i<n;i++) a[i].r=b[i].r=f[i]!='a',a[i].i=b[i].i=0; for (i=n;i<len;i++) a[i].r=b[i].r=a[i].i=b[i].i=0; for (i=0;i<ss;i++) g[i]=(eps+c[i].r+(!(i&1)&&f[i/2]=='a'))/2; QAQ(); for (i=0;i<ss;i++) g[i]+=(eps+c[i].r+(!(i&1)&&f[i/2]=='b'))/2; for (i=0;i<ss;i++) ans=(ans+Quick_mi(2,g[i])-1)%M; cout <<ans<<endl; return 0; }
BZOJ3527力:
坑比lydsy没题面,我是到这里看的题。然后发现这个是可以化成卷积形式的,然后就直接FFT了= =
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 300050 #define ld long double #define eps (double)(1e-8) const double pi=acos(-1.0); struct complex { double r,i; complex (){} complex (ld _r,double _i) {r=_r;i=_i;} } a[N],b[N],c[N],f[N]; complex operator+ (const complex &A,const complex &B) {return complex(A.r+B.r,A.i+B.i);} complex operator- (const complex &A,const complex &B) {return complex(A.r-B.r,A.i-B.i);} complex operator* (const complex &A,const complex &B) {return complex(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);} double d[N]; int n,m,len,bit,rev[N]; void FFT(complex* a,int n,int f) { for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); for (int p=1;p<n;p <<= 1) { complex wn(cos(pi/p),sin(pi/p)*f); for (int i=0;i<n;i+=(p << 1)) { complex e(1,0); for (int j=0;j<p;j++,e=e*wn) { complex x=a[i+j],y=a[i+j+p]*e; a[i+j]=x+y;a[i+j+p]=x-y; } } } if (f!=1) for (int i=0;i<=n;i++) a[i].r/=n; return; } int main() { int i,j,k,l,q,w,e; memset(d,0,sizeof(d));memset(rev,0,sizeof(rev)); cin >>n;bit=0;len=1; for (i=0;i<n;i++) scanf("%lf",&d[i]), a[i].r=d[i]; for (i=1;i<n;i++) b[i].r=(double)1/i/i; while (len<n*2) len <<= 1,bit++; for (i=0;i<len;i++) rev[i]=(rev[i >> 1] >> 1)|((i&1) << (bit-1)); FFT(a,len,1);FFT(b,len,1); for (i=0;i<len;i++) c[i]=a[i]*b[i],c[i].r+=eps; FFT(c,len,-1); for (i=0;i<len;i++) a[i].r=b[i].r=a[i].i=b[i].i=0; for (i=0;i<n;i++) a[i].r=d[n-i-1],a[i].i=0,b[i].i=0; for (i=1;i<n;i++) b[i].r=(double)1/i/i; FFT(a,len,1);FFT(b,len,1); for (i=0;i<len;i++) f[i]=a[i]*b[i]; FFT(f,len,-1); for (i=0;i<n;i++) printf("%.3lf\n",c[i].r-f[n-i-1].r); return 0; }
话说最近的考试题目真是越来越sxbk了,鸿少的题目里面放了FFT也就算了,破太阳的题目里面放了多项式求逆。
等从杭州滚完粗回来就开推Picks的多项式专题
【捂脸贼】好像摆了半个月才开推啊
之前一直不知道有NTT这个东西,于是感觉要取模实在caodan
感觉NTT、多项式逆元、分治FFT也都不难理解的说。。
BZOJ3456城市规划
写的比较丑,反正就是NTT+高能逆元
好像确实时间常数炸翔了,不过在tsinson上面还是过了
复杂度反正算出来是一个log的
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 300050 #define M 1004535809 #define G 3 #define ll long long ll c[N],S[N],T[N],wn[20],jc[N],C[N]; int n,m,len,bit,rev[N]; ll Quick_Power(ll x,int y) { ll z=1; while (y) { if (y&1) z=z*x%M; x=x*x%M; y >>= 1; } return z; } void NTT(ll* a,int n,int f) { for (int i=0;i<n-1;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); int now=0; for (int p=1;p<n;p <<= 1) { now++; for (int i=0;i<n;i+=p << 1) { ll e=1; for (int j=0;j<p;j++,e=e*wn[now]%M) { ll x=a[i+j],y=e*a[i+j+p]%M; a[i+j]=(x+y)%M;a[i+j+p]=(x-y+M)%M; } } } if (f==-1) { for (int i=1;i<n >> 1;i++) swap(a[i],a[n-i]); ll Inv=Quick_Power(n,M-2); for (int i=0;i<n;i++) a[i]=a[i]*Inv%M; } } void Solve(int x) { if (x==1) {T[0]=Quick_Power(S[0],M-2);return;} Solve(x + 1 >> 1); len=1;bit=0; while (len<x*2-1) len <<= 1,bit++; for (int i=1;i<len;i++) rev[i]=((rev[i >> 1] >> 1) | ((i & 1) << (bit - 1))); for (int i=0;i<x;i++) c[i]=S[i]; for (int i=x;i<len;i++) c[i]=0; NTT(T,len,1);NTT(c,len,1); for (int i=0;i<len;i++) T[i]=T[i]*(2-T[i]*c[i]%M+M)%M; NTT(T,len,-1); for (int i=x;i<len;i++) T[i]=0; return; } int main() { cin >>n; for (int i=0;i<20;i++) wn[i]=Quick_Power(G,M - 1 >> i); jc[0]=1;C[0]=1; for (ll i=1,j=1;i<1 << 18;i++,j=j*i%M) jc[i]=Quick_Power(j,M-2),C[i]=Quick_Power(2,i*(i-1)/2%(M-1)); for (int i=-1;i<n;i++) S[n-i-1]=C[n-i-1]*jc[n-i-1]%M; Solve(n+1); len=1;bit=0; while (len<n*2-1) len <<= 1,bit++; for (int i=1;i<len;i++) rev[i]=((rev[i >> 1] >> 1) | ((i & 1) << (bit - 1))); for (int i=0;i<n;i++) S[i]=C[i+1]*jc[i]%M; NTT(S,len,1);NTT(T,len,1); for (int i=0;i<len;i++) c[i]=S[i]*T[i]%M; NTT(c,len,-1); cout <<c[n-1]*Quick_Power(jc[n-1],M-2)%M<<endl; return 0; }
然后再附上这题的分治解法,复杂度是log^2 n的,然而在tsinson上面交了一发后面4个点挂时间了
但是感觉这些东西都不算难写,只不过感觉难调
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define N 300050 #define M 1004535809 #define G 3 #define ll long long ll S[N],T[N],a[N],b[N],c[N],jc[N],cj[N],C[N],wn[20]; int n,m,rev[N]; ll Quick_Power(ll x,int y) { ll z=1; while (y) { if (y&1) z=z*x%M; x=x*x%M; y >>= 1; } return z; } void NTT(ll* a,int n,int f) { for (int i=1;i<n-1;i++) if (i<rev[i]) swap(a[i],a[rev[i]]); int now=1; for (int p=1;p<n;p <<= 1,now++) { for (int i=0;i<n;i+=p << 1) { ll e=1; for (int j=0;j<p;j++,e=e*wn[now]%M) { ll x=a[i+j],y=a[i+j+p]*e%M; a[i+j]=(x+y)%M;a[i+j+p]=(x-y+M)%M; } } } if (f==-1) { for (int i=1;i<n >> 1;i++) swap(a[i],a[n-i]); ll Inv=Quick_Power(n,M-2); for (int i=0;i<n;i++) a[i]=a[i]*Inv%M; } } void Solve(int x,int y) { int z=x + y >> 1,len,bit; if (x==y) {T[x]=(C[x+1]+M-T[x]*cj[x]%M)%M;return;} Solve(x,z); len=1;bit=0; while (len < y - x << 1) len <<= 1,bit++; for (int i=1;i<len;i++) rev[i]=(rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); for (int i=x;i<=z;i++) a[i-x]=T[i]*jc[i]%M; for (int i=z-x+1;i<len;i++) a[i]=0; for (int i=0;i<=y-x;i++) b[i]=S[i]; for (int i=y-x+1;i<len;i++) b[i]=0; NTT(a,len,1);NTT(b,len,1); for (int i=0;i<len;i++) a[i]=a[i]*b[i]%M; NTT(a,len,-1); for (int i=z-x+1;i<=y-x;i++) T[i+x]=(T[i+x]+a[i])%M; Solve(z+1,y); return; } int main() { cin >>n; for (int i=0;i<20;i++) wn[i]=Quick_Power(G,M - 1 >> i); jc[0]=C[0]=1;cj[0]=1; for (ll i=1;i<1 << 18;i++) jc[i]=Quick_Power(cj[i]=i*cj[i-1]%M,M-2), C[i]=Quick_Power(2,i*(i-1)/2%(M-1)); for (ll i=0;i<n;i++) S[i]=C[i]*jc[i]%M; Solve(0,n-1); cout <<T[n-1]%M<<endl; return 0; }
NOI题乱做
RT,放些最近写的NOI老题。
BZOJ3668起床困难综合症
直接爆搞
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 100050 #define INF 0x7f7f7f7f #define ll long long ll a[N][2],n,m,ans=0,ss,t=0; inline ll aa(int x) { ll i,j,k,l,q,w,e=x; for (i=1;i<=n;i++) if (a[i][0]==1) e=e&(a[i][1]&ss);else e=a[i][0]==2?e^(a[i][1]&ss):e|(a[i][1]&ss); return e; } int main() { ll i,j,k,l,q,w,e; char b[20]; memset(a,0,sizeof(a)); scanf("%lld%lld",&n,&m); for (i=1;i<=n;i++) { scanf("%s%lld",b,&a[i][1]); if (b[0]=='A'&&b[1]=='N') a[i][0]=1;else a[i][0]=b[0]=='X'&&b[1]=='O'?2:3; } for (ss=1 << 29;ss;ss >>= 1) { i=aa(0); j=t+ss>m?-1:aa(ss); if (i>=j) ans+=i;else ans+=j,t+=ss; } cout <<ans<<endl; return 0; }
BZOJ3669魔法森林:LCT
#include <iostream> #include <string.h> #include <stdio.h> #include <cmath> #include <algorithm> using namespace std; #define N 100050 #define INF 0x7f7f7f7f struct Line { int s,v,a1,b1; } a[N]; int c[N][2],t[N],fa[N],rf[N],ft[N],ma[N]; int n,m,ans=INF,ss; bool fz[N]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=(x << 3)+(x << 1)+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline bool cmp(Line x,Line y) { return x.a1<y.a1; } inline void Update(int x) { ma[x]=max(ma[c[x][0]],max(ma[c[x][1]],x>n?t[x]:-INF)); return; } inline void fzj(int x) { if (!x||!fz[x]) return; fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]]; swap(c[x][0],c[x][1]); fz[0]=fz[x]=0; return; } inline void Rotate(int x) { int i=fa[x],j=fa[fa[x]],k=x==c[i][0]; if (j) c[j][c[j][1]==i]=x;else rf[x]=rf[i],rf[i]=0; fa[c[x][k]]=c[x][k]?i:0; c[i][1-k]=c[x][k];fa[i]=x; c[x][k]=i;fa[x]=j; Update(i); return; } inline void DFS(int x) { if (fa[x]) DFS(fa[x]); fzj(x);fzj(c[x][0]);fzj(c[x][1]); return; } inline void Splay(int x) { DFS(x); while (fa[x]) { if (fa[fa[x]]) Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]); Rotate(x); } Update(x); return; } inline void Access(int x) { int i=0; while (x) { Splay(x); rf[c[x][1]]=fa[i]=x; fa[c[x][1]]=rf[i]=0; c[x][1]=i;Update(x); i=x;x=rf[x]; } rf[0]=fa[0]=0; return; } inline void Cg_rt(int x) { Access(x);Splay(x); fz[x]=1;fzj(x); return; } inline void Line(int x,int y) { Cg_rt(x);rf[x]=y; return; } inline void Delete(int x) { Splay(x);fa[c[x][0]]=fa[c[x][1]]=0; c[x][0]=c[x][1]=0; return; } inline int Lma(int x) { if (ma[x]==t[x]) return x;else return ma[c[x][0]]==ma[x]?Lma(c[x][0]):Lma(c[x][1]); } inline int Find(int x) { if (x==ft[x]) return x; ft[x]=Find(ft[x]); return ft[x]; } int main() { int i,j,k,l,q,w,e; memset(t,0,sizeof(t));memset(c,0,sizeof(c)); memset(fa,0,sizeof(fa));memset(rf,0,sizeof(rf)); memset(ft,0,sizeof(ft));memset(ma,0,sizeof(ma)); memset(fz,0,sizeof(fz)); scanf("%d%d",&n,&m); ma[0]=-INF; for (i=1;i<=n;i++) ft[i]=i; ss=n; for (i=1;i<=m;i++) scanf("%d%d%d%d",&a[i].s,&a[i].v,&a[i].a1,&a[i].b1); sort(a+1,a+m+1,cmp); for (i=1;i<=m;i++) if (a[i].s!=a[i].v) { k=Find(a[i].s);l=Find(a[i].v); if (k!=l) { ft[k]=l;t[++ss]=ma[ss]=a[i].b1; Line(a[i].s,ss);Line(a[i].v,ss); }else { Cg_rt(a[i].s);Access(a[i].v);Splay(a[i].v); k=Lma(a[i].v); if (t[k]>a[i].b1) { Delete(k);ma[k]=t[k]=a[i].b1; Line(a[i].s,k);Line(a[i].v,k); } } if (Find(1)==Find(n)) { Cg_rt(1);Access(n);Splay(n); ans=min(ans,a[i].a1+t[Lma(n)]); } } ans=ans==INF?-1:ans; cout <<ans<<endl; return 0; }
BZOJ3670动物园:建一棵Fail树(貌似也有的叫KMP自动机?),然后我写了个倍增,但是怎么调都只有60分(明明在本机上用同一组数据是答案正确的但是uoj上怎么都会错是smg?)。感觉最近都是的,未免对这种复杂度太有自信了吧= =,结果好几次都没去想正解就直接贴这种挂的代码。然后想线性的做法,en,没想出来,orzei了hzwer的(wulala说这个还算不难想吧,我思维弱已经成了常态了么= =),然后发现它确实是有性质的(还是看代码吧= =),然后可以搞到线性的。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 1000050 #define M 1000000007 #define ll long long ll ans; int la[N],h[N],n,m,t; char b[N]; int main() { int i,j,k,l,q,w,e; memset(la,0,sizeof(la));memset(h,0,sizeof(h)); scanf("%d ",&t); while (t--) { gets(b);n=strlen(b);h[1]=ans=1; for (i=2;i<=n;i++) { k=la[i-1]; while (k&&b[k]!=b[i-1]) k=la[k]; if (b[k]==b[i-1]) la[i]=k+1;else la[i]=0; h[i]=h[la[i]]+1; } k=0; for (i=2;i<=n;i++) { while (k&&b[k]!=b[i-1]) k=la[k]; if (b[k]==b[i-1]) k++; while (k>(i>>1)) k=la[k]; ans=(ans*(h[k]+1))%M; } printf("%lld\n",ans); } return 0; }
BZOJ3671随机数生成器:感觉题目一大串其实还不就是暴力,但是各种时间空间卡常数卡的丧心病狂,一开始用函数递归打标记MLE,然后用queue也是挂,然后换成了数组,最后把快读的变量都考虑进去了,都过不了= =,后来知道了还是要对于每一行维护左右边界,虽然复杂度一样,但是比起我这种常数还是要小些。
#include <iostream> #include <string.h> #include <cmath> #include <cstdio> #include <algorithm> #include <queue> using namespace std; #define N 5050 #define ll long long struct Point { int a1,a2; }; ll a,b,c,d,x0; int n,m,nm,wz[N*N],t[N*N],le[N],ri[N]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } void Sign(int x,int y) { for (int i=1;i<=n;i++) if (i<x) ri[i]=min(ri[i],y);else if (i>x) le[i]=max(le[i],y); return; } int main() { ll i,j,k,l,q,w,e; cin >>x0>>a>>b>>c>>d>>n>>m>>nm;k=n*m;e=n+m-1; for (i=1;i<=k;i++) t[i]=i; for (i=1;i<=k;i++) x0=((a*x0+b)*x0+c)%d,swap(t[x0%i+1],t[i]); for (i=1;i<=nm;i++) swap(t[q=Read()],t[l=Read()]); for (i=1;i<=n;i++) le[i]=1,ri[i]=m; for (i=1;i<=k;i++) wz[t[i]]=i; for (i=1;i<=k;i++) { q=(wz[i]-1)%m+1;w=(wz[i]-1)/m+1; if (q>=le[w]&&q<=ri[w]) { if (--e) printf("%d ",i);else {printf("%d\n",i);break;} Sign(w,q); } } return 0; }
BZOJ3240矩阵游戏:总记得之前分析过复杂度,总觉得是可以过的= =后来猜结论发现可以套费马小定理上去,然后就高精度都不用就水过了。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define M 1000000007 #define ll long long #define ld long double struct Point { ll a1,a2; }; Point Read() { ll x=0,z=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=(x*10+y-'0')%(M-1),z=(z*10+y-'0')%M, y=getchar(); while (y>='0'&&y<='9'); return (Point){x,z}; } inline ll Quick_Multi(ll x,ll y) { ll i=x*y-(ll)((ld)x/M*y+1e-9)*M; return i<0?i+M:i; } inline Point Multi(Point x,Point y) { return (Point){Quick_Multi(x.a1,y.a1), (Quick_Multi(x.a2,y.a1)+y.a2)%M}; } Point Quick_Mi(Point x,ll y) { Point z;z.a1=1;z.a2=0; while (y) { if (y&1) z=Multi(z,x); x=Multi(x,x); y >>= 1; } return z; } int main() { int i,j;Point k,l,q,w,e,n,m; n=Read();m=Read();k.a1=(e=Read(),e.a1);k.a2=(e=Read(),e.a1); l.a1=(e=Read(),e.a1);l.a2=(e=Read(),e.a1); q=k.a1!=1?Quick_Mi(k,(m.a1+M-2)%(M-1)): (Point){1,((m.a2-1)*k.a2)%M}; w=Multi(q,l); w=w.a1!=1?Quick_Mi(w,(n.a1+M-2)%(M-1)): (Point){1,((n.a2-1)*w.a2)%M}; w=Multi(w,q); cout <<(w.a1+w.a2)%M<<endl; return 0; }
BZOJ2875随机数生成器:裸矩乘
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define ll long long struct Point { ll a1,a2; }; ll n,m,s; inline ll Multi(ll x,ll y) { ll z=0; while (y) { if (y&1) z=(z+x)%m; x=(x+x)%m; y >>= 1; } return z; } inline Point Mult(Point x,Point y) { return (Point){Multi(x.a1,y.a1),(Multi(x.a2,y.a1)+y.a2)%m}; } inline Point Quick_mi(Point x,ll y) { Point z;z.a1=1;z.a2=0; while (y) { if (y&1) z=Mult(z,x); x=Mult(x,x); y >>= 1; } return z; } int main() { int i,j;ll k,l;Point q,w,e; cin >>m>>q.a1>>q.a2>>k>>n>>s; q=Quick_mi(q,n); k=((Multi(q.a1,k)+q.a2)%m)%s; cout <<k<<endl; }
BZOJ2878迷失游乐园:如果是树就是树形DP,否则环上情况特殊考虑,由于环很小甚至环上可以有k^2级别的处理。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 100050 #define ld long double double h[N],s[N],ans,v[N]; int fi[N],c[N*2][3],ss=1,n,m,cl[N],d[N],le,ri,li[N]; bool b[N],f[N]; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline void Line(int x,int y,int z) { c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss; d[x]++;d[y]++; return; } double DF1(int x,int y) { int l=0; for (int i=fi[x];i;i=c[i][1]) if (c[i][0]!=y&&!b[c[i][0]]) h[x]+=c[i][2]+DF1(c[i][0],x),l++; return l?(h[x]/=l):0; } void DS1(int x,int y,int z) { int i;double j=h[x]; h[x]=0; for (i=fi[x];i;i=c[i][1]) if (c[i][0]!=y) h[x]+=h[c[i][0]]+c[i][2]; if (y) h[x]+=z+(d[y]>1?(h[y]-j-z)/(d[y]-1):0); ans+=h[x]/d[x]; for (i=fi[x];i;i=c[i][1]) if (c[i][0]!=y) DS1(c[i][0],x,c[i][2]); return; } void So1() { DF1(n,0); DS1(n,0,0); printf("%.8lf\n",ans/n); return; } bool Find(int x,int y,int z) { b[li[y]=x]=1; for (int i=fi[x];i;i=c[i][1]) if (b[c[i][0]]&&(i^1)!=z) { le=c[i][0];li[ri=y]=i;return 1; }else if (!b[c[i][0]]&&(li[y]=i,Find(c[i][0],y+1,i))) return 1; return 0; } double DF2(int x) { int i,j,k,l=0;double q,w,e=0; f[x]=1; for (i=fi[x];i;i=c[i][1]) if (b[c[i][0]]&&!f[c[i][0]]) e+=c[i][2]+DF2(c[i][0]),l++;else if (!b[c[i][0]]) e+=h[c[i][0]]+c[i][2],l++; if (!l) l=1; f[x]=0;v[x]=e; return e/l; } void So2() { int i,j,k,l,q,w,e; Find(1,1,0); for (i=ri;i&&c[li[i-1]][0]!=le;i--); if (!i) i++; memset(b,0,sizeof(b)); for (j=i;j<=ri;j++) b[li[j-i+1]=c[li[j]][0]]=1; for (j=1,ri=ri-i+1;j<=ri;j++) DF1(li[j],0); for (i=1;i<=ri;i++) h[li[i]]=DF2(li[i]),ans+=h[li[i]],h[li[i]]=v[li[i]]; for (i=1;i<=ri;i++) for (j=fi[li[i]];j;j=c[j][1]) if (!b[c[j][0]]) DS1(c[j][0],li[i],c[j][2]); printf("%.8lf\n",ans/n); return; } int main() { int i,j,k,l,q,w,e; scanf("%d%d",&n,&m);ans=0; for (i=1;i<=m;i++) q=Read(),w=Read(),e=Read(),Line(q,w,e); if (m<n) So1();else So2(); return 0; }
BZOJ2877魔幻棋盘:
没看出来,感觉二维差分是很神啊,具体题解移步这里,然后就是写一个二维线段树了= =
然而中间有一个地方写挂了一直没调出来wa了几次真是羞耻= =不过感觉还是很容易写挂啊
而且40+个if真是sxbk。也不知道网上有的人写400+是怎么做到的(以前我好像写裸的splay也写过400+现在感觉真是厉害)
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 500050 #define ll long long ll t,n,m,X,Y,st=0,ss=0,d[N*5],s=0,INF=100000000151234567; struct Seg_Tree { ll v;Seg_Tree* c[2]; } b[N*10]; struct Ment_Tree { Seg_Tree* t;Ment_Tree* c[2]; } a[N*4]; inline ll Read() { ll x=0;char y;bool z=0; do y=getchar(),z|=y=='-'; while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return z?-x:x; } inline ll gcd(ll x,ll y) {return !y?x:gcd(y,x%y);} inline ll Num(int x,int y) {return d[(x-1)*m+y];} inline ll Abs(ll x) {return x<0?-x:x;} inline ll Calc(int x,int y) { if (x<X&&y<Y) return Num(x,y)-Num(x+1,y)-Num(x,y+1)+Num(x+1,y+1); if (x>X&&y<Y) return Num(x,y)-Num(x-1,y)-Num(x,y+1)+Num(x-1,y+1); if (x<X&&y>Y) return Num(x,y)-Num(x+1,y)-Num(x,y-1)+Num(x+1,y-1); if (x>X&&y>Y) return Num(x,y)-Num(x-1,y)-Num(x,y-1)+Num(x-1,y-1); if (x==X&&y==Y) return Num(x,y); if (x==X&&y<Y) return Num(x,y)-Num(x,y+1); if (x==X&&y>Y) return Num(x,y)-Num(x,y-1); if (x<X&&y==Y) return Num(x,y)-Num(x+1,y); return Num(x,y)-Num(x-1,y); } Seg_Tree* DSF(int x,int y,int z) { int i=(x+y)/2,j=++st; if (x==y) b[j].v=Calc(z,x),b[j].c[0]=b[j].c[1]=NULL;else b[j].c[0]=DSF(x,i,z),b[j].c[1]=DSF(i+1,y,z), b[j].v=gcd(b[j].c[0]->v,b[j].c[1]->v); return &b[j]; } Seg_Tree* Merge(int x,int y,Seg_Tree* z,Seg_Tree* o) { int i=(x+y)/2,j=++st; b[j].v=gcd(z->v,o->v); if (x==y) b[j].c[0]=b[j].c[1]=NULL;else b[j].c[0]=Merge(x,i,z->c[0],o->c[0]), b[j].c[1]=Merge(i+1,y,z->c[1],o->c[1]); return &b[j]; } Ment_Tree* DFS(int x,int y) { int i=(x+y)/2,j=++ss; if (x==y) a[j].t=DSF(1,m,x);else a[j].c[0]=DFS(x,i),a[j].c[1]=DFS(i+1,y), a[j].t=Merge(1,m,a[j].c[1]->t,a[j].c[0]->t); return &a[j]; } ll QueSeg(int x,int y,Seg_Tree* z,int o,int p) { int i=(x+y)/2;ll j=-INF,k=-INF; if (x==o&&y==p) return z->v; if (o<=i) j=QueSeg(x,i,z->c[0],o,min(p,i)); if (p>i) k=QueSeg(i+1,y,z->c[1],max(o,i+1),p); if (j==-INF) return k;else return k==-INF?j:Abs(gcd(k,j)); } ll QueMent(int x,int y,Ment_Tree* z,int o,int p,int u,int v) { int i=(x+y)/2;ll j=-INF,k=-INF; if (x==o&&y==p) return QueSeg(1,m,z->t,u,v); if (o<=i) j=QueMent(x,i,z->c[0],o,min(p,i),u,v); if (p>i) k=QueMent(i+1,y,z->c[1],max(o,i+1),p,u,v); if (j==-INF) return k;else return k==-INF?j:Abs(gcd(k,j)); } void ModiSeg(int x,int y,Seg_Tree* z,int o,ll p) { int i=(x+y)/2; if (x==y) {z->v+=p;return;} if (o<=i) ModiSeg(x,i,z->c[0],o,p);else ModiSeg(i+1,y,z->c[1],o,p); z->v=gcd(z->c[0]->v,z->c[1]->v); return; } void Modify(int x,int y,Seg_Tree* z,Seg_Tree* o,Seg_Tree* p,ll u) { int i=(x+y)/2; z->v=gcd(o->v,p->v); if (x==y) return; if (u<=i) Modify(x,i,z->c[0],o->c[0],p->c[0],u);else Modify(i+1,y,z->c[1],o->c[1],p->c[1],u); return; } void ModiMent(int x,int y,Ment_Tree* z,int o,int p,ll u) { int i=(x+y)/2; if (x==y) {ModiSeg(1,m,z->t,p,u);return;} if (o<=i) ModiMent(x,i,z->c[0],o,p,u);else ModiMent(i+1,y,z->c[1],o,p,u); Modify(1,m,z->t,z->c[0]->t,z->c[1]->t,p); return; } void Revise() { ll i,j,k=Read(),q=Read(),l=Read(),w=Read(),e=Read(); if (k<=X&&l>=X&&q<=Y&&w>=Y) ModiMent(1,n,&a[1],X,Y,e); if (k<=X&&l>=X&&q<=Y&&q-1) ModiMent(1,n,&a[1],X,q-1,-e); if (k<=X&&l>=X&&w>=Y&&w!=m) ModiMent(1,n,&a[1],X,w+1,-e); if (k<=X&&l>=X&&q>Y) ModiMent(1,n,&a[1],X,q,e); if (k<=X&&l>=X&&w<Y) ModiMent(1,n,&a[1],X,w,e); if (q<=Y&&w>=Y&&k<=X&&k-1) ModiMent(1,n,&a[1],k-1,Y,-e); if (q<=Y&&w>=Y&&l>=X&&l!=n) ModiMent(1,n,&a[1],l+1,Y,-e); if (q<=Y&&w>=Y&&k>X) ModiMent(1,n,&a[1],k,Y,e); if (q<=Y&&w>=Y&&l<X) ModiMent(1,n,&a[1],l,Y,e); if (k<=X&&q<=Y&&k-1&&q-1) ModiMent(1,n,&a[1],k-1,q-1,e); if (k<=X&&q>Y&&k-1) ModiMent(1,n,&a[1],k-1,q,-e); if (k>X&&q<=Y&&q-1) ModiMent(1,n,&a[1],k,q-1,-e); if (k>X&&q>Y) ModiMent(1,n,&a[1],k,q,e); if (k<=X&&w>=Y&&k-1&&w!=m) ModiMent(1,n,&a[1],k-1,w+1,e); if (k<=X&&w<Y&&k-1) ModiMent(1,n,&a[1],k-1,w,-e); if (k>X&&w>=Y&&w!=m) ModiMent(1,n,&a[1],k,w+1,-e); if (k>X&&w<Y) ModiMent(1,n,&a[1],k,w,e); if (l>=X&&q<=Y&&l!=n&&q-1) ModiMent(1,n,&a[1],l+1,q-1,e); if (l>=X&&q>Y&&l!=n) ModiMent(1,n,&a[1],l+1,q,-e); if (l<X&&q<=Y&&q-1) ModiMent(1,n,&a[1],l,q-1,-e); if (l<X&&q>Y) ModiMent(1,n,&a[1],l,q,e); if (l>=X&&w>=Y&&l!=n&&w!=m) ModiMent(1,n,&a[1],l+1,w+1,e); if (l>=X&&w<Y&&l!=n) ModiMent(1,n,&a[1],l+1,w,-e); if (l<X&&w>=Y&&w!=m) ModiMent(1,n,&a[1],l,w+1,-e); if (l<X&&w<Y) ModiMent(1,n,&a[1],l,w,e); return; } int main() { ll i,j,k,l,q,w,e; n=Read();m=Read();X=Read();Y=Read();t=Read(); for (i=1;i<=n*m;i++) d[i]=Read(); DFS(1,n); for (i=1;i<=t;i++) if (!Read()) { k=Read(),l=Read(),q=Read(),w=Read(),s++, printf("%lld\n",QueMent(1,n,&a[1],X-k,X+q,Y-l,Y+w)); }else Revise(); return 0; }
BZOJ2435道路修建:
做法一眼,但是之前一直不知道递归层数5w+就会爆炸的【捂脸贼】,所以搞成DFS序再搞
#include <iostream> #include <cmath> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; #define N 1000050 #define ll long long ll ans=0; int c[N*2][3],b[N],fa[N],fi[N],s[N],a[N],n,m,ss=1; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline void Line(int x,int y,int z) { c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss; return; } void BFS() { int i,j,k,l,q,w,e,ri=1; b[1]=1;fa[1]=-1; for (i=1;i<=n;i++) { for (j=fi[b[i]];j;j=c[j][1]) if (!fa[c[j][0]]) fa[c[j][0]]=b[i],b[++ri]=c[j][0], a[c[j][0]]=c[j][2]; s[i]=1; } for (i=n;i>=1;i--) for (j=fi[b[i]];j;j=c[j][1]) if (c[j][0]!=fa[b[i]]) s[b[i]]+=s[c[j][0]]; for (i=2;i<=n;i++) ans+=(ll)(a[i])*abs(n-s[i]*2); return; } int main() { int i,j,k,l,q,w,e; n=Read(); for (i=1;i<n;i++) q=Read(),w=Read(),e=Read(),Line(q,w,e); BFS(); cout <<ans<<endl; return 0; }
BZOJ2434阿狸的打字机:
首先AC自动机是肯定的,但是爆力kmp会挂。所以考虑优化,首先询问可以变成y串上面有多少个i使得yi可以通过fail指针转移到x串的末尾,所以考虑建fail树,然后维护关于DFS序的线段树,初始权值全部为0,在AC自动机上DFS,每经过一个点就使其权值加1,遇到询问就查询x串末尾所对应的子树和,离开时也要权值-1。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> using namespace std; #define N 100050 #define ll long long int n,m,ss=0,qu[N][3],fi[N],li[N],s=0,sg[N][2];char d[N]; int fr[N],nr[N]; queue <int> list; struct Trie { int fa[N],ne[N],fi[N],v[N]; } a; struct Fail { int fa[N],ne[N],fi[N]; } b; struct Segment_Tree { int c[N*3][2],s[N]; } c; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } /* void DFF(int x) { cout <<x<<' '<<b.fa[x]<<' '<<b.ne[x]<<' '<<b.fi[x]<<endl; if (b.fi[x]) DFF(b.fi[x]); if (b.ne[x]) DFF(b.ne[x]); return; }*/ inline void Get(int x,int y) { b.fa[x]=y;b.ne[x]=b.fi[y];b.fi[y]=x;return; } void Set_Up() { int i,j,k,l,q,w,e; list.push(0); while (!list.empty()) { k=list.front();list.pop(); for (i=a.fi[k];i;i=a.ne[i]) { list.push(i);q=b.fa[k]; while (q) { for (j=a.fi[q];j;j=a.ne[j]) if (a.v[j]==a.v[i]) {Get(i,j);break;} if (b.fa[i]) break; q=b.fa[q]; } if (!q&&!b.fa[i]) { for (j=a.fi[0];j;j=a.ne[j]) if (a.v[j]==a.v[i]&&i!=j) {Get(i,j);break;} if (!b.fa[i]) Get(i,0); } } } return; } void Set_up() { int i,j,k,l,q,w,e=0; for (i=0;i<n;i++) if (d[i]=='B') e=a.fa[e];else if (d[i]=='P') li[++s]=e,nr[s]=fr[e],fr[e]=s;else { k=0; for (j=a.fi[e];j;j=a.ne[j]) if (a.v[j]==d[i]) {k=e=j;break;} if (k==0) { a.v[++ss]=d[i];a.fa[ss]=e; a.ne[ss]=a.fi[e];a.fi[e]=ss;e=ss; } } ss=0; Set_Up(); return; } void Sign(int x) { sg[x][0]=++ss; for (int i=b.fi[x];i;i=b.ne[i]) Sign(i); sg[x][1]=ss; return; } void Insert(int x,int y,int z,int o,int p) { int i=(x+y)/2,j=z*2; c.s[z]+=p; if (x==y) return; if (o>i) Insert(i+1,y,j+1,o,p);else Insert(x,i,j,o,p); return; } int Query(int x,int y,int z,int o,int p) { int i=(x+y)/2,j=z*2,k=0; if (x==o&&y==p) return c.s[z]; if (o<=i) k=Query(x,i,j,o,min(i,p)); if (p>i) k+=Query(i+1,y,j+1,max(o,i+1),p); return k; } void DFS(int x) { Insert(1,ss,1,sg[x][0],1); for (int i=fr[x];i;i=nr[i]) for (int j=fi[i];j;j=qu[j][1]) qu[j][2]=Query(1,ss,1,sg[li[qu[j][0]]][0],sg[li[qu[j][0]]][1]); for (int i=a.fi[x];i;i=a.ne[i]) DFS(i); Insert(1,ss,1,sg[x][0],-1); return; } int main() { scanf("%s",d);n=strlen(d); Set_up();Sign(0);m=Read(); for (int i=1,k;i<=m;i++) qu[i][0]=Read(),qu[i][1]=fi[k=Read()],fi[k]=i; DFS(0); for (int i=1;i<=m;i++) printf("%d\n",qu[i][2]); return 0; }
BZOJ2007海拔:
可以自行YY到一个性质:这些数要不就是0要不就是1(话说题目下面那个提示:海拔也有可能是小数也是sxbk),因为最优方案中最大的数如果调整到旁边的数的大小是可以使答案更优的,最小的也是这样。所以最优方案中最大的数一定是1、最小的一定是0,同理通过调整不存在小数,而且不存在不包含左上角的0连通块和不包含右下角的1连通块,因为这些连通块全部取反之后是会更优的。所以最后就变成了求一个最小割了,由于是平面图,而且点数艹蛋,所以转成对偶图用最短路问题做。
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> using namespace std; #define N 550 #define M 1500000 #define INF 0x7f7f7f7f int h[M],fi[M],c[M][3],n,m,S=M-1,T=M-2,sg[N][N],ss=1,st=0; int a[N][N][4]; bool b[M]; queue <int> li; inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } inline void Line(int x,int y,int z,int o) { c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss; c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=o;fi[y]=ss; return; } void Set_up() { int i,j,k,l,q,w,e; for (i=1;i<=n;i++) sg[0][i]=sg[i][n+1]=S,sg[n+1][i]=sg[i][0]=T; for (i=1;i<=n;i++) for (j=1;j<=n;j++) sg[i][j]=++st; for (i=0;i<=n;i++) for (j=1;j<=n;j++) a[i][j][3]=Read(); for (i=1;i<=n;i++) for (j=0;j<=n;j++) a[i][j+1][4]=Read(); for (i=0;i<=n;i++) for (j=1;j<=n;j++) a[i+1][j][1]=Read(); for (i=1;i<=n;i++) for (j=0;j<=n;j++) a[i][j][2]=Read(); for (int i=1;i<=n;i++) for (int j=0;j<=n;j++) Line(sg[i][j],sg[i][j+1],a[i][j][2],a[i][j+1][4]); for (int i=0;i<=n;i++) for (int j=1;j<=n;j++) Line(sg[i][j],sg[i+1][j],a[i][j][3],a[i+1][j][1]); return; } void SPFA() { int i,j,k,l,q,w,e; li.push(S);b[S]=1;h[T]=INF;h[S]=0; for (i=1;i<=st;i++) h[i]=INF; while (!li.empty()) { q=li.front();li.pop();b[q]=0; for (i=fi[q];i;i=c[i][1]) if (h[q]+c[i][2]<h[c[i][0]]) { h[c[i][0]]=h[q]+c[i][2]; if (!b[c[i][0]]) li.push(c[i][0]),b[c[i][0]]=1; } } return; } int main() { int i,j,k,l,q,w,e; n=Read();Set_up(); SPFA(); printf("%d\n",h[T]); return 0; }