Lvat_s Blog

简单的单调栈

#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,否则一定会在这个子树的内部再分块）

最后剩下的点在下面找一个子树丢进去就行了,必定满足条件

#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模版略微改动一下

#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

#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

#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

真是日了狗了

#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次

#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乱搞

题解

#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;
}

旋转卡壳模版题

首先搞出凸包，然后在凸包上面扫描，用两个指针维护单调性

#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