发布于

lp1494 国家集训队 小Z的袜子

令颜色为\(c_i\)为第\(i\)种颜色在给定区间内出现的次数。
则，题目所求为：
$$\frac{\sum_{i=1}^{n}c_{i}(c_{i}-1)}{(r-l)(r-l+1)}$$
展开可以得到：
$$\frac{\sum_{i=1}^{n}c_{i}^2-\sum_{i=1}^{n}c_{i}}{(r-l)(r-l+1)}$$
由性质可得：
$$\sum_{i=1}^{n}c_{i}=r-l+1$$
故而，我们需要求的仅有：
$$\sum_{i=1}^{n}c_{i}^2$$
对于这个式子的求法，我们很容易可以想到莫队。
我们考虑一个区间添加上一个数与删除一个数造成的影响。
令修改的颜色为\(x\)，则：
$$\Delta v=\sum_{i=1}^{n}c_{i}^2-c_{x}^{2}+(c_{x}±1)^2-\sum_{i=1}^{n}c_{i}^2$$
展开可得：
$$\Delta v=1±2c_{x}$$

下面考虑莫队。
莫队的原理大致是，将原数列分块，然后将询问以左端点在原数列中的块为第一关键字，右端点为第二关键词来排序。
虽然说它是一种优化后的暴力，但是，若令一次修改的复杂度是\(f_{n}\)，根据最小直线斯坦纳树的性质，可以证明这么做的复杂度是 \(O(f_{n} n \sqrt{m})\)，可以通过此题。
依据毒瘤lxl的说法，莫队最快的分块大小是\(n/\sqrt{m*2/3}\)
故而我们对原数列分块完以后，将询问排序。然后开始移动区间。
扫一遍即可。
另外就是一个小优化，排序的时候分奇偶排序，也就是说，奇数块右端点递增，偶数块右端点递减。
原理很简单，就是移过去再移回来，路上的点都扫了一遍。 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
int BLOCK;
int belong[50005];
struct Query{
	int l;
	int r;
	int id;
	int len;
	inline bool operator <(const Query &B)const{
		return (belong[l]^belong[B.l])?(belong[l]<belong[B.l]):((belong[l]&1)?r<B.r:r>B.r);
	}
}q[50005];
long long tot=0;
int cnt[50005];
inline void add(int X){
	tot+=(cnt[X]<<1|1);
	++cnt[X];
}
inline void del(int X){
	tot+=(1-(cnt[X]<<1));
	--cnt[X];
}
inline long long Gcd(long long A,long long B){
	return B?Gcd(B,A%B):A;
}
long long ans1[50005],ans2[50005];
int n,m,a[50005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=n/std::sqrt(m*2.0/3.0); 
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
		q[i].len=q[i].r-q[i].l+1;
		ans2[i]=1;
	}
	for(int i=1;i<=n;++i){
		belong[i]=(i-1)/BLOCK+1;
	}
	std::stable_sort(q+1,q+1+m);
	int l=q[1].l,r=q[1].l-1;
	long long nwgcd;
	for(int i=1;i<=m;++i){
		while(l<q[i].l){
			del(a[l]);
			++l;
		}
		while(l>q[i].l){
			--l;
			add(a[l]);
		}
		while(r>q[i].r){
			del(a[r]);
			--r;
		}
		while(r<q[i].r){
			++r;
			add(a[r]);
		}
		if(tot!=q[i].len){
			ans1[q[i].id]=tot-q[i].len,ans2[q[i].id]=1LL*(q[i].r-q[i].l)*q[i].len;
			nwgcd=Gcd(ans1[q[i].id],ans2[q[i].id]);
			ans1[q[i].id]/=nwgcd,ans2[q[i].id]/=nwgcd;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld/%lld\n",ans1[i],ans2[i]);
	}
}

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

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;
}
发布于

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

 

发布于

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

 

发布于

lp2324 SCOI2005 骑士精神

一道\(IDA*\)的入门题。
首先我们发现移动空格比移动马更容易。
然后考虑如何移动。爆搜马的位置是一种有效的做法。
但是直接爆搜很容易出现一个问题：搜索可能会在一些劣的情况下搜很久，或者搜进死胡同不出来。
这时候我们设计一个东西叫做估价函数\(g_S\)，如果当前局面的花费\(h_S\)加上估价函数大于花费上界\(f_S\)的话，这条选择支就是不优的。
然后我们可以枚举上界进行搜索。
由于随着上界的增长，花费的增长速度极快——每一层的花费都远大于上一层的花费。故而尽管上界具有单调性，但二分上界并不会更优。
（其实\(IDA*\)本质上就是玄学剪枝吧。）

#include<iostream>
#include<cstdio>

int nw[6][6];
const int mp[6][6]={
    {0,0,0,0,0,0},
    {0,1,1,1,1,1},
    {0,0,1,1,1,1},
    {0,0,0,-1,1,1},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0},
};
const int dx[8]={-2,-2,-1,-1,1,1,2,2};
const int dy[8]={1,-1,2,-2,2,-2,1,-1};
inline int val(){
    int rt=0;
    for(int i=1;i<=5;++i){
        for(int j=1;j<=5;++j){
            if(mp[i][j]!=nw[i][j]){
                ++rt;
            }
        } 
    }
    return rt;
}

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

inline void Swap(int &X,int &Y){
    X^=Y^=X^=Y;
}

inline bool srch(int dp,int X,int Y,int dm,int lst){
    int Nval=val();
    if(!Nval){
        return 1;
    }
    if(dp>dm){
        return 0;
    }
    for(int i=0;i<8;++i){
        if(i+lst==7){
            continue;
        }
        int NX=X+dx[i],NY=Y+dy[i];
        if(NX<1||NY<1||NX>5||NY>5){
            continue;
        } 
        Swap(nw[X][Y],nw[NX][NY]);
        Nval=val();
        if(Nval+dp<=dm+1){
            if(srch(dp+1,NX,NY,dm,i)){
                return 1;
            }
        }
        Swap(nw[X][Y],nw[NX][NY]);
    }
    return 0;
}

void init(){
    char ch[6];
    int SX,SY;
    for(int i=1;i<=5;++i){
        std::cin>>ch+1;
        for(int j=1;j<=5;++j){
            nw[i][j]=ch[j]-'0';
            if(!isdigit(ch[j])){
                nw[i][j]=-1;
                SX=i,SY=j;
            }
        }
    }
    if(!val()){
        puts("0");
        return;
    }
    for(int i=1;i<=15;++i){
        if(srch(1,SX,SY,i,-1)){
            printf("%d\n",i);
            return;
        }
    }
    puts("-1");
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

NOIP2018 旅行

题目大意：求一棵树的最小DFS序，和一张n条边的连通图删去任意一条边以后的最小DFS序。
话说这一题和我出过的某一道题非常神似，都是在求一些特定的DFS序。就连对DFS的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面，然后用了十分钟写掉了。
第一个子问题很简单，贪心地DFS即可，这是因为字典序的特性，使得，如果每一次拓展都选择的是当前最小的，那么总是不会更劣。
对于第二个子问题，它不再是求纯粹的DFS序了，但是看到\(n=5000\)的数据范围，可以想到暴力枚举删边，这就转化为第一个问题。
如果依然是一边DFS一边删边的话，最坏情况下可能会达到\(O(n^2*logn)\)的复杂度，尽管有32Gi7，也很难通过一些大数据。
我们考虑预处理。首先将读入的边排序，然后插入边表。这样遍历的顺序就是从小到大了。
注意对边进行预排序时，由于插入边表是倒序插入，所以应当让末端点从大到小排序。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
int n,m;
struct ee{
	int v;
	int nxt;
}e[10005];
int h[5005],et=0;
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
struct e0{
	int u;
	int v;
	bool operator<(const e0 &B)const{
		return (u==B.u)?(v>B.v):(u<B.u);
	}
}e0[10005],e00[5005];
int Du,Dv,ans[5005],Ans[5005],at=0;
bool vis[5005];
inline void dfs(int X){
	vis[X]=1,ans[++at]=X;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]||(e[i].v==Du&&X==Dv)||(e[i].v==Dv&&X==Du)){
			continue;
		}
		dfs(e[i].v);
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&e0[i].u,&e0[i].v);
		e00[i].u=e0[i].u,e00[i].v=e0[i].v;
		e0[i+m].u=e0[i].v,e0[i+m].v=e0[i].u;
	}
	std::sort(e0+1,e0+(m<<1|1));
	for(int i=1;i<=(m<<1);++i){
		add(e0[i].u,e0[i].v);
	}
	if(m==n-1){
		Du=0,Dv=0;
		dfs(1);
		for(int i=1;i<=n;++i){
			printf("%d ",ans[i]);
		}
		return;
	}else if(m==n){
		for(int i=1;i<=n;++i){
			Ans[i]=0x3f3f3f3f;
		}
		for(int i=1;i<=m;++i){
			Du=e00[i].u,Dv=e00[i].v;
			at=0;
			for(int j=1;j<=n;++j){
				vis[j]=0;
			}
			dfs(1);
			if(at==n){
				for(int j=1;j<=n;++j){
					if(ans[j]==Ans[j]){
						continue;
					}else if(ans[j]>Ans[j]){
						break;
					}else{
						for(int k=1;k<=n;++k){
							Ans[k]=ans[k];
						}
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]);
		}
	}
}
int main(){
	init();
	return 0;
}

 

发布于

NOIP2018 赛道修建

一道树形DP裸题。
因为部分分给得很足，所以我在考场上先打了一堆部分分，建了5个命名空间。
然后在打二叉树的部分分的时候想到了正解。（虽然可能二分写挂了）
题目大意：给定一棵带权树，将它的一部分拆成\(m\)条链，使得权值最短的链的权值最大。
最小的求最大，当然满足无后效性，所以我们考虑二分答案。
然后我们考虑检验。首先，很容易可以发现答案具有无后效性。换句话说，每个子树在计算出它对答案的贡献之后，就只需要计算出它对父节点的贡献。
这是因为，每一个父节点，它能使用的仅有子树的一条链，而不是整个子树的信息。
故而，我们只需要「可以提供给父节点的那条链」的值更新上去即可。我们用\(f_{x}\)表达这个上传的值。
并且，对于每棵子树是可以贪心地处理的——如果一棵子树中的一条链可以和另一条链组成一条合法的链，那就没必要把它上传了。
这是因为，如果不上传，一定可以对答案产生1的贡献；如果上传了，仅仅是有可能对答案产生1的贡献。
那么我们对每个子树分别考虑。这就转化为了一个新的问题：
「对于一个长度为\(n\)的序列，取出其中尽可能多的数对或数，使得数对的和或数的值大于给定值，并且在有遗留数的情况下使得遗留的数的值最大。」
这个问题要怎么做呢？将它们从小到大排序，那么对于大于给定值的数，单独选取是更优的。
然后处理剩下来的数。用双指针做。
如果右指针的数可以与左指针指的数组成合法数对就把右指针推入栈中，直到没有合法的右指针，就考虑栈中是否为空。
如果不为空就说明存在一个可以和左指针匹配的数，那么就将答案加一，否则左指针就找不到数和它匹配了，那么就用它来更新\(f{x}\)左指针往右推。一直到序列为空。
然后，对于剩下的数，它们一定都可以组成合法数对——这是因为所有被推入栈中的数，都可以和一个比栈中最小数还要小的数组成合法数对。
那么，我们考虑剩下的数的数量的奇偶性。如果是奇数个，那么就计算答案之后用最大值来更新\(f_{x}\)。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
struct ee{
	int v;
	int w;
	int nxt;
}e[50005];
int h[50005],et=0;
int n,m;
inline void add(int u,int v,int w){
	e[++et]=(ee){v,w,h[u]};
	h[u]=et;
}
int MN,rt=0,f[50005],nw;
int st[50005],tp=0,st2[50005],tp2=0;
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
	}
	tp=0,tp2=0;
	for(int i=h[X];i;i=e[i].nxt){
		st[++tp]=f[e[i].v]+e[i].w;
	}
	std::sort(st+1,st+1+tp);
	while(tp&&st[tp]>=MN){
		--tp;
		++rt;
	}
	for(int i=1;i<=tp;++i){
		while(i<tp&&st[i]+st[tp]>=MN){
			st2[++tp2]=st[tp];
			--tp;
		}
		if(tp2){
			--tp2;
			++rt;
		}else{
			f[X]=st[i];
		}
	} 
	if(tp2&1){
		f[X]=st2[1];
	}
	rt+=(tp2>>1);
} 
inline bool chck(int X){
	std::memset(f,0,sizeof(f));
	MN=X;
	rt=0;
	dfs(1);
	if(rt>=m){
		return 1;
	}else{
		return 0;
	}
}
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		if(u>v){
			u^=v^=u^=v;
		}
		add(u,v,w);
	}
	int l=0,r=0x3f3f3f3f,mid,ans=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(chck(mid)){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

 

发布于

NOIP2018 货币系统

一道看起来像数论题的完全背包问题。
幸好我前一天没有仔细看数论，使得我想的是写暴力…要不然我可能真的会推一个小时的\(EXGCD\)或\(CRT\)或者高斯消元之类的东西。
总之是小凯的疑惑迷惑了我，以为是一道数论题，所以到最后我都以为自己写的是暴力。
结果发现其实是正解思路的，已经写到了正解的倒数第二步，随便一优化就通过了。
但是始终以为是打暴力。
果然还是太菜了。
题意简述：你有\(n\)个正整数，要求，确定一个最小的\(m\)，使得用\(m\)种正整数数能够表示的数集与题目给出数能够表示的数集的完全一致。
首先我们证明一个定理：答案的\(m\)个数一定是原有数的子集。
下面我们分两类考虑这个问题。
如果新的数可以被原有数表示，那么显然它是没有意义的。
如果新的数不能被原有数表示，那么显然它是不合法的。
那么我们只需要考虑删除哪些数即可。
我们发现，一个数需要删除，当且仅当它可以被其他数表达出来。
反证法：如果它不可被其他数表示的话，那么删除它以后它就无法表示出来了。
并且，我们可以发现，这个问题满足最优子结构：如果一个数可以被当前的系统表达出来，那么删除当前系统中任意一些可以被表达出来的数，都不会导致这个数不能被表达出来。
故而，先删哪个其实都不影响答案的正确性。
因此我们可以从小往大删（可能可以节省时间）
暴力地考虑，我们需要枚举值域内每一个已经可以被表达出来的数，然后将这个数加上当前数的任意倍（值域范围内）
这么做最坏可能是\(O(T*n*a^2)\)的。
考虑优化。用欧拉筛的思想，对于每一个数，我们只需要加上当前数的一倍即可。
因为，如果加上当前数的两倍的话，就会在之后再一次访问到这个数，这时候就产生了访问次数上的浪费。
这样做是\(O(T*n*a)\)。
那就做完了。

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

int n,a[105];
bool usf[25005];
void init(){
	std::memset(usf,0,sizeof(usf));
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	if(n==1){
		puts("1");
		return;
	}
	std::sort(a+1,a+1+n);
	int cnt=n;
	usf[0]=1;
	for(int i=1;i*a[1]<=25000;++i){
		usf[i*a[1]]=1;
	}
	for(int i=2;i<=n;++i){
		if(usf[a[i]]){
			a[i]=0;
			--cnt;
		}else{
			for(int j=0;j+a[i]<=25000;++j){
				if(!usf[j]){
					continue;
				}else{
					usf[j+a[i]]=1;
				}
			}
		}
	}
	printf("%d\n",cnt);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

 

发布于

NOIP2018 铺设道路

题意简述：
有一个序列，你可以一次将一个连续的段-1，但是不能让一个段变成0，求最小变成全零的操作次数。
方法有很多，个人的做法是差分以后把所有正值加起来。
没有细节，NOIP2013原题，完全就是为了送分。
感谢良心出题人。

#include<iostream>
#include<cstdio>
int n,a[100010],da[100010];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=n;++i){
		da[i]=a[i]-a[i-1];
	}
	int sm=0;
	for(int i=1;i<=n;++i){
		da[i]=std::max(da[i],0);
		sm+=da[i];
	}
	printf("%d\n",sm);
}
int main(){
	init();
	return 0;
}