发布于

lp1110 ZJOI2007 报表统计

事实上对于第一类询问和第二类询问我们可以分别处理。
第二类询问的处理方法是非常显然的。由于只有插入而没有删除操作，因此，第二类询问的答案只会缩小、不会增大。
故而，我们对整个数列的值维护一个Splay，每一次插入一个新的数以后，用它和它的前驱与它和它的后继的差的绝对值来更新第二类的答案。
这可以用multiset来简易地实现。
对于第一类询问，我们发现，维护这个值其实并不是难点——用线段树或者平衡树都可以轻松实现。问题在于，如何在插入新的数之后保持这个值。
我们仔细思考，发现，对于任意一段区间来说，它对答案的贡献只有三个：这个区间的答案，这个区间的左端点和这个区间的右端点。
故而，我们建一棵线段树或者平衡树，维护这三个信息（个人认为线段树比较科学。）每一次修改则修改对应的节点，然后递归向上更新即可。
这样就做完了，个人觉得实现难度还是比较低的。

#include<iostream>
#include<cstdio>
#include<set>
#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
inline int Abs(int X){
	return X>0?X:-X;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

std::multiset<int> st;
int ansS=0x3f3f3f3f;
int n,m,a[500005];

class SegmentTree{
	private:
		class Node{
			public:
				int l;
				int r;
				int dlt;
			inline Node(){
				dlt=0x3f3f3f3f;
			}
			inline void init(int V){
				l=r=V;
			}
			inline void psh(int V){
				dlt=Min(dlt,Abs(r-V));
				r=V;
			}
		};
		Node tr[1100000];
		inline void updt(int X){
			tr[X].l=tr[LS].l;
			tr[X].r=tr[RS].r;
			tr[X].dlt=Min(Min(tr[LS].dlt,tr[RS].dlt),Abs(tr[LS].r-tr[RS].l));
		}
		inline void build(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].init(a[L]);
				return;
			}
			build(L,MID,LS),build(MID+1,R,RS);
			updt(X);
		}
		inline void push(int L,int R,int X,int A,int V){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].psh(V);
				return;
			}
			A>MID?push(MID+1,R,RS,A,V):push(L,MID,LS,A,V);
			updt(X);
		}
		inline void prnt(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				printf("%d:[%d,%d,%d] ",X,tr[X].l,tr[X].r,tr[X].dlt);
				return;
			}
			prnt(L,MID,LS),prnt(MID+1,R,RS);
		}
	public:
		inline void PUSH(int X,int K){
			push(1,n,1,X,K);
		}
		inline void BUILD(){
			build(1,n,1);
		}
		inline int QUERYG(){
			return tr[1].dlt;
		}
		inline void PRINT(){
			prnt(1,n,1);
			puts("");
		}
};

inline void STPUSH(int K){
	st.insert(K);
	std::multiset<int> ::iterator it=st.find(K);
	int ans1,ans2;
	++it;
	if(it!=st.end()){
		ans1=*it;
	}else{
		ans1=0x3f3f3f3f;
	}
	--it;
	if(it!=st.begin()){
		--it;
		ans2=*it;
	}else{
		ans2=0x3f3f3f3f;
	}
	ans1=Abs(K-ans1),ans2=Abs(K-ans2);
	ansS=Min(ansS,Min(ans1,ans2));
}

SegmentTree T;
void init(){
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		STPUSH(a[i]);
	}
	T.BUILD();
	char op[10];
	int k;
	for(int i=1;i<=m;++i){
		std::cin>>op;
		switch(op[4]){
			case 'R':{
				scanf("%d%d",&x,&k);
				T.PUSH(x,k);
				STPUSH(k);
				break;
			}
			case 'G':{
				printf("%d\n",T.QUERYG());
				break;
			}
			case 'S':{
				printf("%d\n",ansS);
				break;
			}
			case 'P':{
				T.PRINT();
				break;
			}
		}
	}
}

int main(){
	init();
	return 0;
}
发布于

lp2596 ZJOI2006 书架


看到这一题我们就可以想到Splay。
具体来说，这一题要求维护下列四个操作：
将序列中的一个数与它的前一个数/后一个数交换。
将序列中的一个数移到序列头/序列尾。
如果单单如此的话那这一题就太简单了。对于一二操作只需要直接和前驱、后继调换，对于三四操作只需要将左/右子树移动到右/左子树的最左/右节点的左/右孩子。
但事实上并非这样。这一题对序列中数的操作并非是直接给出的，而是对序列中的每一个点编了号，然后每一次访问这个编号。
但仔细思考就会发现，考虑到对序列的操作只会更换位置，
故而，对于这种操作，我们定义一个数组名为loc，储存的是，编号为\(loc_i\)的数在数列中的标号。
要十分注意编号和逆编号的对应关系。以及交换之后对它们原来的关系的影响。 

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int loc[80005],aloc[80005];
class Splay{
	private:
		class Node{
			public:
				int fa;
				int sn[2];
				int sz;
				inline void prnt(){
					printf("(%d,%d,%d)\n",fa,sn[0],sn[1]);
				}
			inline Node(int FA=0,int LS=0,int RS=0,int SZ=0){
				fa=FA,sn[0]=LS,sn[1]=RS,sz=SZ;
			}
		};
		Node tr[80005];
		int rt;
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
		}
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayTwo(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0; 
		}
		inline void splayRnw(int X){
			while(tr[X].fa){
				splayTwo(X);
			}
			rt=X;
		}
		inline int fnd(int K){
			int P=rt,FP=0;
			while(P){
				FP=P;
				if(tr[tr[P].sn[0]].sz+1<K){
					K-=(tr[tr[P].sn[0]].sz+1);
					P=tr[P].sn[1];
				}else if(tr[tr[P].sn[0]].sz<K){
					return P;
				}else{
					P=tr[P].sn[0];
				}
			}
			return FP;
		}
		inline int fndMn(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[0];
			}
			return FP;
		}
		inline int fndMx(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[1];
			}
			return FP;
		}
		inline int build(int L,int R,int FA){
			if(L>R){
				return 0;
			}
			tr[MID].fa=FA,tr[MID].sz=1;
			tr[MID].sn[0]=build(L,MID-1,MID);
			tr[MID].sn[1]=build(MID+1,R,MID);
			updt(MID);
			return MID;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].sn[0]);
			printf("%d ",X);
			prnt(tr[X].sn[1]);
		}
	public:
		inline void INIT(int N){
			build(1,N,0);
			rt=(1+N)>>1;
		}
		inline void SWAP(int X,int D){
			splayRnw(X);
			int P=D?fndMn(tr[X].sn[1]):fndMx(tr[X].sn[0]);
			int X_2=aloc[X],P_2=aloc[P];
			std::swap(loc[X_2],loc[P_2]);
			std::swap(aloc[X],aloc[P]);
			splayRnw(X);
		}
		inline void LST(int X){
			splayRnw(X);
			int P=fndMn(tr[X].sn[1]);
			tr[tr[X].sn[0]].fa=P,tr[P].sn[0]=tr[X].sn[0],tr[X].sn[0]=0;
			splayRnw(tr[P].sn[0]);
		}
		inline void RST(int X){
			splayRnw(X);
			int P=fndMx(tr[X].sn[0]);
			tr[tr[X].sn[1]].fa=P,tr[P].sn[1]=tr[X].sn[1],tr[X].sn[1]=0;
			splayRnw(tr[P].sn[1]);
		}
		inline int RNK(int X){
			splayRnw(X);
			return tr[tr[X].sn[0]].sz;
		}
		inline int ARNK(int X){
			int P=fnd(X);
			splayRnw(P);
			return P;
		}
		inline void PRINT(){
			printf("%d ->",rt);
			prnt(rt);
			puts("");
		}
};
int n,m;
Splay T;
void init(){
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int x,t;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		loc[x]=i,aloc[i]=x;
	}
	char op[10];
	for(int i=1;i<=m;++i){
		std::cin>>op;
		scanf("%d",&x);
		switch(op[0]){
			case 'T':{
				T.LST(loc[x]);
				break;
			}
			case 'B':{
				T.RST(loc[x]);
				break;
			}
			case 'I':{
				scanf("%d",&t);
				t==0?0:(T.SWAP(loc[x],t==-1?0:1),0);
				break;
			}
			case 'A':{
				printf("%d\n",T.RNK(loc[x]));
				break;
			}
			case 'Q':{
				printf("%d\n",aloc[T.ARNK(x)]);
				break;
			}
		}
	} 
}

int main(){
	init();
	return 0;
}
发布于

lp3386 二分图最大匹配

一道匈牙利算法的模板题。
对于一张二分图\(G\)（也就是没有奇环的图），我们定义它的「匹配」为一个图\(G'(V’,E’)\)，使得：
$$\forall V” \in V’,V”_{u}\in E’,V”_{v}\in E’,|E’|=2|V’|$$
我们称一个匹配是最大匹配，当且仅当它是一个边数最多的匹配。

匈牙利算法是用于求解最大匹配的一类问题。
匈牙利算法使用了一种被称为「增广」的操作。
我们首先定义一条增广路径指的是一张二分图上的路径，使得这条路径的起点和终点都是尚未匹配的点，并且它的路径上经过的所有点都是已经匹配过的点。
那么很容易可以发现，一条增广路径上的边必然是「一条已匹配一条未匹配」的。
于是，我们对增广路径上的所有边的匹配状态取反，就可以增加匹配数量的大小。
增广操作是指，对于一个点，尝试访问它的每一个相邻点，然后从这个相邻点找下去，直到能找到一条增广路径为止。然后将这条增广路径上所有边匹配状态取反。
故而，每一次新加入一个点，我们尝试一次增广。这样就能够找到最大匹配了。 

#include<iostream>
#include<cstdio>

int mp[1005][1005];
bool vis[1005];
int n,m,q,usd[1005];
inline bool dfs(int X){
	for(int i=1;i<=m;++i){
		if(!mp[X][i]){
			continue;
		}
		if(!vis[i]){
			vis[i]=1;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	
	return 0;
}
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i][j]=mp[j][i]=0;
			usd[i]=usd[j]=0;
		}
	}
	int u,v;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&u,&v);
		if(u>n||v>m){
			continue;
		}
		++mp[u][v];
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		ans+=dfs(i);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}
发布于

lp2042 NOI2005 维护数列

Splay裸题。
具体来说，维护两个延迟标记，翻转标记和改变标记。然后对于每一个标记考虑下传。
对于两种询问各自更新区间和与区间最大子段和。
一个区间的最大子段和有可能有三种情况：左子区间的最大子段和，右子区间的最大子段和，以及跨过两个区间的子段和。
故而我们对每个区间关于子段和维护三个信息，左起最大子段和、右起最大子段和以及总最大子段和。
而对于左起最大子段和的更新，则考虑两种情况：左子区间的最大子段和，以及整个左子区间加上根节点再加上右子区间的左起最大子段和。
右起同理。

注意：

  • 1.updt时应当先updt(tr[X].sn[D^1])再updt(X)
  • 2.添加节点和各种修改之后应当科学地rnw
  • 3.添加节点时应当注意是从posi~posi+1之间的区间。
  • 4.一个节点被删除以后，rnw它的父亲是没有意义的，应当从根开始rnw
  • 5.内存回收机制中，添加入栈应当是++tp,出栈应当是tp–
  • 6.考虑updt和pshd的方式：对于每一次pshd，我们应该统一修改它的子节点的标记，并对它的子节点计算贡献，然后取消它本身的标记；打标记的时候对它本身计算好贡献。
  • 换句话说，不要在统计一个节点的贡献之前，updt它的父亲。
  • 7.加入节点应当加入成一棵二叉树，而不是一条链。根据我根本不懂的势能分析法，加入一棵二叉树带来的势能改变是常数乘大小级的，而一条链则是对数乘大小级的。
  • 8.对于MAX-SUM操作，必须要至少选中一个节点，所以应当额外维护一个最大值。 
#include<iostream>
#include<cstdio>
#define R register
#define MAGIC 19260817
#define MID ((L+R_R)>>1)
/*

*/
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Chck(int X){
    return X>0?X:0;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
//表示特殊状态 
class Splay{
    private:
        class Node{
            public:
    			int fa;
    			int sn[2];
    			int sz;
    			int sm;
    			int lmxsm;
    			int rmxsm;
    			int mxsm;
    			int mx;
    			int v;
    			int lzy_flp;
    			int lzy_chng;
    			inline void set(int FA,int V){
    			    fa=FA,sz=1,sm=v=mxsm=mx=V,lmxsm=rmxsm=Chck(V);
    			    sn[0]=sn[1]=lzy_flp=0,lzy_chng=MAGIC;
                }
                inline void init(){
                    fa=sz=sm=lmxsm=rmxsm=v=sn[0]=sn[1]=lzy_flp=0;
                    mxsm=mx=-MAGIC;
                    lzy_chng=MAGIC;
                }
        };
        Node tr[500005];
        int st[500005],tp,cnt,rt;
        inline int fndD(int X){
            return tr[tr[X].fa].sn[0]==X?0:1;
        }
        inline void chng(int X){
            tr[X].sm=tr[X].lzy_chng*tr[X].sz,tr[X].mxsm=Max(tr[X].lzy_chng,tr[X].lzy_chng*tr[X].sz);tr[X].lmxsm=tr[X].rmxsm=Chck(tr[X].lzy_chng*tr[X].sz);
            tr[X].v=tr[X].mx=tr[X].lzy_chng;
        }
        inline void flp(int X){
            Swap(tr[X].sn[0],tr[X].sn[1]);
            Swap(tr[X].lmxsm,tr[X].rmxsm);
        }
        inline void pshd(int X){
            if(!X){
                return;
            }
            if(tr[X].lzy_chng!=MAGIC){
            	tr[tr[X].sn[0]].lzy_chng=tr[tr[X].sn[1]].lzy_chng=tr[X].lzy_chng;
                chng(tr[X].sn[0]),chng(tr[X].sn[1]);
                tr[X].lzy_chng=MAGIC;
            }
            if(tr[X].lzy_flp){
            	tr[tr[X].sn[0]].lzy_flp^=1,tr[tr[X].sn[1]].lzy_flp^=1;
                flp(tr[X].sn[0]),flp(tr[X].sn[1]);
                tr[X].lzy_flp=0;
            }
        }
        inline void updt(int X){
            if(!X){
                return;
            }
            tr[X].sm=tr[tr[X].sn[0]].sm+tr[tr[X].sn[1]].sm+tr[X].v;
            tr[X].mx=Max(Max(tr[tr[X].sn[0]].mx,tr[tr[X].sn[1]].mx),tr[X].v);
            tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
            tr[X].lmxsm=Max(tr[tr[X].sn[0]].sm+tr[X].v+tr[tr[X].sn[1]].lmxsm,tr[tr[X].sn[0]].lmxsm);
            tr[X].rmxsm=Max(tr[tr[X].sn[1]].sm+tr[X].v+tr[tr[X].sn[0]].rmxsm,tr[tr[X].sn[1]].rmxsm);
            tr[X].mxsm=Max(Max(tr[tr[X].sn[0]].mxsm,tr[tr[X].sn[1]].mxsm),tr[tr[X].sn[0]].rmxsm+tr[X].v+tr[tr[X].sn[1]].lmxsm);
        }
        inline void splayOne(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
            tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
            tr[tr[X].sn[D^1]].fa=X,tr[tr[X].fa].sn[D2]=X;
            updt(tr[X].sn[D^1]),updt(X);
        }
        inline void splayTwo(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
        }
        inline void splayRnw(int X){
            if(!X){
                return;
            }
            //printf("%d->",X);
            while(tr[X].fa){
                splayTwo(X);
                //printf("[%d,%d,%d[%d,%d](%d)] ",X,tr[X].fa,tr[tr[X].fa].fa,tr[X].sn[0],tr[X].sn[1],fndD(X));
            }
            //puts("");
            rt=X;
        }
        //注意，权值splay中的fnd函数实质上求的是排名为K的节点。 
        inline int fnd(int K){
            R int P=rt,FP=0;
            while(P){
                pshd(P);
                FP=P;
                if(tr[tr[P].sn[0]].sz+1<K){
                    K-=(tr[tr[P].sn[0]].sz+1);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<K){
                    return P;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return FP;
        }
        inline int nwlc(int FA,int D,int V){
            if(!cnt){
                rt=1;
            }
            int P=tp?st[tp--]:++cnt;
            tr[FA].sn[D]=P;
            tr[P].set(FA,V);
            return P;
        }
        inline int preSplay(int L,int LEN){
            int __L__=fnd(L),__R__=fnd(L+LEN+1);
            splayRnw(tr[__L__].fa),splayRnw(tr[__R__].fa);
            splayRnw(__L__);
            splayRnw(__R__);
            //printf("%d,%d,%d\n",rt,tr[rt].sn[0],tr[rt].sn[1]);
            if(tr[__L__].fa!=__R__&&__L__!=__R__){
                splayOne(__L__);
            }
            pshd(tr[tr[rt].sn[0]].sn[1]);
            return tr[rt].sn[0];
        }
        inline void rmv(int X){
            if(!X){
                return;
            }
            rmv(tr[X].sn[0]);
            rmv(tr[X].sn[1]);
            tr[tr[X].fa].sn[fndD(X)]=0;
            tr[tr[X].sn[0]].fa=tr[tr[X].sn[1]].fa=0;
            st[++tp]=X;
        }
        inline void prnt(int X, int dep=0){
            if(!X){
                return;
            }
            //pshd(X);
            prnt(tr[X].sn[0], dep+1);
            //printf("{%d}[%d](%d,%d)[%d][%d,%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].mxsm,tr[X].lmxsm,tr[X].rmxsm);
            for(int i = 1; i <= dep; ++i) printf("口");
        	//printf("ID:%d    VAL:%d    SM:%d   CHANGE_TAG:%d \n",X,tr[X].v,tr[X].sm,tr[X].lzy_chng);
        	printf("%d %d\n",tr[X].v,tr[X].mxsm);
            prnt(tr[X].sn[1], dep+1);
        }
        inline void build(int L,int R_R,int *IN,int D,int FA){
        	if(L>R_R){
        		return;
			}
        	int P=nwlc(FA,D,IN[MID]);
        	build(L,MID-1,IN,0,P);
        	build(MID+1,R_R,IN,1,P);
        	updt(P);
		}
    public:
        inline void INSERT(int L,int TOT,int *IN){
            int X=preSplay(L+1,0);
            build(1,TOT,IN,1,X);
            updt(X),updt(tr[X].fa),updt(tr[tr[X].fa].fa);
       }
        inline void DELETE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            rmv(X);
            updt(tr[rt].sn[0]),updt(rt);
        }
        inline void MAKE_SAME(int L,int LEN,int V){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_chng=V;
            chng(X);
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void REVERSE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_flp^=1;
            if(tr[X].lzy_flp){
            	flp(X);
            }
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void GET_SUM(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            printf("%d\n",tr[X].sm);
        }
        inline void MAX_SUM(){
            printf("%d\n",(tr[rt].mxsm)?tr[rt].mxsm:tr[rt].mx);
        }
        inline void INIT(int N,int *IN){
            tr[0].init();
            rt=tp=cnt=0;
            int X=0;
            for(int i=1;i<=N;++i){
                X=nwlc(X,1,IN[i]);
            }
            nwlc(1,0,-MAGIC),nwlc(X,1,-MAGIC);
            splayRnw(N+1),splayRnw(N+2);
        }
        inline void PRINT(){
            printf("%d ->\n",rt);
            prnt(rt);
            puts("");
        }
};
int n,m;
int a[4000005];
Splay T;
void init(){
    scanf("%d%d",&n,&m);
    int posi,tot,c;
    char op[10];
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    T.INIT(n,a);
    for(int i=1;i<=m;++i){
        std::cin>>op;
        switch(op[2]){
            case 'S':{
                scanf("%d%d",&posi,&tot);
                for(int j=1;j<=tot;++j){
                    scanf("%d",a+j);
                }
                T.INSERT(posi,tot,a);
                break;
            }
            case 'L':{
                scanf("%d%d",&posi,&tot);
                T.DELETE(posi,tot);
                break;
            }
            case 'K':{
                scanf("%d%d%d",&posi,&tot,&c);
                T.MAKE_SAME(posi,tot,c);
                break;
            }
            case 'V':{
                scanf("%d%d",&posi,&tot);
                T.REVERSE(posi,tot);
                break;
            }
            case 'T':{
                scanf("%d%d",&posi,&tot);
                T.GET_SUM(posi,tot);
                break;
            }
            case 'X':{
                T.MAX_SUM();
                break;
            }
        }
    }
}

int main(){
    init();
    return 0;
}
发布于

CF1093

这场比赛打得很糟心，具体来说就是Debug能力不足。勉强涨了一点分。

CF1093 A
一道水题。依照题意模拟即可。 

#include<iostream>
#include<cstdio>

int n;
void init(){
	scanf("%d",&n);
	int x,ans;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		ans=x/7+1;
		printf("%d\n",ans);
	}
}

int main(){
	init();
	return 0;
}

CF1093 B
将字符串排序之后，如果第一项和最后一项不同，那它肯定不是回文；如果相同，那么中间也都相同，判一下即可。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

int n,len;
char ch[1005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		std::memset(ch,0,sizeof(ch));
		std::cin>>ch+1;
		len=std::strlen(ch+1);
		std::sort(ch+1,ch+1+len);
		if(ch[1]==ch[len]){
			puts("-1");
			continue;
		}else{
			puts(ch+1);
		}
	}
}

int main(){
	init();
	return 0;
}

CF1093 C
考虑到数列单调不减，则A序列的前半部分也单调不减，那么我们维护一个值表示当前值，然后从\(1\)扫到\(\frac{n}{2}\)即可。该增加的时候就增加。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

int n;
long long a[200005],b[200005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=(n>>1);++i){
		scanf("%I64d",b+i);
	}
	long long nw=0;
	for(int i=1;i<=(n>>1);++i){
		if(i>1&&b[i]-nw>b[i-1]-a[i-1]){
			nw=b[i]-b[i-1]+a[i-1];
		}
		a[i]=nw,a[n-i+1]=b[i]-nw;
	}
	for(int i=1;i<=n;++i){
		printf("%I64d ",a[i]);
	}
}

int main(){
	init();
	return 0;
}

CF1093 D
考虑每一个连通块各自独立，所以分别计算出值然后乘一起即可。
又，我们发现，本质上题目要求的就是一条线段两端的点的权值的奇偶性不同。
所以我们可以对一个连通块二染色，使得任意两种颜色不相邻。很容易可以证明，要么没有方案，要么方案只有一种。
我们分别考虑用一和三来填充黑色和白色，方案数很显然是\(2^{size_0}+2^{size_1}\)。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
#include<queue>
const long long MOD = 998244353;
struct ee{
	int v;
	int nxt;
}e[600005];
int h[300005],et=0;
inline long long pw(int A,int X){
	long long RT=1,BS=A;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=MOD;
		}
		BS*=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
bool clr[300005],vis[300005];
std::queue<int> q;
struct data{
	int A;
	int SZ;
}; 
inline data slv(int X){
	int RT=0;
	clr[X]=0,vis[X]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(X);
	int P,SZ=0;
	while(!q.empty()){
		P=q.front();
		q.pop();
		++SZ;
		if(!clr[P]){
			++RT;
		}
		for(int i=h[P];i;i=e[i].nxt){
			if(vis[e[i].v]){
				if(clr[e[i].v]==clr[P]){
					return (data){-1,-1};
				}
			}else{
				vis[e[i].v]=1;
				clr[e[i].v]=clr[P]^1;
				q.push(e[i].v);
			}
		}
	}
	return (data){RT,SZ};
} 
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	long long ans=1;
	data A;
	for(int i=1;i<=n;++i){
		clr[i]=0;vis[i]=0;
	}	
	for(int i=1;i<=n;++i){
		if(vis[i]){
			continue;
		}else{
			A=slv(i);
			if(A.A==-1){
				puts("0");
				return;
			}
			ans*=(pw(2,A.SZ-A.A)+pw(2,A.A));
			ans%=MOD;
		}
	}
	ans%=MOD;
	printf("%I64d\n",ans);
}
inline void CLEAR(){
	for(int i=1;i<=et;++i){
		e[i].v=e[i].nxt=0;
	}
	for(int i=1;i<=n;++i){
		h[i]=0;
	}
	n=0,m=0,et=0;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
		CLEAR();
	}
	return 0;
}
发布于

AGC029

这一场打得还行，可惜C没有调出来。不过还是暴涨七百多分。摸不透算分机制。

AGC 29 A
给定一个01序列，每一次可以把01变成10，求最大操作次数。
猜结论题（其实证明很显然）。结论是每一个1后面的0的个数之和。 

#include<iostream>
#include<cstdio>
#include<cstring>

int n;
char ch[200005];
int sm[200005];
void init(){
	std::cin>>(ch+1);
	n=std::strlen(ch+1);
	for(int i=1;i<=n;++i){
		ch[i]=(ch[i]=='B'?1:0);
	}
	sm[n+1]=0;
	for(int i=n;i>=1;--i){
		sm[i]=sm[i+1]+(ch[i]^1);
	}
	long long ans=0;
	for(int i=1;i<=n;++i){
		if(ch[i]){
			ans+=sm[i+1];
		}
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}

AGC 29 B
给定一个序列，问从中最多能找出多少个数对使得它们的和是二的次幂。
贪心。考虑从大往小遍历，如果一个大的数能够找到一个比它小的数配成二的次幂，那么不选这个大的数肯定不会更优。
用\(map\)优化一下即可。 

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>

std::map<int,int> mp;

int n,a[200005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		mp[a[i]]?(++mp[a[i]]):mp[a[i]]=1;
	}
	std::map<int,int>::iterator it=mp.end();
	--it;
	
	int ans=0,nw;
	while(1){
		if(it->second==0){
			goto loop;
		}
		nw=it->first;
		for(int i=30;i>=1;--i){
			while(it->second>=1&&(1<<i)-nw>=0&&mp[(1<<i)-nw]>=1&&(nw!=(1<<(i-1)))){
				--mp[(1<<i)-nw];
				it->second-=1;
				++ans;
			}
			while(it->second>=2&&nw==(1<<(i-1))){
				it->second-=2;
				++ans;
				
			}
		}
		loop:
			if(it==mp.begin()){
				break;
			}
			--it;
	}
	
	printf("%d\n",ans);
} 

int main(){
	init();
	return 0;
}

AGC 29 D
容易知道，每一轮T一定是能走就走。因为如果T不走，那么A就可以通过不走来强迫游戏结束。
并且，如果P经过了一个障碍上方，游戏就结束了。所以A一定会尽可能地让P走到一个障碍上方。
故而，A不往右走，只有两种情况。一，是下方存在一个障碍；二，是右边有障碍挡住。
很显然，如果固定起始点，只有横坐标与纵坐标相同的点才会挡住A。
因此，每一次A被挡住了，就更新起始点，然后向下走即可。 

#include<iostream>
#include<cstdio>
#include<algorithm>

struct data{
	int x;int y;
	inline bool operator<(const data &B){
		return x==B.x?y<B.y:x<B.x;
	}
	inline void init(int X,int Y){
		x=X,y=Y;
	}
}a[200005];
int n,h,w;
void init(){
	scanf("%d%d%d",&h,&w,&n);
	int x,y;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		a[i].init(x,y);
	}
	std::sort(a+1,a+1+n);
	int nw=0;
	for(int i=1;i<=n;++i){
		if(a[i].x-nw==a[i].y){
			++nw;
		}
		if(a[i].x-nw>a[i].y){
			printf("%d\n",a[i].x-1);
			return;
		}
	}
	printf("%d\n",h);
}

int main(){
	init();
	return 0;
}
发布于

lp5104 红包发红包

在\(\lbrack 0,1 \rbrack \)中任取一个数，期望是\(\frac{1}{2}\)
同理，在\(\lbrack 0,w \rbrack \)中任取一个数，期望是\(\frac{w}{2}\)
故而，取\(k\)个数的期望是\(\frac{w}{2^k}\)
费马小定理加快速幂即可。 

#include<iostream>
#include<cstdio>
const long long MOD = 1000000007;

inline long long pw(int A,long long X){
	long long RT=1,BS=A;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=MOD;
		}
		BS*=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}

inline long long inv(int X){
	return pw(X,MOD-2);
}

long long w,n,k;

void init(){
	scanf("%lld%lld%lld",&w,&n,&k);
	printf("%lld\n",(w*(inv(pw(2,k))))%MOD);
}

int main(){
	init();
	return 0;
}
发布于

lp3391 【模板】文艺平衡树（Splay）

虽然说是模板题，但实际上时候在考察Splay一个很巧妙的运用，也就是用Splay模拟区间。
首先我们发现二叉排序树一个很巧妙的性质：对于一个点\(a\)和它的一个孩子\(b\)，若令\(b\)是\(a\)的\(D\)方向的孩子，
那么区间\((a,b)\)内的所有数都在以\(b\)的\(D\ xor\ 1\)方向上的孩子为根的子树中。
然后我们考虑翻转操作。我们毫不惊讶地发现，当我们将一棵子树上的所有节点都左右调换以后，这棵子树所代表的区间就完成了翻转。
对于一个节点来说，它的位置就已经表示了它的大小。
但是，如果对于每一次翻转我们都翻转整棵子树的话，复杂度是不可接受的。我们考虑一种类线段树的操作方法，也就是使用\(Lazy Tag\)来维护翻转。
而，除了翻转操作之外，会改变树的结构的只有旋转操作。于是我们只需要在旋转之前下放\(x\)和\(fa\)的延迟标记即可。
另外尤其要注意不要旋转过头。 

#include<iostream>
#include<cstdio>
class Splay{
	private:
		class Node{
			public:
				int v;
				int sz;
				int fa;
				int sn[2];
				int lzy;
		};
		Node tr[200005];
		int rt;
		inline void prnt(int X){
			if(!X){
				return;
			}
			pshd(X);
			prnt(tr[X].sn[0]);
			printf("%d ",tr[X].v);
			prnt(tr[X].sn[1]);
		}
		inline void debugPrnt(int X){
			if(!X){
				return;
			}
			pshd(X);
			debugPrnt(tr[X].sn[0]);
			printf("[%d,%d]{%d}:%d ",tr[X].sn[0],tr[X].sn[1],tr[X].fa,tr[X].v);
			debugPrnt(tr[X].sn[1]);
		}
		inline void pshd(int X){
			if(tr[X].lzy){
				tr[X].lzy^=1;
				tr[tr[X].sn[0]].lzy^=1,tr[tr[X].sn[1]].lzy^=1;
				std::swap(tr[X].sn[0],tr[X].sn[1]);
			}
		}
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
		}
		inline int fndD(int X){
			return tr[tr[X].fa].sn[0]==X?0:1;
		}
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			pshd(tr[X].fa),pshd(X);
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayRnw(int X){
			while(tr[X].fa){
				splayOne(X);
			}
			rt=X; 
		}
		inline int fnd(int X){
			int P=rt,FP=0;
			while(P){
				pshd(P);
				FP=P;
				if(tr[tr[P].sn[0]].sz+1<X){
					X-=(tr[tr[P].sn[0]].sz+1);
					P=tr[P].sn[1];
				}else if(tr[tr[P].sn[0]].sz<X){
					return P;
				}else{
					P=tr[P].sn[0];
				}
			}
			return FP;
		}
	public:
		inline void build(int N){
			for(int i=1;i<=N;++i){
				tr[i].sn[0]=i-1;
				tr[i].v=i;
				tr[i].fa=i+1;
				tr[i].sz=1;
			}
			tr[N].fa=0;
			tr[1].sn[0]=N+1,tr[N].sn[1]=N+2;
			tr[N+1].v=-2147483647,tr[N+2].v=2147483647;
			tr[N+1].fa=1,tr[N+2].fa=N;
			tr[N+1].sz=1,tr[N+2].sz=1;
			rt=N;
			splayRnw(N+1);
			splayRnw(N+2);
		}
		inline void flp(int L,int R){
			//printf("[%d](%d,%d)\n",rt,fnd(L),fnd(R+2));
			splayRnw(fnd(L));
			splayRnw(fnd(R+2));
			tr[tr[tr[rt].sn[0]].sn[1]].lzy^=1;
		}
		inline void splayPrnt(int N){
			splayRnw(N+1);
			splayRnw(N+2);
			prnt(tr[tr[rt].sn[0]].sn[1]);
			puts("");
		}
		inline void debug(){
			printf("%d ->",rt);
			debugPrnt(rt);
			puts("");
		}
};
int n,q;
Splay T;
void init(){
	int n,q;
	scanf("%d%d",&n,&q);
	int l,r;
	T.build(n);
	for(int i=1;i<=q;++i){
		scanf("%d%d",&l,&r);
		T.flp(l,r);
	}
	T.splayPrnt(n);
}
int main(){
	init();
	return 0;
}
发布于

平衡树-Splay

我们将一棵以\(Splay\)方式维护的二叉搜索树封装为一个对象。
对于这个对象，我们定义它的一类私有对象\(Node\)，代表二叉搜索树上的一个节点。
对于这个节点，在通常情况下，我们需要维护的信息包括：
\(sn\)，这是一个有两个元素的数组。其中第\(0\)项表示左子节点，第\(1\)表示右子节点。
\(fa\)，表示它的父节点。
\(v\)，表示它的值。
\(nm\)，表示值为\(v\)的数的个数。
\(sz\)，表示所有子节点中的数的个数的和。

对于一棵二叉搜索树上的一个节点，我们定义它的旋转、单旋和双旋操作。
定义一个函数\(fndD(X)\)，表示一个节点相对于它的父节点是\(fndD(X)\)子节点
那么，一个节点\(X\)的旋转操作为：
将它的\(fndD(X)\ xor\ 1\)子节点作为它的父节点的\(fndD(X)\)子节点，并将\(X\)作为它的祖父节点的\(fndD(X_fa)\)节点，然后将它原来的父节点变成它的\(fndD(X)\ xor \ 1\)节点。
定义一个节点的单旋操作为，将这个节点向上旋转两次。
定义一个节点的双旋操作为，将这个节点的父节点向上旋转一次，然后再将这个节点向上旋转一次。
同时，我们定义一个将一个节点一直依据下述方法单旋/双旋到根的操作为一个伸展操作：
对于一个相对于其父亲的位置与其父亲相对于其祖父的位置相同的节点，对它采用双旋操作。
对于一个相对于其父亲的位置与其父亲相对于其祖父的位置不同的节点，对它采用单旋操作。

下面我们用一种被称为势能分析法的复杂度分析方式来分析它的复杂度。

我们定义关于一个节点\(X\)的势能函数\(\phi(X)\)，定义为它的子树大小取对数。我们定义关于整棵二叉搜索树\(T\)的一个势能函数\(\Phi (T)\)，定义为它的所有节点的\(\phi\)值之和。

对于第\(i\)次操作，我们定义一个函数\(T\)和一个摊还代价辅助函数\(A\)，其中\(T(i)\)表示第\(i\)次操作消耗的实际时间。\(A(i)\)由下述式子定义：
$$A_{i}=T_{i}+\Phi_{i}-\Phi_{i-1}$$
那么，我们可以得到公式：
$$A_{sum}=\sum_{i=1}^{q}A_{i}=\sum_{i=1}^{q}T_{i}+\Phi_{q}-\Phi_{0}$$
故而，我们只需要求出对于每一次操作的\(T\)与\(\Delta\Phi\)即可。

考虑到，每一个操作事实上都可以视为一次\(Splay\)操作，所以我们只需要考虑各类\(Splay\)操作造成的影响即可。
故而，我们需要计算的便是旋转、单旋和双旋对的操作复杂度以及它们对\(\Phi(T)\)的影响。

首先我们分析旋转操作。
容易知道，对于一次关于节点\(X\)的旋转操作，会改变\(\phi\)值的有且仅有两个节点：\(X\)和它的父亲\(Y\)。
我们定义\(X\)旋转后的节点为\(X’\)，\(Y\)旋转后的节点为\(Y’\)，很容易可以得到一个式子：
$$\Delta\Phi = \phi_{X’} – \phi_{X} + \phi_{Y’} – \phi_{Y}$$
考虑到旋转操作后，\(X’\)位于\(Y\)的位置，并且节点的数量没有增减、对父节点也没有影响，所以得到\(\phi_{X’}=\phi_{Y}\)
考虑\(Y’\)是\(X’\)的子节点，我们可以得到
$$ \phi_{X’} > \phi_{Y’}$$
将上述两式代入式中，可得：
$$\Delta\Phi < \phi_{X’} – \phi_{X}$$
于是可以证明，一次旋转的均摊复杂度上界是\(O(\phi_{X’}-\phi_{X})\)

然后我们分析单旋操作。
依然是定义一个关于节点\(X\)的旋转操作，定义它的父亲为\(Y\)，祖父为\(Z\)，旋转后分别为\(X’,Y’,Z’\)
很容易可以得到一个式子：
$$\Delta\Phi = \phi_{X’} – \phi_{X} + \phi_{Y’} – \phi_{Y} + \phi_{Z’} – \phi_{Z}$$
同理于旋转操作，我们可以得到：
$$\phi_{X’} = \phi_{Z}$$
故而：
$$\Delta\Phi = – \phi_{X} + \phi_{Y’} – \phi_{Y} + \phi_{Z’}$$
同理于旋转操作，我们可以得到：
$$\phi_{Y’}<\phi_{X’},\phi_{X}<\phi_{Y}$$ 故而：$$\Delta\Phi < \phi_{X’} + \phi_{Z’} – 2\phi_{X}$$$$\Delta\Phi < 2(\phi_{X’}-\phi_{X}) – \phi_{X’} – \phi_{Z’}$$又，$$\phi_{X’} + \phi_{Z’} = log_{2}{|X’||Z’|} > 2$$
所以，
$$\Delta\Phi < 2(\phi_{X’}-\phi_{X}) – 2$$

故而单旋操作的复杂度为\(O(\phi_{X’}-\phi_{X})\)

双旋操作的复杂度同理。

令总共进行了\(n\)次旋转操作，对于总体的复杂度上界，我们有：
$$A_{sum}<\sum_{i=1}^{n}\phi_{i}-\phi_{i-1}$$
故而得到最终的摊还复杂度：\(O(\phi_{n})\)

然而，上述的势能分析法仍然不够直观。下面我们考虑一种基于伸展操作的性质的另一种分析法。
引理一： 每一次伸展操作，必然会使得从这个节点到根的一条链的长度折半。
首先我们考虑单旋和双旋操作的使用情况。
我们称应当使用双旋的情况为一字型，应当使用单旋的情况为之字形，很容易可以发现，原来已有的一条链总是会被拆成两个部分。
而，详细地考虑各种情况，我们发现，不存在一种链，使得这种折半失效。
故而，我们得到了引理一。

下面考虑引理一是怎样在实际情况中发挥作用的。
我们说一个节点的深度可接受，指的是它的深度是\(log_2n\)的常数倍。
考虑对某一个节点进行操作。如果这个节点的深度可接受，那么操作它的复杂度也是可接受的。
如果这个节点的深度不可接受，根据引理一，总是可以在\(log_2n\)次操作以内将其的深度变为可接受的。
而每一次操作最多只会令这个链的深度加一，因此\(log_2n\)次操作的复杂度可以均摊到那些令这个链深度加一的操作上，从而使操作的均摊浮渣度仍然是可接受的。

注意：
1.三目运算符优先级比逗号高。
2.函数名不要搞混。
3.注意区分节点大小和子树大小。
4.当寻找前驱的时候，当前值与当前点的值相等应当向左走；当寻找后继时，当前值与当前点的值相等应当向右走。 

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXQ 1000005
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Min(int A,int B){
    return A<B?A:B;
}
class Splay{
	private:
		class Node{
    		public:
    			int sn[2];
    			int fa;
    			int v;
    			int nm;
    			int sz;
    			inline void set(int FA,int LS,int RS,int V){
    			    fa=FA,v=V,sn[0]=LS,sn[1]=RS,nm=1,sz=1;
                }
                inline void init(){
                	sn[0]=sn[1]=fa=v=nm=sz=0;
				}
		};
		int INF;
		Node tr[MAXQ];
		int st[100005],tp,cnt,rt;
		inline int fndD(int X){
			return tr[tr[X].fa].sn[0]==X?0:1;
		}
		inline void szRnw(int X){
		    tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].nm;
        }
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[tr[X].sn[D^1]].fa=tr[X].fa;tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa;tr[X].fa=tr[tr[X].sn[D^1]].fa;
			tr[tr[X].sn[D^1]].fa=X;tr[tr[X].fa].sn[D2]=X;
			szRnw(tr[X].sn[D^1]);szRnw(X);
			if(!tr[X].fa){
				rt=X;
			}
		}
		inline void splayTwo(int X){
		    int D=fndD(X),D2=fndD(tr[X].fa);
		    tr[X].fa?
				(tr[tr[X].fa].fa?
					(D==D2?
						(splayOne(tr[X].fa),splayOne(X),0)
						:(splayOne(X),splayOne(X),0))
					:(splayOne(X),0))
				:0;
		}
		inline void splayRnw(int X){
			while(tr[X].fa){
			    splayTwo(X);
            }
		}
		inline int nwlc(int FA,int LS,int RS,int V,int D){
			if(!cnt){
				rt=1;
			}
			int P=tp?st[tp--]:++cnt;
		    tr[FA].sn[D]=P;
		    tr[P].set(FA,LS,RS,V);
		    return P;
        }
        inline int fnd(int V){
            int P=rt,FP=0;
            while(P){
                FP=P;
                if(tr[P].v==V){
                    splayRnw(P);
                    return P;
                }
                P=tr[P].sn[tr[P].v>V?0:1];
            }
            return FP;
        }
        inline int fndMn(int X){
            int P=X,FP=tr[X].fa;
            while(P){
                FP=P;
                P=tr[P].sn[0];
            }
            return FP;
        }
        inline int fndMx(int X){
        	int P=X,FP=tr[X].fa;
        	while(P){
        		FP=P;
        		P=tr[P].sn[1];
			}
			return FP;
		}
		inline void clr(int X,int D){
			if(D==2){
				tr[X].init();
				st[++tp]=X;
				return;
			}
			rt=tr[X].sn[D],tr[tr[X].sn[D]].fa=0;
			tr[X].init();
			st[++tp]=X;
		}
		inline void init(int P){
			if(!tr[P].sn[0]||!tr[P].sn[1]){
				tr[P].sn[0]?(clr(P,0)):(tr[P].sn[1]?clr(P,1):clr(P,2));
			}else{
				int RS=fndMn(tr[P].sn[1]);
				tr[RS].sn[0]=tr[P].sn[0],tr[tr[P].sn[0]].fa=RS;
				clr(P,1);
				splayRnw(RS);
			}
			if(!tr[rt].v&&!tr[rt].sz&&!tr[rt].fa&&!tr[rt].nm){
				splayInit();
			}
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].sn[0]);
			printf("(%d)%d:[%d,%d][%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].fa);
			prnt(tr[X].sn[1]);
		}
	public:
	    inline void psh(int V){
	        int P=rt,FP=0,D=0;
	        while(P){
	            FP=P;
	            if(tr[P].v==V){
	                ++tr[P].nm;
	                splayRnw(P);
	                return;
                }
                D=tr[P].v>V?0:1;
	            P=tr[P].sn[tr[P].v>V?0:1];
            }
            splayRnw(nwlc(FP,0,0,V,D));
        }
        inline void del(int V){
            int P=fnd(V);
            splayRnw(P);
            tr[P].nm>1?(--tr[P].nm):(init(P),0);
        }
        inline int fndPre(int V){
            int P=rt,RT=-INF;
            while(P){
                RT=tr[P].v<V?Max(RT,tr[P].v):RT;
                P=tr[P].sn[tr[P].v<V?1:0];
            }
            return RT;
        }
        inline int fndNxt(int V){
            int P=rt,RT=INF;
            while(P){
                RT=tr[P].v>V?Min(RT,tr[P].v):RT;
                P=tr[P].sn[tr[P].v>V?0:1];
            }
            return RT;
        }
        inline int rnk(int V){
            int P=rt,RT=0;
            while(P){
                if(tr[P].v>V){
                    P=tr[P].sn[0];
                }else if(tr[P].v==V){
                    RT+=tr[tr[P].sn[0]].sz;
                    splayRnw(P);
                    return RT+1;
                }else{
                    RT+=tr[tr[P].sn[0]].sz+tr[P].nm;
                    P=tr[P].sn[1]; 
                }
            }
            return RT+1;
        }
        inline int aRnk(int V){
            int P=rt;
            while(P){
                if(tr[tr[P].sn[0]].sz+tr[P].nm<V){
                    V-=(tr[tr[P].sn[0]].sz+tr[P].nm);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<V){
                    return tr[P].v;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return P;
        }
        inline void splayInit(){
			INF=2147483647,tp=0,cnt=0,rt=0;
			memset(tr,0,sizeof(tr));
		}
		inline void splayPrnt(){
			prnt(rt);
			puts("");
		}
}; 
Splay T;
void init(){
	int n,x,op;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		//T.splayPrnt();
		scanf("%d%d",&op,&x);
		switch(op){
			case 1:{
				T.psh(x);
				break;
			}
			case 2:{
				T.del(x);
				break;
			}
			case 3:{
				printf("%d\n",T.rnk(x));
				break;
			}
			case 4:{
				printf("%d\n",T.aRnk(x));
				break;
			}
			case 5:{
				printf("%d\n",T.fndPre(x));
				break;
			}
			case 6:{
				printf("%d\n",T.fndNxt(x));
				break;
			}
		}
	}
}
int main(){
//	freopen("Splay.out","w",stdout);
	T.splayInit();
	init();
	return 0;
}
发布于

博客已经恢复访问

在昨日晚上被短暂的墙以后，我申请了搬瓦工的更换IP服务，现在已经可以正常访问。
用亲身经历警告各位，千万不要在服务器上搭建任何梯子。

大江南北一片赤红。
博客恢复正常访问。
发布于

lp5077 Tweetuzki 爱等差数列

令首项为\(x\)，长度为\(l\)由等差数列求和式可得：
$$s=\frac{l(l-1)}{2}+l*x$$
故，题意等价于求：
使得式子：
$$2s=l(l-1+2x)$$
成立的最小\(x\)
即求使得式子成立的最大\(l\)
又，易知：
$$l<\sqrt{2s},s\le10^{12}$$
故，
$$l<10^{6}$$
显然这个复杂度是可以接受的。

#include<iostream>
#include<cstdio>
#include<cmath>
long long s;
inline void init(){
	scanf("%lld",&s);
	long long ans=0,len;
	for(long long i=1;i*i<=2*s;++i){
		if((2*s%i==0)&&(2*s/i-i+1>0)&&((s-(i*(i-1)/2))%i==0)){
			len=i;ans=((2*s)/i-i+1)>>1;
		}
	}
	printf("%lld %lld",ans,ans+len-1);
}

int main(){
	init();
	return 0;
}
发布于

lp5079 Tweetuzki 爱伊图

看似是一道暴力模拟题，实际上是一个技巧性模拟题。
我们注意到，对于除了2和5以外的所有的数，它们的每一列的#数量都是不同的，故而我们可以用1代表”#”，0代表”.”，然后跑一遍求和即可。
对于2和5，我们特殊处理，暴力扫描即可。 

#include<iostream>
#include<cstdio>
#include<algorithm>

char lst[12][100005];
int lst2[100005][12];
int cnt[100005];
int r,c;

inline bool cmp(int A,int B){
	return A>B;
}

void init(){
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			std::cin>>lst[i][j];
		}
	}
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			lst2[j][i]=lst[i][j]=='#'?1:0;
		}
	}
	for(int i=1;i<=c;++i){
		std::sort(lst2[i]+1,lst2[i]+1+r,cmp);
	}
	for(int i=1;i<=c;++i){
		for(int j=1;j<=r;++j){
			cnt[i]+=lst2[i][j];
		}
	}
	int cnt1=0,cnt2=0,cnt3=0;
	for(int i=1;i<=c;++i){
		if(!cnt[i]){
			cnt1=cnt2=cnt3=0;
		}else{
			cnt1=cnt[i],cnt2=cnt[i+1],cnt3=cnt[i+2];
			if(cnt1==5&&!cnt2){
				printf("1");
			}else{
				if(cnt1==4&&cnt2==3&&cnt3==4){
					bool bo=0;
					for(int j=1;j<=r;++j){
						if(lst[j][i]=='.'&&lst[j][i+1]=='.'&&lst[j][i+2]=='#'){
							bo=1;
						}else if(lst[j][i]=='#'&&lst[j][i+1]=='.'&&lst[j][i+2]=='.'){
							if(bo){
								printf("2");
							}else{
								printf("5");
							}
							break;
						}
					}
				}else if(cnt1==3&&cnt2==3&&cnt3==5){
					printf("3");
				}else if(cnt1==3&&cnt2==1&&cnt3==5){
					printf("4");
				}else if(cnt1==5&&cnt2==3&&cnt3==4){
					printf("6");
				}else if(cnt1==1&&cnt2==1&&cnt3==5){
					printf("7");
				}else if(cnt1==5&&cnt2==3&&cnt3==5){
					printf("8");
				}else if(cnt1==4&&cnt2==3&&cnt3==5){
					printf("9");
				}else if(cnt1==5&&cnt2==2&&cnt3==5){
					printf("0");
				}
				i+=2; 
			}
		}
	}
}

int main(){
	init();
	return 0;
}
发布于

lp2540 NOIP2015 斗地主增强版

首先，我们注意到花色对于斗地主不会造成任何影响，所以我们可以忽视掉花色这个信息。
然后，我们将剩余的信息，依据数码的从小到大储存。
然后我们可以注意到，对于一种出牌方式，调整一些牌组的出牌顺序对答案并不会造成影响。
并且，散牌似乎具有贪心的性质。看起来如果能出三带二那么出三带一就不会更优，如果能出四带二那出三带二就不会更优。
对于顺子的情况是一个例外，因为如果能出顺子的话，可能存在一种情况，使得不出顺子比出顺子更优；亦有可能将一个顺子出一部分会更优。故而对于顺子应该爆搜判定。
总结起来就是：爆搜出顺子，贪心出散牌。
但是仔细考虑，我们可以发现，这种贪心是一种想当然的对正确答案的近似。这事实上仅因为四不可带一这一性质。
故而，对于4 4 1 2的情况，用上述的贪心得出的答案应当是3，然而事实上只需2即可。
但是，前面仍然有一个结论是正确的——也就是，出牌顺序不对答案造成影响。又考虑到，数码的顺序其实仅对顺子而言有意义。
所以我们可以仅储存，数量为k的数码有多少种，从而可以用5^13的空间复杂度预处理每一种散牌的状态。
但是如果这么做的话会发现连样例二都过不了。这事实上是因为，暴力搜索散牌的时间复杂度是完全不可接受的。
考虑到状态数极少，可以记忆化搜索来完成预处理。
用f[i][j][k][l]表示，有i个1，j个2，k个3，l个4时的最小解决花费即可。
几个坑点：
1.出顺子的时候应当是-=,+=而非直接赋值。
2.预先判双王以后应当计算花费。
3.出顺子的时候，在遍历到长度没达到要求的区间的时候也应当先将其清零然后在遍历之后加回去。
4.注意四带二的各种拆法：理论上应当有\(C_{4}^{2}+C_{3}^{2}\)种，少一种都不行，例如：两组三张和两组四张可以把两组三张拆开来打。
真可以说是丧心病狂的模拟题。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define dfs(X) X.srch()
//所有数+10之后mod13,13小王,14大王。 
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Min(int A,int B){
    return A<B?A:B;
}
struct statue;
int n,ans=0x3f3f3f3f,f[14][14][9][7];
int CNT[4]={0,0,0,0};
struct statue{
    int cst;
    int a[15];
    inline void init(){
        for(int i=0;i<15;++i){
            a[i]=0;
        }
    }
    inline statue(int cstin){
        cst=cstin;
    }
    inline void srch(){
        /*
        for(int i=0;i<15;++i){
            printf("%d ",a[i]);
        }
        printf("\n");
        */
        statue nw(cst+1);
        for(int i=0;i<15;++i){
            nw.a[i]=a[i];
        }
        for(int i=0;i<12;++i){
            if(a[i]>=3){
                nw.a[i]-=3;
                for(int j=i+1;j<12;++j){
                    if(a[j]<3){
                        break;
                    }
                    nw.a[j]-=3;
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<3){
                        break;
                    }
                    nw.a[j]+=3;
                }
                nw.a[i]+=3;
            }
            if(a[i]>=2){
                nw.a[i]-=2;
                for(int j=i+1;j<12;++j){
                    if(a[j]<2){
                        break;
                    }
                    nw.a[j]-=2;
                    if(j-i<2){
                        continue;
                    }
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<2){
                        break;
                    }
                    nw.a[j]+=2;
                }
                nw.a[i]+=2;
            }
            if(a[i]>=1){
                --nw.a[i];
                for(int j=i+1;j<12;++j){
                    if(a[j]<1){
                        break;
                    }
                    --nw.a[j];
                    if(j-i<4){
                        continue;
                    }
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<1){
                        break;
                    }
                    ++nw.a[j];
                }
                ++nw.a[i];
            }
        }
        CNT[0]=CNT[1]=CNT[2]=CNT[3]=0;
        for(int i=0;i<15;++i){
        	++CNT[a[i]-1];
		}
		ans=Min(ans,cst+f[CNT[0]][CNT[1]][CNT[2]][CNT[3]]);
//		printf("%d:%d %d %d %d\n",cst,CNT[0],CNT[1],CNT[2],CNT[3]);
    }
};
int II=0,JJ=0,KK=0,LL=0;
inline int rnw(int A,int B,int C,int D){
	if(A<0||B<0||C<0||D<0||A>13||B>13||C>8||D>6){
		return 0;
	}
    f[A][B][C][D]=Min(f[A][B][C][D],f[II][JJ][KK][LL]+1);
    return 0;
}
inline void prpr(){
    memset(f,0x3f,sizeof(f));
    f[0][0][0][0]=0;
    for(int i=0;i<=13;++i){
        for(int j=0;j<=13;++j){
            for(int k=0;k<=8;++k){
                for(int l=0;l<=6;++l){
//                	printf("%d %d %d %d\n",i,j,k,l);
                    II=i,JJ=j,KK=k,LL=l;
                    rnw(i,j,k,l+1);
                    rnw(i+2,j,k,l+1);
                    rnw(i,j+1,k,l+1);
                    rnw(i-1,j,k+1,l+1),rnw(i+1,j-1,k+1,l+1),rnw(i,j-1,k,l+2),rnw(i+1,j,k-1,l+2),rnw(i-1,j+1,k-1,l+2),rnw(i,j-2,k+2,k+1);
                    rnw(i,j+2,k,l+1);
                    rnw(i,j,k,l+2);
                    rnw(i-1,j+1,k+1,l+1),rnw(i-1,j-1,k+1,l+2),rnw(i-2,j,k+2,l+1);
                    
                    rnw(i,j,k+1,l);
                    rnw(i+1,j,k+1,l);
                    rnw(i,j+1,k+1,l);
                    
                    rnw(i,j+1,k,l);
                    
                    rnw(i+1,j,k,l);
                }
            }
        }
    }
}
void init(){
    ans=0x3f3f3f3f;
    int x,xx;
    statue s(0);
    s.init();
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&xx);
        ++s.a[(!x)?(12+xx):((x+10)%13)];
    }
    if(s.a[13]&&s.a[14]){
        s.a[13]=s.a[14]=0;
        ++s.cst;
        dfs(s);
        --s.cst;
        s.a[13]=s.a[14]=1;
    }
    dfs(s);
    printf("%d\n",ans);
}
int main(){
	prpr();
    int T;
    scanf("%d%d",&T,&n);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

lp2661 NOIP2015 信息传递

找图上最小环。删掉所有非环边即可。

#include<iostream>
#include<cstdio> 
struct ee{
    int v;
    int nxt;
}e[200005];
int h[200005],et=0;
bool vis[200005];
int n,in[200005],a[200005];
inline void add(int u,int v){
    e[++et]=(ee){v,h[u]};
    h[u]=et;
}
inline int fnd(int s){
    int x=s,nxt=a[x],rt=1;
    vis[x]=1;
    while(!vis[nxt]){
        ++rt;
        x=nxt;
        nxt=a[nxt];
        vis[x]=1;
    }
    return rt;
}
void init(){
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        add(i,x);
        ++in[x];
        a[i]=x;
    }
    int nw,nwxt;
    for(int i=1;i<=n;++i){
        nw=i;
        while(!in[nw]){
            --in[a[nw]];
            nwxt=nw;
            nw=a[nw];
            a[nwxt]=0;
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        if(!vis[i]&&a[i]){
            ans=std::min(ans,fnd(i));
        }
    }
    printf("%d\n",ans);
}

int main(){
    init();
    return 0;
}

 

发布于

二叉搜索树

二叉搜索树。
二叉搜索树是一棵二叉树。对于这棵树上的任意一个节点，右子树中的所有节点都大于它；左子树中的所有节点都小于它。
基于这个性质，我们可以以\(O(h)\)的时间的复杂度，来完成下述操作：
1.插入一个元素。
2.删除其中任意一个元素。
3.查找其中的一个元素。
4.查找第\(k\)大数。
5.询问某数的排名。
6.以常数更小的方式来查找一个数的前驱/后继。
7.以\(O(n)\)输出有序的整棵树。
8.查找将一个数插入树后的前驱/后继。
9.查找一个节点的子树大小。
下面我们一一讨论下述操作的实现。
操作6可能是最容易理解的一种操作。对于一个节点，如果要寻找它的后继，那么它的后继一定在如下两个位置之一：它的右子树，或者它的父亲。
如果它有右子树，那么它的后继一定在它的右子树中。这是因为，对于其他所有点，要么比它和它的右子树中的所有节点更大，要么比它们更小。这由二叉搜索树的基本性质可以轻松证明。
然后，它的后继一定是它的右子树中的最小点，这是因为右子树中的所有点都大于它。显然，这个最小点是右子树中最左的节点。我们称其为「后继右左定理」。
而上述的内容对于求一个有左子树的节点的前驱显然仍然是成立的。
如果它没有右子树，那么对于它的所有祖先，存在两种情况。
一是不存在任意一个祖先，使得这个祖先的父亲在这个祖先的右边，这种情况下，因为它没有右子树，所以它一定是整棵树中最大的节点，这样它就没有后继了；
另外一种是至少存在一个祖先，使得这个祖先的父亲在这个祖先的左边。
即，以这个祖先为根的整棵子树都是这个祖先的父亲的左子树，则此时很显然该节点是整棵子树中最右的节点。那么它显然是这个祖先的父亲的前驱。这可以根据「前驱左右定理」得出。
这样，我们就可以对任意的一个节点找到它的（如果存在）前驱和/或后继。
在有了操作6之后，我们就可以考虑操作1。如果插入的数比已有的任何数都大/都小，那么就一定可以插入到最右/左节点的右/左儿子。
如果不是这样的话，那么，它的大小一定在原来的一对大小相邻的数之间。
而综合「前驱左右定理」和「后继右左定理」，可以得出，一对大小相邻的节点之中，有且仅有一方的可以通过在子树中寻找来找到另一方。
这也就意味着，较大者的左子树和较小者的右子树中有且仅有一个是空的。那么，我们就一定可以把一个新的节点插入到一个空节点。
然后我们考虑操作3。它可以通过递归的二分操作来实现。假设我们当前在以\(x\)为根节点的子树中查找指定节点，
那么我们就可以根据二叉搜索树的性质，判断这个节点是\(x\)，或位于\(x\)的某一棵子树中。
于是我们就可以递归查找任意一个数。
同理，操作8也是可以用相似的方法来实现。当这个数递归查找到一个无法继续查找的节点\(x\)，
那么\(x\)一定是需要查找的数的前驱/后继，然后我们就可以通过操作6来查找这个数的后继/前驱。
接下来我们考虑操作4。操作4本质上也是一个树上二分的过程。我们首先计算出所有子树的大小，然后依据子树大小的单调性来递归查找第\(k\)大数。
于是我们考虑操作5，操作5可以在实现操作3的过程中实现。当每一次我们递归查找，我们同样也可以确定目标排名所在的一个区间，并且不断缩小这个区间。
事实上，每一次向下递归查找的过程，都确定了一部分的数一定大于或者小于目标数。当找到目标节点的时候，目标节点的区间就可以根据已有信息和它的左右子树（如果存在）来确定。
操作7就显得很显然了。通过中序遍历，我们可以以小-中-大的顺序来遍历整棵二叉树，也就将二叉树展开为一个有序序列。
它体现了二叉搜索树的性质的一个有趣的性质——对于任意一棵子树，它总是对应着有序序列上的一个连续区间。
这是因为，这棵子树之外的所有点，要么大于这棵子树中的所有点，要么小于这棵子树中的所有点。
另一方面，我们也可以从顶向下来理解这个过程。
对于根节点，它的左子树中的所有节点（如果存在）在序列中一定位于它左侧，而右子树（如果存在）中的所有节点在序列中一定位于它的右侧。
那么，递归地考虑每个子树，根据二叉搜索树的基本性质，它们都对应着一个有序的序列。所以它们总是对应着有序序列上的一个连续区间。
通过这种理解方式，我们也可以相应的理解（乃至证明）上诉的所有操作和性质。
下面是所有操作中最复杂的操作2，事实上操作2是唯一一个可能改变已有结构的操作。
对于需要删除的节点，存在三种情况。
情况一：它是一个叶节点。对于这种情况，我们只需要单纯地删除它，然后自底向顶更新子树大小。
情况二：它只有一个子节点。对于这种情况，我们只需要单纯地删除它，然后将它的子树接在它的父节点，然后自顶向上更新子树大小。
情况三：它既有左节点又有右节点。这种情况可能会比较复杂。首先我们知道，这个节点必然有前驱/后继。不妨将它的其他部分放在它的后继上。（前驱同理。）
这时候分两类讨论。
如果它的后继不是它的右子节点，那么可以将它的后继接在它的父节点，然后将它的右子树的其他部分作为它的后继的右子树。然后将它的左子树作为它的后继的左子树。
否则，我们将它的左节点放在它的后继的左节点处，然后将它的后继接在它的父节点。
对于操作9，我们只需要在每次更新的时候自顶向上计算贡献，存储好即可直接写出。
二叉搜索树是平衡树的基础，由于没有相关模板题，所以我也不太确定我的二叉搜索树有没有写挂。请各位多多指教。
 

#include<iostream>
#include<cstdio>
int st[100005],tp=0;
struct data{
    int v;int fa;int ls;int rs;int sz;int cnt;
}tr[100005];
int rot=0,trt=0;
inline int nwlc(){
    return tp?st[tp--]:++trt;
}
inline void init(int X){
    tr[X].cnt=tr[X].fa=tr[X].ls=tr[X].rs=tr[X].sz=tr[X].v=0;
    st[++tp]=X;
}
inline void rnw(int X){
    int P=X;
    while(P){
        tr[P].sz=tr[tr[P].ls].sz+tr[tr[P].rs].sz+tr[P].cnt;
        P=tr[P].fa;
    }
}
inline int nwpt(int V,int FA,int LS,int RS,int SZ){
    if(!rot){
        int P=1;trt=1;tp=0;rot=1;
        tr[P]=(data){V,0,0,0,1,1};
        return P;
    }
    int P=nwlc();
    tr[FA].v>V?tr[FA].ls=P:tr[FA].rs=P;
    tr[P]=(data){V,FA,LS,RS,SZ,1};
    return P;
}
inline int fndNm(int X){
    int P=rot,FP=0;
    while(P){
        FP=P;
        if(tr[P].v==X){
            FP=P;
            break;
        }
        P=X<tr[P].v?tr[P].ls:tr[P].rs;
    }
    return FP;
}
inline int fndMx(int X){
    int P=X,FP;
    while(P){
        FP=P;
        P=tr[P].rs;
    }
    return FP;
}
inline int fndMn(int X){
    int P=X,FP;
    while(P){
        FP=P;
        P=tr[P].ls;
    }
    return FP;
}
inline int fndPre(int X){
    if(tr[X].ls){
        return fndMx(tr[X].ls);
    }else{
        int P=X,NP;
        while(P){
            NP=P;
            P=tr[P].fa;
            if(tr[P].rs==NP){
                break;
            }
        }
        return P;
    }
}
inline int fndNxt(int X){
    if(tr[X].rs){
        return fndMn(tr[X].rs);
    }else{
        int P=X,NP;
        while(P){
            NP=P;
            P=tr[P].fa;
            if(tr[P].ls==NP){
                break;
            }
        }
        return P;
    }
}
inline int fndPP(int X){
    int MX=fndMx(rot);
    if(X<tr[MX].v){
        return MX;
    }
	int P=rot,FP=0;
	while(P){
		FP=P;
		if(tr[P].v==X){
			FP=P;
			break;
		}else{
			if(tr[P].v>X&&tr[tr[P].ls].v<X){
				FP=P;
				break;
			}else if(tr[P].v<X&&tr[tr[P].rs].v>X){
				FP=tr[P].rs;
				break;
			}
		}
		P=X<tr[P].v?tr[P].ls:tr[P].rs;
	}
	return fndPre(FP);
}
inline int fndNN(int X){
    int MN=fndMn(rot);
    if(X<tr[MN].v){
        return MN;
    }
	int P=rot,FP=0;
	while(P){
		FP=P;
		if(tr[P].v==X){
			FP=P;
			break;
		}else{
			if(tr[P].v>X&&tr[tr[P].ls].v<X){
				FP=tr[P].ls;
				break;
			}else if(tr[P].v<X&&tr[tr[P].rs].v>X){
				FP=P;
				break;
			}
		}
		P=X<tr[P].v?tr[P].ls:tr[P].rs;
	}
	return fndNxt(FP);
}
inline void trIns(int X){
    int P=rot,FP;
    while(P){
        FP=P;
        if(tr[P].v==X){
            ++tr[P].cnt;
            rnw(P);
            return;
        }
        P=(tr[P].v>X)?tr[P].ls:tr[P].rs;
    }
    rnw(nwpt(X,FP,0,0,1));
}
inline void cnnctP(int FA,int X,int SN){
    if(!SN){
        return;
    }
    tr[SN].fa=FA;
    tr[FA].ls==X?(tr[FA].ls=SN):(tr[FA].rs=SN);
}
inline void delP(int FA,int X,int SN){
    (tr[X].cnt>1)?--tr[X].cnt,cnnctP(FA,X,SN):cnnctP(FA,X,SN),init(X);
    rnw(SN?SN:FA);
}
inline void trDel(int X){
    if(!tr[X].ls&&!tr[X].rs){
        delP(tr[X].fa,X,0);
    }else if(tr[X].ls&&!tr[X].rs){
        delP(tr[X].fa,X,tr[X].ls);
    }else if(tr[X].rs&&!tr[X].ls){
        delP(tr[X].fa,X,tr[X].rs);
    }else{
        if(tr[X].rs==fndNxt(X)){
            tr[tr[X].ls].fa=tr[X].rs;
            tr[tr[X].rs].ls=tr[X].ls;
            delP(tr[X].fa,X,tr[X].rs);
        }else{
            int XN=fndNxt(X),LW;
            LW=tr[XN].fa;
            cnnctP(tr[XN].fa,XN,tr[XN].rs);
            tr[XN].rs=tr[X].rs;
            tr[tr[X].rs].fa=XN;
            tr[XN].ls=tr[X].ls;
            tr[tr[X].ls].fa=XN;
            tr[X].rs=XN;
            tr[XN].fa=X;
            delP(tr[X].fa,X,XN);
            rnw(LW);
        }
    }
}
inline int fndRnkN(int X){
    int P=rot;
    while(P){
        if(X<=tr[tr[P].ls].sz){
            X-=tr[tr[P].ls].sz;
            P=tr[P].ls;
        }else if(X<=tr[tr[P].ls].sz+tr[P].sz){
            return P;
        }else{
            X-=(tr[tr[P].ls].sz+tr[P].cnt);
            P=tr[P].rs;
        }
    }
    return -1;
}

inline int fndRnkS(int X){
    int P=rot,RT=0;
    while(P){
        P=(X<tr[P].v)?tr[P].ls:tr[P].rs,RT+=tr[tr[P].ls].sz;
    }
    return RT;
}
inline void trPrnt(int X){
    if(tr[X].ls){
        trPrnt(tr[X].ls);
    }
    printf("%d ",tr[X].v);
    if(tr[X].rs){
        trPrnt(tr[X].rs);
    }
}
int q;
void init(){
    scanf("%d",&q);
    int op,x;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&op,&x);
        switch(op){
            case 1: {
                trIns(x);
                break;
            }
            case 2: {
                trDel(fndNm(x));
                break;
            }
            case 3: {
                printf("%d\n",fndRnkS(x));
                break;
            }
            case 4:{
                printf("%d\n",tr[fndRnkN(x)].v);
                break;
            }
            case 5: {
                printf("%d\n",tr[fndPP(x)].v);
                break;
            }
            case 6: {
                printf("%d\n",tr[fndNN(x)].v);
                break;
            }
        }
    }
} 
int main(){
    init();
    return 0;
}

 

发布于

lp2679 NOIP2015 子串

首先观察数据范围和题意，我们猜测这是一道DP题。
我们首先维护\(f_{i,j,k}\)表示，对于\(B\)中的前\(i\)个字符，在\(A\)中的前\(k\)个字符中，可以用\(j\)个子串来完成匹配。
那么，对于一个当前的字符\(i\)，它如果需要匹配，我们有两种匹配方法：一是加到已有的串，二是新开一个串。
加到已有的串是很好转移的，直接\(f_{i+1,j,k+1}+=(A_{k+1}==B_{i+1})*f_{i,j,k}\)；
而如果是新开一个串，朴素的考虑肯定是从\(k\)往后扫，然后把状态转移到所有之后的可行的位置：\(f_{i+1,j+1,S}+=f{i,j,k}\)。
但将一个状态转移到多个状态的加速转移是很难实现的，所以我们考虑使用填表法。
很容易可以发现，对于一个状态\(f_{i,j,k}\)，它可以从上述的两种状态转移到。
故而我们可以得到一个朴素的转移方程：
\(f_{i,j,k}=(A_{k}==B_{i})*f_{i-1,j,k-1}+\sum_{S=i}^{k}f_{i-1,j-1,S}\)
观察可以发现，这个转移方程的复杂度瓶颈在于后面那个求和式——这使得整个转移的复杂度是\(O(n^{2}*m*k)\)的。
我们考虑优化转移。区间求和的转移优化已经可以说是套路了，我们只需要简单地维护一个前缀和即可。
用\(sm_{i,j,k}\)表示，要用\(1~k\)中的串\(j\)个串填充\(1~i\)的位置的方案数。
同时,\(40000000\)的空间复杂度对于\(128MB\)的内存限制来说是非常危险的。所以我们考虑滚动数组。
这样就做完了。

#include<iostream>
#include<cstdio>
/* 

*/
const long long MOD=1000000007;

int n,m,K;
long long f[2][205][1005],sm[2][205][1005];
char A[1005],B[205];
void init(){
    scanf("%d%d%d",&n,&m,&K);
    std::cin>>(A+1)>>(B+1);
    int nw=1;sm[0][0][0]=1;
    for(int i=1;i<=n;++i){
    	sm[nw][0][0]=1;
    	for(int j=1;j<=m;++j){
    		for(int k=1;k<=K;++k){
    			f[nw][j][k]=(A[i]==B[j])?((f[nw^1][j-1][k]+sm[nw^1][j-1][k-1])%MOD):0;
    			sm[nw][j][k]=(sm[nw^1][j][k]+f[nw][j][k])%MOD;
			}
		}
		nw^=1;
	}
    printf("%lld\n",sm[nw^1][m][K]);
}

int main(){
    init();
    return 0;
}

 

发布于

lp2260 清华集训2012 模积和

题目大意：求式子：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ mod\ j) (i \ne j)$$
的值。

那么容斥以后等价于求：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ mod\ j)-\sum_{i=1}^{min(n,m)}(n\ mod\ i)*(m\ mod\ i)$$

首先求：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ mod\ j)$$

首先，我们有定理：
$$ n\ mod\ p=n-p*\lfloor \frac{n}{p} \rfloor$$
然后配合上\(\Sigma\)的运算法则，我们可以把原式转化为：
$$n^{2}*m^{2}-m^{2}\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor-n^{2}\sum_{j=1}^{m}j\lfloor \frac{m}{j} \rfloor-\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor \sum_{j=1}^{m}j\lfloor \frac{m}{j} \rfloor$$
我们设：
$$ P=\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor,Q=\sum_{j=1}^{m}j\lfloor \frac{m}{j} \rfloor$$
所以我们可以用数论分块来分别计算\(P,Q\)的值。

而，对于第二部分：
$$R=\sum_{i=1}^{min(n,m)}(n\ mod\ i)*(m\ mod\ i)$$
我们不妨令\(n<m\)
那么将原式展开，可得：
$$R=\sum_{i=1}^{n}n*m-n*i\lfloor \frac{m}{i} \rfloor-m*i\lfloor \frac{n}{i} \rfloor+i^{2}\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor$$
这个式子显然也是可以数论分块的。但是我们需要计算\(i^{2}\)对于式子的贡献。
用一些简单的证明方法可以得到：
$$\sum_{i=1}^{n}i^{2}=\frac{n(2n+1)(n+1)}{6}$$
那么它的区间和即是：
$$\sum_{i=1}^{r}i^{2}-\sum_{i=1}^{l-1}i^{2}=\frac{(2r^2+2rl+2l^2-r-3l+2)(r-l+1)}{6}$$
于是我们就可以统计整个结果了。

现在我们来考虑数论分块。

数论分块是一种处理形如
$$ \sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor$$
的公式的求值的方法。

而对于函数：

$$f(x)=\lfloor \frac{a}{x} \rfloor$$

可以发现，对于连续的一段\(x\)的区间，它的值是相同的。
具体来说是，令值为\(k\)则，令区间的左端点为\(l\)，则整个区间的值为：
$$k=\lfloor \frac{n}{l} \rfloor$$
那么右端点\(r\)很显然是满足方程：
$$\lfloor \frac{n}{x} \rfloor=k$$
的最大值。
依据整除的性质得到的引理一，我们发现：
$$r=\lfloor \frac{n}{k} \rfloor$$
从而，区间为：
$$[l,\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$$

附：对于引理一的证明：

引理一：求证方程：
$$\lfloor \frac{n}{x} \rfloor=k$$
的解的最大值\(t\)为
$$t=\lfloor \frac{n}{k} \rfloor$$
我们令方程的一个合法解\(x\)满足：
$$x*k+r=n\ (0\le r < x)\ (1)$$
并令：
$$t=x+d$$
那么，有：
$$\lfloor \frac{n}{x+d} \rfloor=k$$
则：
$$(x+d)*k+r’=n\ (0\le r < x+d)\ (2)$$
联立方程\((1),(2)\)可得：
$$d*k+r’=r$$
由整除的定义可得：
$$d=\lfloor \frac{r}{k} \rfloor$$
很显然，当
$$x=\lfloor \frac{n}{k} \rfloor$$
时，
$$r=n\ mod\ k,r<k,\lfloor \frac{r}{k} \rfloor=0$$
此时\(x\)取到最大值。
证毕。

另：尽量用模块化编程，而不是去化简式子。这样可以用复杂度换取正确率。

#include<iostream>
#include<cstdio>
const long long MOD = 19940417;
const long long inv2 = 9970209;
const long long inv6 = 3323403;
long long n,m;
inline long long sm1(long long A){
    return (A*(A+1)%MOD)*inv2%MOD;
}
inline long long sm2(long long A){
    return ((A*(A+1)%MOD)*(2*A+1)%MOD)*inv6%MOD;
}
void init(){
    scanf("%lld%lld",&n,&m);
    n>m?n^=m^=n^=m:0; 
    long long P,Q,R;
    int l,r;
    r=0,P=0;
    while(r<n){
        l=r+1;
        r=(n/l)?(n/(n/l)):n;
        P+=(((r-l+1)*(n/l)%MOD)*(l+r)%MOD*inv2)%MOD;
        P%=MOD;
//        printf("P:%lld\n",P);
    }
    P%=MOD;
    r=0,Q=0;
    while(r<m){
        l=r+1;
        r=(m/l)?(m/(m/l)):m;
        Q+=(((r-l+1)*(m/l)%MOD)*(l+r)%MOD*inv2)%MOD;
        Q%=MOD;
//        printf("Q:%lld\n",Q);
    }
//    printf("%lld %lld\n",P,Q);
    Q%=MOD;
    R=(n*m%MOD)*n%MOD;
    long long ans=(n*m%MOD)*(n*m%MOD)%MOD-(n*n%MOD)*Q%MOD-(m*m%MOD)*P%MOD+P*Q%MOD;
    ans%=MOD;
    ans+=MOD;
    ans%=MOD;
    r=0;
    while(r<n){
        l=r+1;
        r=std::min((n/l)?(n/(n/l)):n,(m/l)?(m/(m/l)):m);
        CNT1=m/l;
        CNT2=n/l;
        R-=((((sm1(r)-sm1(l-1))%MOD)*(m/l)%MOD)*n%MOD+(((sm1(r)-sm1(l-1))%MOD)*(n/l)%MOD)*m%MOD);
        R+=(((sm2(r)-sm2(l-1))%MOD)*((m/l)*(n/l)%MOD))%MOD;
        R%=MOD;
    }
    ans-=R;
    ans%=MOD;
    ans+=MOD;
    ans%=MOD;
    printf("%lld",ans);
    
}
int main(){
    init();
    return 0;
}

 

发布于

lp2052 NOI2011 道路修建

作为一道NOI的题，它一度令我以为它是2001的。
不曾想，NOI竟然有这么水的题。
我一开始以为自己的写法错了。
但是…
唉，反正就是计算子树大小就对了。
另：存树的时候绝·对·不·可·以「u>v?u^=v^=u^=v:0」！！！这样会导致错误。反例：1->3,3->2。NOIP因为这个丢了很多分。

#include<iostream>
#include<cstdio>
#include<cmath>

struct ee{
    int v;
    int w;
    int nxt;
}e[2000005];
int h[1000005],et=0;
inline void add(int u,int v,int w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}

int n,in[1000005];
int f[10000005];
bool vis[1000005];
long long ans=0;
inline void dfs(int X){
    for(int i=h[X];i;i=e[i].nxt){
        if(vis[e[i].v]==1){
            continue;
        }
        vis[e[i].v]=1;
        dfs(e[i].v);
        ans+=1LL*e[i].w*(std::abs(((f[e[i].v]<<1)-n)));
        f[X]+=f[e[i].v];
    }
    ++f[X];
}


void init(){
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    vis[1]=1;
    dfs(1);
    printf("%lld",ans);
}

int main(){
    init();
    return 0;
}

 

发布于

lp1967 NOIP2013 货车运输

一道最大生成树加LCA的裸题。
因为是求路上权值最小的边权值最大，所以可以在最大生成树上跑。当然二分答案加01BFS也是一种想法，不过时间复杂度不对。
那么在最大生成树上很显然最大的路径上边权值最小。
所以在最大生成树上跑LCA，记录沿途路径最大值即可。
当然跑树剖也是可以的，不过很难写。

#include<iostream>
#include<cstdio>
#include<algorithm>

const int INF = 0x3f3f3f3f;

int n,m,q;

int FA[10005];
inline int fa( int X ){
    return X==FA[X]?X:(FA[X]=fa(FA[X]));
}
inline void mrg( int X, int Y ){
    X = fa( X ), Y = fa( Y );
    FA[X] = Y;
}

struct ee0{
    int u;
    int v;
    int w;
    inline bool operator < (const ee0 &B)const{
        return w > B.w;
    }
}e0[50005];

struct ee{
    int v;
    int w;
    int nxt;
}e[20005];
int h[10005],et=0;
inline void Add(int U,int V,int W){
    e[++et] = (ee){V,W,h[U]};
    h[U] = et;
}

int fi[10005][20],fv[10005][20],dep[10005];
bool vis[10005];
inline void dfs(int X,int FTHR){
    for(int i=h[X];i;i=e[i].nxt){
        if(vis[e[i].v]){
            continue;
        }
        vis[e[i].v]=1;
        fi[e[i].v][0]=X;
        fv[e[i].v][0]=std::min(fv[e[i].v][0],e[i].w);
        dep[e[i].v]=dep[X]+1;
        dfs(e[i].v,X);
    }
}

inline int lca(int X,int Y){
    dep[X]<dep[Y]?(X^=Y^=X^=Y):0;
    int ans=INF,dlt;
    if(X==Y){
        return 0;
    }
    for(dlt=15;dlt>=0;--dlt){
        if(dep[X]-(1<<dlt)>=dep[Y]){
            ans=std::min(ans,fv[X][dlt]);
            X=fi[X][dlt];
        }
    } 
    if(X==Y){
        return ans;
    }
    for(dlt=15;dlt>=0;--dlt){
        if(fi[X][dlt]!=fi[Y][dlt]){
            ans=std::min(ans,fv[X][dlt]);
            ans=std::min(ans,fv[Y][dlt]);
            X=fi[X][dlt],Y=fi[Y][dlt];
        }
    }
    ans=std::min(ans,fv[X][0]);
    ans=std::min(ans,fv[Y][0]);
    return ans;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&e0[i].u,&e0[i].v,&e0[i].w);
    }
    for(int i=1;i<=n;++i){
        FA[i]=i;
        fv[i][0]=INF;
    }
    std::sort(e0+1,e0+1+m);
    for(int i=1;i<=m;++i){
        if(fa(e0[i].v)!=fa(e0[i].u)){
            Add(e0[i].u,e0[i].v,e0[i].w);
            Add(e0[i].v,e0[i].u,e0[i].w);
            mrg(e0[i].u,e0[i].v);
        }
    }
    for(int i=1;i<=n;++i){
        if(FA[i]==i){
            fi[i][0]=0;
            fv[i][0]=0;
            vis[i]=1;
            dfs(i,0);
        }
    }
    scanf("%d",&q);
    for(int j=1;j<=15;++j){
        for(int i=1;i<=n;++i){
            fi[i][j]=fi[fi[i][j-1]][j-1];
            fv[i][j]=std::min(fv[i][j-1],fv[fi[i][j-1]][j-1]);
        }
    }
    int u,v;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&u,&v);
        if(fa(u)!=fa(v)){
            puts("-1");
            continue;
        }
        printf("%d\n",lca(u,v));
    }
}

int main(){
    init();
    return 0;
}