简单的单调栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;int n,Stack[250005],Top,ans;int main(){freopen("1113.in","r",stdin);freopen("1113.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){ int x,y; scanf("%d %d",&x,&y); while(Top && Stack[Top]>=y){if(Stack[Top]!=y)ans++;Top--;} Stack[++Top]=y;}printf("%d\n",ans+Top);return 0;} |
树上分块
对于每个子树维护siz
大于B就把这个子树和当前的省作为一块丢掉（这一块一定小于2*B,否则一定会在这个子树的内部再分块）
最后剩下的点在下面找一个子树丢进去就行了,必定满足条件
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 | #include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;const int N=2005;int n,B,en,h[N],St[N],belong[N],St_size,siz[N],home[N],hcnt;struct Edge{int b,next;}e[N];void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}void DFS(int u,int fa){St[++St_size]=u;for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(v==fa)continue; DFS(v,u); if(siz[u]+siz[v]>=B){ siz[u]=0; home[++hcnt]=u; while(St[St_size]!=u)belong[St[St_size--]]=hcnt; } else siz[u]+=siz[v];}siz[u]++;}void Paint(int u,int fa,int col){if(!belong[u])belong[u]=col;else col=belong[u];for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(v!=fa)Paint(v,u,col);}}int main(){freopen("1086.in","r",stdin);freopen("1086.out","w",stdout);scanf("%d %d",&n,&B);if(n<B){puts("0");return 0;}for(int i=1;i<n;i++){ int u,v; scanf("%d %d",&u,&v); AddEdge(u,v); AddEdge(v,u);}DFS(1,0);if(!hcnt)home[++hcnt]=1;Paint(1,0,hcnt);printf("%d\n",hcnt);for(int i=1;i<=n;i++)printf("%d ",belong[i]);putchar('\n');for(int i=1;i<=hcnt;i++)printf("%d ",home[i]);putchar('\n');return 0;} |
把FFT模版略微改动一下
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 | #include<cstdio>#include<algorithm>#include<cstring>#include<cstdlib>#include<cmath>using namespace std; const int N=270000;const double Pi=acos(-1); int An,Bn,Cn,n,Rev[N],Step; struct Complex{double a,b;Complex(){}Complex(double sa,double sb){a=sa;b=sb;}friend Complex operator+(Complex A,Complex B){return Complex(A.a+B.a,A.b+B.b);}friend Complex operator-(Complex A,Complex B){return Complex(A.a-B.a,A.b-B.b);}friend Complex operator*(Complex A,Complex B){return Complex(A.a*B.a-A.b*B.b,A.a*B.b+A.b*B.a);}}A[N],B[N],C[N]; void FFT(Complex *x,int flag){for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);for(int k=1;k<n;k<<=1){ Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k)); for(int i=0;i<n;i+=k<<1){ Complex wkj=Complex(1.0,0.0); for(int j=0;j<k;j++){ Complex a=x[i+j],b=x[i+j+k]*wkj; x[i+j]=a+b; x[i+j+k]=a-b; wkj=wkj*wk; } }}if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;} int main(){freopen("2194.in","r",stdin);freopen("2194.out","w",stdout);scanf("%d",&An);Bn=An;Cn=An+Bn-1;for(int i=0;i<An;i++)scanf("%lf %lf",&A[i].a,&B[An-i].a);for(n=1,Step=0;n<Cn;n<<=1,Step++);for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));FFT(A,1);FFT(B,1);for(int i=0;i<n;i++)C[i]=A[i]*B[i];FFT(C,-1);for(int i=Cn/2+1;i<=Cn;i++)printf("%d\n",(int)(C[i].a+0.5));return 0;} |
LCT
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | #include<cstdio>#include<algorithm>using namespace std;int n,m;struct Node{int rev;Node *ch[2],*fa;Node(Node *fat);void Pushdown();}*root[10005],*Null;Node::Node(Node *fat){fa=fat;ch[0]=ch[1]=Null;rev=0;}void Node::Pushdown(){if(rev){ if(ch[0]!=Null)ch[0]->rev^=1; if(ch[1]!=Null)ch[1]->rev^=1; swap(ch[0],ch[1]); rev=0;}}int Notroot(Node *x){return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);}void Prepare(Node *x){if(Notroot(x))Prepare(x->fa);x->Pushdown();}void Rotate(Node *x,int kind){Node *y=x->fa,*z=y->fa;y->ch[!kind]=x->ch[kind];if(x->ch[kind]!=Null)x->ch[kind]->fa=y;x->fa=z;if(Notroot(y))z->ch[z->ch[1]==y]=x;y->fa=x;x->ch[kind]=y;}void Splay(Node *x){Prepare(x);while(Notroot(x)){ Node *y=x->fa,*z=y->fa; if(!Notroot(y))Rotate(x,y->ch[0]==x); else { if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);} else if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);} else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);} else {Rotate(x,0);Rotate(x,1);} }}}void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}}void Makeroot(Node *x){Access(x);Splay(x);x->rev^=1;}void Link(Node *u,Node *v){Makeroot(u);u->fa=v;}void Cut(Node *u,Node *v){Makeroot(u);Access(v);Splay(v);if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}}Node *Find(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}Node *GetNull(){Node *p=new Node(Null);p->ch[0]=p->ch[1]=p->fa=p;p->rev=0;return p;}Node *ToLct(int x){return root[x];}int main(){freopen("2049.in","r",stdin);freopen("2049.out","w",stdout);scanf("%d %d",&n,&m);Null=GetNull();for(int i=1;i<=n;i++)root[i]=new Node(Null);for(int i=1;i<=m;i++){ int u,v; char s[10]; scanf("%s %d %d",s,&u,&v); if(s[0]=='C')Link(ToLct(u),ToLct(v)); if(s[0]=='D')Cut(ToLct(u),ToLct(v)); if(s[0]=='Q'){ if(Find(ToLct(u))==Find(ToLct(v)))puts("Yes"); else puts("No"); }}return 0;} |
水题可以愉悦身心
分层图SPFA
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 | #include<cstdio>#include<cstdlib>#include<cstring>#include<queue>#include<algorithm>using namespace std;int n,m,k,en,h[55],D[55][55],flag[55][55],ans;struct Que{int a,b;Que(int sa,int sb){a=sa;b=sb;}};queue<Que> Q;struct Edge{int b,v,next;}e[2005];void AddEdge(int sa,int sb,int sc){e[++en].b=sb;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}void SPFA(){memset(D,127,sizeof(D));flag[0][1]=1;D[0][1]=0;Q.push(Que(0,1));while(!Q.empty()){ Que u=Q.front(); Q.pop(); flag[u.a][u.b]=0; for(int i=h[u.b];i;i=e[i].next){ int v=e[i].b; if(D[u.a][v]>D[u.a][u.b]+e[i].v){ D[u.a][v]=D[u.a][u.b]+e[i].v; if(!flag[u.a][v]){ flag[u.a][v]=1; Q.push(Que(u.a,v)); } } } if(u.a<k){ for(int i=h[u.b];i;i=e[i].next){ int v=e[i].b; if(D[u.a+1][v]>D[u.a][u.b]+e[i].v/2){ D[u.a+1][v]=D[u.a][u.b]+e[i].v/2; if(!flag[u.a+1][v]){ flag[u.a+1][v]=1; Q.push(Que(u.a+1,v)); } } } }}ans=D[0][n];for(int i=1;i<=k;i++)ans=min(ans,D[i][n]);}int main(){freopen("2662.in","r",stdin);freopen("2662.out","w",stdout);scanf("%d %d %d",&n,&m,&k);for(int i=1;i<=m;i++){ int u,v,w; scanf("%d %d %d",&u,&v,&w); AddEdge(u,v,w); AddEdge(v,u,w);}SPFA();printf("%d\n",ans);return 0;} |
行尾有空格会PE
真是日了狗了
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 | #include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;int n,T;struct Data{int id,x;friend bool operator<(Data A,Data B){return A.id<B.id;}}a[50005];bool cmp(Data A,Data B){return A.x<B.x || (A.x==B.x && A.id<B.id);}int main(){freopen("2761.in","r",stdin);freopen("2761.out","w",stdout);scanf("%d",&T);while(T--){ scanf("%d",&n); a[n+1].id=99999; for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i; sort(a+1,a+n+1,cmp); for(int i=2;i<=n;i++)if(a[i].x==a[i-1].x)a[i].id=99999; sort(a+1,a+n+1); for(int i=1;i<=n;i++){if(a[i+1].id==99999){printf("%d\n",a[i].x);break;}else printf("%d ",a[i].x);}}return 0;} |
分层图SPFA
最后必须依次比较，因为可能因为边数太少用不到k次
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 | #include<cstdio>#include<cstdlib>#include<cstring>#include<queue>#include<algorithm>using namespace std;int n,m,k,S,T,en,h[10005],D[15][10005],flag[15][10005],ans;struct Que{int a,b;Que(int sa,int sb){a=sa;b=sb;}};queue<Que> Q;struct Edge{int b,v,next;}e[100005];void AddEdge(int sa,int sb,int sc){e[++en].b=sb;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}void SPFA(){memset(D,127,sizeof(D));D[0][S]=0;flag[0][S]=1;Q.push(Que(0,S));while(!Q.empty()){ Que u=Q.front(); Q.pop(); flag[u.a][u.b]=0; for(int i=h[u.b];i;i=e[i].next){ int v=e[i].b; if(D[u.a][v]>D[u.a][u.b]+e[i].v){ D[u.a][v]=D[u.a][u.b]+e[i].v; if(!flag[u.a][v]){ flag[u.a][v]=1; Q.push(Que(u.a,v)); } } } if(u.a<k){ for(int i=h[u.b];i;i=e[i].next){ int v=e[i].b; if(D[u.a+1][v]>D[u.a][u.b]){ D[u.a+1][v]=D[u.a][u.b]; if(!flag[u.a+1][v]){ flag[u.a+1][v]=1; Q.push(Que(u.a+1,v)); } } } }}ans=D[0][T];for(int i=1;i<=k;i++){ans=min(ans,D[i][T]);}}int main(){freopen("2763.in","r",stdin);freopen("2763.out","w",stdout);scanf("%d %d %d %d %d",&n,&m,&k,&S,&T);for(int i=1;i<=m;i++){ int u,v,w; scanf("%d %d %d",&u,&v,&w); AddEdge(u,v,w); AddEdge(v,u,w);}SPFA();printf("%d\n",ans);return 0;} |
的确是好题。。。
根本不会，然后copy了PoPoQQQ大爷的代码
反正就是LCT乱搞
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | #include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int Mod=10007,N=30005;int n,m,vis[N],cnt,fa[N];struct Line{int k,b;Line(){}Line(int ks,int bs){k=ks;b=bs;}friend Line operator+(Line A,Line B){return Line(A.k*B.k%Mod,(B.k*A.b+B.b)%Mod);}int F(int x){return (k*x+b)%Mod;}};struct Node{Line v,sum;Node *ch[2],*fa,*spc;Node(int k,int b);void Pushup();}*root[N],*Null;Node::Node(int k,int b){ch[0]=ch[1]=fa=spc=Null;v=sum=Line(k,b);}void Node::Pushup(){sum=ch[0]->sum+v+ch[1]->sum;}bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}Node *GetNull(){Node *p=new Node(1,0);p->ch[0]=p->ch[1]=p->fa=p;return p;}void Rotate(Node *x,int kind){Node *y=x->fa,*z=y->fa;y->ch[!kind]=x->ch[kind];if(x->ch[kind]!=Null)x->ch[kind]->fa=y;x->fa=z;if(Notroot(y))z->ch[z->ch[1]==y]=x;y->fa=x;x->ch[kind]=y;y->Pushup();x->Pushup();}void Splay(Node *x){while(Notroot(x)){ Node *y=x->fa,*z=y->fa; if(!Notroot(y))Rotate(x,y->ch[0]==x); else { if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);} else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);} else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);} else {Rotate(y,0);Rotate(x,0);} }}}void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}Node *Findroot(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}pair<int,int>exgcd(int a,int b){if(!b)return make_pair(1,0);pair<int,int>P=exgcd(b,a%b);return make_pair(P.second,P.first-a/b*P.second);}int Inv(int x){int P=exgcd((x+Mod)%Mod,Mod).first;return (P%Mod+Mod)%Mod;}void DFS(int u){vis[u]=cnt;if(vis[fa[u]]==cnt){root[u]->spc=root[fa[u]];return;}root[u]->fa=root[fa[u]];if(!vis[fa[u]])DFS(fa[u]);}int Query(Node *x){Node *rt=Findroot(x);Access(rt->spc);Splay(rt->spc);int k=rt->spc->sum.k,b=rt->spc->sum.b;if(k==1 && !(b==0 && x->sum.k==0))return b?-1:-2;Access(x);Splay(x);return x->sum.F((Mod-b)*Inv(k-1)%Mod);}void Modify(Node *x,int k,Node *f,int b){Node *rt=Findroot(x);x->v.k=k;x->v.b=b;x->Pushup();if(x==rt)x->spc=Null;else { Access(x); Splay(x); x->ch[0]->fa=Null; x->ch[0]=Null; x->Pushup(); if(Findroot(rt->spc)!=rt){ Access(rt); Splay(rt); rt->fa=rt->spc; rt->spc=Null; }}Access(x);Splay(x);if(Findroot(f)==x){x->spc=f;}else x->fa=f;}int main(){freopen("2759.in","r",stdin);freopen("2759.out","w",stdout);scanf("%d",&n);Null=GetNull();for(int i=1;i<=n;i++){ int k,f,b; scanf("%d %d %d",&k,&f,&b); fa[i]=f; root[i]=new Node(k,b);}for(int i=1;i<=n;i++){if(!vis[i]){cnt++;DFS(i);}}scanf("%d",&m);for(int i=1;i<=m;i++){ char s[10]; int x,k,p,b; scanf("%s",s); if(s[0]=='A'){scanf("%d",&x);printf("%d\n",Query(root[x]));} if(s[0]=='C'){scanf("%d %d %d %d",&x,&k,&p,&b);Modify(root[x],k,root[p],b);}}return 0;} |
旋转卡壳模版题
首先搞出凸包，然后在凸包上面扫描，用两个指针维护单调性
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 | #include<cstdio>#include<cstdlib>#include<cstring>#include<cstring>#include<algorithm>using namespace std;int n,St_size,St[2005];double ans;struct Point{double x,y;Point(){}Point(int sa,int sb){x=sa;y=sb;}friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}friend double operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}friend bool operator<(Point A,Point B){return A.y<B.y || A.y==B.y && A.x<B.x;}}poi[2005];double Abs(double x){return x>0?x:-x;}double Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}bool cmp(Point A,Point B){int Mul=(int)((A-poi[1])*(B-poi[1]));return (Mul>0)||(Mul==0 && Dist(A,poi[1])<Dist(B,poi[1]));}void Graham(){if(n==1){St[1]=1;St_size=1;return;}St[1]=1;St[2]=2;St_size=2;for(int i=3;i<=n;i++){ while(St_size>1 && (poi[St[St_size]]-poi[St[St_size-1]])*(poi[i]-poi[St[St_size-1]])<=0)St_size--; St[++St_size]=i;}}void Prepare(){int pos=1;for(int i=2;i<=n;i++)if(poi[i]<poi[pos])pos=i;swap(poi[pos],poi[1]);sort(poi+2,poi+n+1,cmp);}void RC(){St[St_size+1]=1;for(int i=1;i<=St_size;i++){ int poix=i%St_size+1,poiy=(i+2)%St_size+1; for(int j=i+2;j<=St_size;j++){ while(poix%St_size+1!=j && Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix+1]]-poi[St[i]]))>Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]])))poix=poix%St_size+1; while(poiy%St_size+1!=i && Abs((poi[St[poiy+1]]-poi[St[i]])*(poi[St[j]]-poi[St[i]]))>Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])))poiy=poiy%St_size+1; ans=max(ans,Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]]))+Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]]))); }}}int main(){freopen("1069.in","r",stdin);freopen("1069.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf %lf",&poi[i].x,&poi[i].y);}Prepare();Graham();RC();printf("%.3lf\n",ans/2);return 0;} |
AHOI2016挂的很惨。。。
lyz lyf都开始停课搞OI了，马上就要拿到Au走上人生巅峰了
我因为没进省队回家种仙人掌去了很悲伤
所以，我在此立下FLAG:
我不停课，但我的OI也不会停的！
同时预祝两位大爷今年NOI能拿到Au为学校争光~
AHOI2017,我会翻盘的！
UPD2016.08.17
lyz确实拿到Au了……lyf是Cu
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com
