lp3902 递增

最长上升子序列裸题。
dp+二分即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=100005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
int n,a[N],f[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1]=a[1];
	int pos,ans=1;
	for(int i=2;i<=n;++i){
		pos=lower_bound(f+1,f+1+n,a[i])-f-1;
		ans=Max(ans,pos+1);
		f[pos+1]=Min(f[pos+1],a[i]);
	}
	printf("%d\n",n-ans);
}

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

lp4027 NOI2007 货币兑换

我们观察到,整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得:
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说,购买的A和B券的数量分别是:
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么,我们从j转移到i的方程是:
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设:
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$
那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。
通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意:要判一下分母不能等于极小数,否则可能会挂。

略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得: $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说,购买的A和B券的数量分别是: $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么,我们从j转移到i的方程是: $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设: $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$ 那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。 通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意:要判一下分母不能等于极小数,否则可能会挂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
	double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。 
inline double cmp(const data &A,const data &B){
	return A.a*B.b>B.a*A.b; 
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
//	printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
	return a[P].x*A+a[P].y*B; 
}
inline double slp(int A,int B){
	if(fabs(a[A].x-a[B].x)<eps){
		return INF;
	}
	return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
	int mid=(l+r)>>1;
	int I=l,J=mid+1,tp=l;
	while(I<=mid&&J<=r){
		if(a[I].x<a[J].x){
			b[tp++]=a[I++];
		}else{
			b[tp++]=a[J++];
		}
	}
	while(I<=mid){
		b[tp++]=a[I++];
	}
	while(J<=r){
		b[tp++]=a[J++];
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
}
inline void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],f[l-1]);
		a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
		a[l].x=(double)a[l].r*a[l].y;
		return;
	}
	int mid=(l+r)>>1;
	int I=l,J=mid+1;
	for(int i=l;i<=r;++i){
		if(a[i].id<=mid){
			b[I++]=a[i];
		}else{
			b[J++]=a[i];
		}
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
	cdq(l,mid);
	tp=0;
	for(int i=l;i<=mid;++i){
		while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
			--tp;
		}
		st[++tp]=i;
	}
//	printf("[%d,%d]\n",l,r);
//	for(int i=1;i<=tp;++i){
//		printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
//	}
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
			--tp;
		}
		f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
//		printf("%d %lf\n",i,a[i].ans); 
	}
	cdq(mid+1,r);
	mg(l,r);
}
void init(){
	scanf("%d%lf",&n,&f[0]);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	cdq(1,n);
//	for(int i=1;i<=n;++i){
//		printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
//	}
	printf("%.3lf\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp2501 HAOI2006 数字序列

我们分别考虑一二问。
对于第一问,我们思考一个子序列是合法的「不用修改」的子序列的充要条件。
容易想到的,这个条件是:
$$ \forall i,j\in S, i=j-i$$
自然语言化地说,就是,对于这个不用修改的子序列中的任意两个元素,它们的值的差距至少要大于它们间的元素个数,这样才能放得下它们中间的元素。
移项,我们得到:
$$a_j-j>=a_i-i$$
所以,我们令\(b_i=a_i-i\),那么第一问中不用修改的个数就是\(b\)的最长不下降子序列长度。
对于第二问,首先,它可以被转化为「最小修改代价求\(b\)单调不减」。
我们有一个结论:相邻两关键点\(i,j\)间一定可以找到一条分界线,使得线左端的所有点变化成\(b_i\),右端所有点变化成\(b_j\)会最优。
这是如何证明的呢?
首先,我们知道,\(i,j\)之间的任意一个点,它的值必然要小于\(b_i\)或者大于\(b_j\),否则选取这个点只会让答案更优。
然后,我们尝试进行反证。如果有一个点修改以后位于中间,并且它可以被修改到某一边,那么显然修改到某一边之后答案会更小。
如果将分界线定在某处,会使得某些点与它们的最优处于的边不相同,那么考虑这些点与分界点之间的其他点的数量。
如果其他点的数量小于这些点,那么不妨把这些点修改后的位置换到另一边,这样答案就变小了点数差*上下两边距离。
否则,不如不修改。
所以我们证明了这个结论。
然后是关于时间复杂度的。可以证明,在序列随机的情况下,最长不下降子序列的期望长度是logn级别的。(我不会证,也找不到文章。求大佬教教我)

注意:要提前把\(b_0\)设成\(-INF\),并在末尾插入一个\(INF\)的点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=35005;
const int INF=0x3f3f3f3f;
inline ll Abs(ll X){
	return X>=0?X:-X;
}
inline ll Min(ll A,ll B){
	return A<B?A:B;
}
int n,a[N],b[N],nm[N];
ll f[N],sm1[N],sm2[N];
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i]-i;
	}
	int cnt=0,nw;
	b[0]=-INF;f[0]=-INF;
	b[++n]=INF;
	for(int i=1;i<=n;++i){
		if(b[i]>=f[cnt]){
			f[++cnt]=b[i];
			nm[i]=cnt;
		}else{
			nw=upper_bound(f+1,f+cnt,b[i])-f;
			f[nw]=b[i];
			nm[i]=nw;
		}
	}
	printf("%d\n",n-cnt);
	for(int i=n;i>=0;--i){
		add(nm[i],i);
		f[i]=INF;
	}
	f[0]=0;
	int v;
	for(int i=1;i<=n;++i){
		for(int j=h[nm[i]-1];j;j=e[j].nxt){
			v=e[j].v;
			if(v>i||b[v]>b[i]){
				continue;
			}
			sm1[v]=0;
			for(int k=v+1;k<=i;++k){
				sm1[k]=sm1[k-1]+Abs(b[k]-b[v]);
			}
			sm2[i-1]=0;
			for(int k=i-2;k>=v;--k){
				sm2[k]=sm2[k+1]+Abs(b[k+1]-b[i]);
			}
			for(int k=v;k<i;++k){
				f[i]=Min(f[i],f[v]+sm1[k]+sm2[k]);
			}
		}
	}
	printf("%lld\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp2515 HAOI2010 软件安装

简单的tarjan缩点+树形背包DP。
考虑N<=100,M<=500,只需要设f[i][j]表示第i个点,已用j的容量。
然后直接DP即可。
特别地,由于如果某一个点的子树中的点被选中了,这个点也要被选中,所以我们在计算每个点的时候,一定要将这个点加进去。
然后仔细看看这道题,发现它不保证没有环!
这下完蛋了,咋做啊?
考虑到这个环要么都选,要么都不选,所以可以先用tarjan找环,把找环后的点拿来dfs。
然后我们考虑一个性质:如果存在环,那么这个环缩成的点一定是某一棵树的树根。
所以我们不妨计算每一个点的入度,然后将入度为0的点连向虚点0。这样只需要一次DP。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

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 ee{
	int v;
	int nxt;
}e[505];
int h[505],g[505],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
int n,m,f[505][505],w[505],v[505],ww[505],val[505],d[505],in[505];
int vis[505],clr[505],dfn[505],lw[505],cnt=0,ccnt=0,st[505],tp=0;
inline void dfs0(int X){
	vis[X]=1,dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	for(int i=g[X];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);lw[X]=Min(lw[X],lw[e[i].v]);
		}else if(vis[e[i].v]){
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
	if(dfn[X]==lw[X]){
		++ccnt;
		while(st[tp+1]!=X){
			clr[st[tp]]=ccnt;
			val[ccnt]+=v[st[tp]],ww[ccnt]+=w[st[tp]];
			vis[st[tp]]=0;
			--tp;
		}
	}
}
inline void dfs1(int X){
	for(int i=ww[X];i<=m;++i){
		f[X][i]=val[X];
	}
	for(int i=h[X];i;i=e[i].nxt){
		dfs1(e[i].v);
		for(int j=m-ww[X];j>=0;--j){//j表示之前的子树的重量和。 
			for(int k=0;k<=j;++k){//k表示这棵子树的重量和。 
				f[X][j+ww[X]]=Max(f[X][j+ww[X]],f[e[i].v][k]+f[X][j-k+ww[X]]); 
			}
		}
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&v[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
		if(d[i]){
			add(g,d[i],i);
		}
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			dfs0(i);
		}
	}
	for(int i=1;i<=n;++i){
		if(clr[d[i]]!=clr[i]){
			add(h,clr[d[i]],clr[i]);
			++in[clr[i]];
		}
	}
	for(int i=1;i<=ccnt;++i){
		if(!in[i]){
			add(h,0,i);
		}
	}
	dfs1(0);
	printf("%d\n",f[0][m]);
}
int main(){
	init();
	return 0;
}

lp3233 HNOI2014 世界树

让我们来分析这道题。
我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优。
由此我们继续推导,可以发现,假如只有两个关键点的话,它们之间的链上一定可以找到一个分界线,使得这条分界线的一段——以及所有与链上这一端相邻的节点——放在一个关键点上,并把剩下的放在另一个关键点上。这样是最优的。
然后我们考虑有三个关键点的情况。如果有三个关键点的话,问题似乎就复杂了很多,这是因为这条分界线必须是基于三个节点共同决定的。
我们换一个思路考虑。求出三个关键点两两的LCA。那么,这一分界线就必然可以在这六个点(最多六个)两两之间的链上找到。
存在一种叫做「虚树」的数据结构。这个数据结构本质上就是将所有关键点以及关键点两两之间的LCA建成一个数。
我们如此考虑,如果有一个点是关键点,那么它向下能够管辖的点的数量就是它的子树大小减去它的所有子节点能管辖的点数之和。
它向上能够管辖的点的数量则相对比较复杂。
我们考虑每一条边,假设我们已经预处理出了虚树上每一个点相邻最近的关键点,那么,如果这条边两端的点相邻最近的关键点是相同的,那么这条边(以及和这条边相邻的所有点)都划归到那个关键点下管辖。
如果这条边两段的点相邻最近的关键点不同,则需要使用倍增来确定这条边要如何被划分成两个部分。

接下来要考虑如何确定虚树上每一个点相邻最近的关键点。
我们不妨这样考虑:一个点相邻最近的关键点如果在它的下方,那么这可以通过树形DP求得;如果在它的上方或者其他子树内呢?
显然,如果这个点的相邻最近关键点在它的上方或者和它不在同一子树内,那么它的父亲的最近关键点一定与这个点的最近关键点相同。
于是,我们不妨从上而下DP,求得这个点在上方或者不在同一子树的最近关键点。

现在我们来梳理一下这一题的思路。
首先,我们进行预处理,处理出每个点的深度和dfn。
然后,我们进行两次树形DP,求出每个点的最近关键点。
第三,我们预处理出所有「末端节点」——也就是所有「是一个虚树上节点的直接儿子且子树内没有关键点的原树上的点」。这些点的贡献可以直接统计到它们父亲的最近关键点。
最后,我们依次考虑剩下的虚树边上的点。如果两段的最近关键点相同,那么就统计到那个最近关键点。否则就进行倍增寻找答案。

顺便讲一下如何建虚树。
我们将所有关键点按照dfs序排序,然后建一个栈,代表当前正在向下延长的链。
如果当前的点与栈顶的LCA的深度小等于次栈顶,那么就说明当前点不在栈顶的子树里,也就意味着栈顶处于当前应该维护的链外。
于是,我们需要就可以将新的这个点加入虚树和栈中。
否则,就说明原来的栈顶需要被弹出,那么就处理完它应该连的边然后将它弹出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
#define Fv2(i,X) for(int i=g[X];i;i=e[i].nxt)
using namespace std;

typedef pair<int,int> pii;
const int N=300005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int nxt;
}e[1200005];
int h[N],g[N],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}

int dfn[N],cnt=0,sz[N],dep[N],fa[N][20];
inline void dfs0(int X){
	dfn[X]=++cnt;sz[X]=1;
	Fv(i,X){
		if(e[i].v==fa[X][0]){
			continue;
		}
		fa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
int usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];
pii nr[N];
inline void dfs1(int X){
	nr[X]=(usd[X]?pii(0,X):pii(INF,0));
	Fv2(i,X){
		dfs1(e[i].v);
		nr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));
	}
}
inline void dfs2(int X,int D,int P){
	if(pii(D,P)<nr[X]){
		nr[X]=pii(D,P);
	}else{
		D=nr[X].first,P=nr[X].second;	
	}
	Fv2(i,X){
		dfs2(e[i].v,D+dep[e[i].v]-dep[X],P);
	}
}
//子节点中所有子树中有虚树上节点的点都是不可以选取的。
//我们不妨逆向考虑,枚举每一个虚树上的子节点,然后从那个节点开始倍增,一直倍增到这棵树的子节点,然后把这些子节点的子树挖掉。 
inline void dfs3(int X){
	ans[hr[X]=nr[X].second]+=sz[X];
	Fv2(i,X){
		int nw=e[i].v;
		for(int j=18;j>=0;--j){
			if(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){
				nw=fa[nw][j];
			}
		}
		ans[hr[X]]-=sz[up[e[i].v]=nw];
		dfs3(e[i].v);
	}
}
//现在剩下的末端节点就只有虚树上的节点了。 
//如果子节点的dfs序大于当前节点,那么分割点就偏上;否则偏下。 
inline void dfs4(int X){
	Fv2(i,X){
		if(hr[e[i].v]==hr[X]){
			ans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];
		}else{
			int len=dep[hr[e[i].v]]+dep[X]-nr[X].first;
			len=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));
//			这里比较的是编号!!! 
			int nw=e[i].v;
			for(int j=18;j>=0;--j){
				if(dep[fa[nw][j]]>=len){
					nw=fa[nw][j];
				}
			}
			ans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];
			ans[hr[X]]+=sz[up[e[i].v]]-sz[nw];
		}
		dfs4(e[i].v);
	}
}
inline void dfs5(int X){
	up[X]=hr[X]=0;
	Fv2(i,X){
		dfs5(e[i].v);
	}
	g[X]=0;
}
inline bool cmp(int A,int B){
	return dfn[A]<dfn[B];
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		swap(X,Y);
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int st[N],tp=0;
void init(){
	int n,Q;
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(h,u,v);
		add(h,v,u);
	}
	dep[1]=1;
	dfs0(1);
	for(int j=1;j<=18;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	scanf("%d",&Q);
	int m,X,Y;
	while(Q--){
		scanf("%d",&m);
		for(int i=1;i<=m;++i){
			scanf("%d",&pt[i]);
			ppt[i]=pt[i],usd[pt[i]]=1;
		}
		sort(pt+1,pt+1+m,cmp);
		st[tp=1]=pt[1];
		for(int i=2;i<=m;++i){
			X=pt[i],Y=lca(X,st[tp]);
			while(tp>1&&dep[Y]<=dep[st[tp-1]]){
				add(g,st[tp-1],st[tp]);
				--tp;
			}
			if(Y!=st[tp]){
				add(g,Y,st[tp]);st[tp]=Y;
			}
			st[++tp]=X;
		}
		while(tp>1){
			add(g,st[tp-1],st[tp]);
			--tp;
		}
		dfs1(st[1]);
		dfs2(st[1],nr[st[1]].first,nr[st[1]].second);
		dfs3(st[1]);
		dfs4(st[1]);
		ans[hr[st[1]]]+=sz[1]-sz[st[1]];
		for(int i=1;i<=m;++i){
			printf("%d ",ans[ppt[i]]);
		}
		puts("");
		dfs5(st[1]);
		for(int i=1;i<=m;++i){
			ans[pt[i]]=0,usd[pt[i]]=0;
		}
	}
}
int main(){
	init();
	return 0;
}

lp2622 关灯问题II

显然,对于某个状态,按下某个按钮之后,一定会得到另一个状态。
而灯的状态最大只有\(2^10\)。
故而考虑建一张图,2^n个点,m条边,那么答案就是从0到2^n-1的最短距离。
直接BFS即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int INF=0x3f3f3f3f;
int n,m;
queue<int> q;
int dep[1025],vis[1025];
int a[15],b[105],c[105];
inline int bfs(){
	for(int i=0;i<(1<<n);++i){
		dep[i]=INF;
	}
	q.push(0);
	dep[0]=0;
	int p,v;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=1;i<=m;++i){
			v=(p|b[i])&c[i];
			if(dep[v]>dep[p]+1){
				dep[v]=dep[p]+1;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return (dep[(1<<n)-1]^INF)?dep[(1<<n)-1]:-1;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		b[i]=c[i]=0;
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<n;++j){
			scanf("%d",&a[j]);
			if(a[j]==1){
				b[i]|=(1<<j);
				c[i]|=(1<<j);
			}
			if(a[j]==0){
				c[i]|=(1<<j);
			}
		}
	}
	printf("%d\n",bfs());
}
int main(){
	init();
	return 0;
}

lp2519 HAOI2011 problem a

我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1,右端点是r=n-b。
仔细观察,会发现,这个可能的区间,就是和这个考生同分(包括这个考生)的考生的数量。
那么显然,如果这个可能的区间不存在,那么这个考生在撒谎;如果在同一个区间里面有超过区间长度的考生数,那么也是不合法的。
我们仔细想想,还有什么情况是冲突的。我们发现,说真话的考生所在的区间是不能重合的。
于是问题就转化为一个类似于背包的问题。我们可以将这些区间排序,那么不妨设f[i]表示第i个区间为真的情况下的最大数量。
首先,如果右端点递减,我们可以考虑用一个单调队列来维护这个东西。
在这种情况下,可以维护一个r值递增,f值递增的单调队列。
每一次把新的右端点插入到单调队列的右端,然后如果右端的f值比当前的f值小,那么就把右端的f值给干掉。
然而,实际上,右端点是无单调性的,所以可能存在这样一种情况:新插入的点的r值更小,而f值也更小。这时候就没有办法判断是否要删掉单调队列末端的点了。
想象一下在这种情况下要怎么做。在这种情况下,我们可以将新插入的点插到r值刚好比它小的那个点前面,然后把所有r值比它大而f值比它小的点都删掉。
要如何维护呢?直观地想是使用平衡树,但是我们可以使用map来完成这个操作。
然而,这样涉及到复杂的iterator操作。我并不是很会。
我们考虑另外一种想法。我们令f[i]表示以i为当前访问过的最右端点的情况下的最优值。
那么,我们可以记录每一个右端点的所有左端点,然后枚举这些左端点并转移,就可以得出答案。
注意:一个区间的权值要与它的长度取min!
注意:这样求出来的答案是真的数量,要用n减去它!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
typedef pair<int,int> pii;
const int N=100005;
int n;
int f[N];
vector<int> lst[N];
map<pii,int> mp;
void init(){
	scanf("%d",&n);
	int x,y,l,r;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		l=x+1,r=n-y;
		if(l>r){
			continue;
		}
		if(++mp[(pii){l,r}]==1){
			lst[r].push_back(l);
		}
	}
	for(int i=1;i<=n;++i){
		f[i]=f[i-1];
		for(int j=0;j<lst[i].size();++j){
			f[i]=Max(f[i],f[lst[i][j]-1]+Min(i-lst[i][j]+1,mp[(pii){lst[i][j],i}]));
		}
	}
	printf("%d\n",n-f[n]);
}
int main(){
	init();
	return 0;
}

lp4582 FJOI2014 树的重心

两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小,那么我们发现,一棵子树有且仅有它的大小是对答案有影响的。所以我们可以预处理出每棵子树的不同大小的联通结构数,然后枚举子树大小瞎统计一下。 那么想想要怎么预处理。我们令\(f_{i,j}\)表示以\(i\)为根节点的子树中选取\(j\)个节点的联通子树的个数,\(g_{i,j}\)表示当前子树前\(i\)个儿子选取\(j\)个的联通子树的个数。 那么,根据定义我们有: $$g_{nw,j}=\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$ $$f_{X,i}=g_{sum\_of\_sons,i-1}$$ 然后树形DP即可。 仔细想想,如果有两个重心,那么把两个重心的连边断开,两边的答案的统计是互不干扰的。 故而我们可以将原树分成两棵树统计答案,再把答案相乘。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(A,X) for(int A=h[X];A;A=e[A].nxt)

const int MOD=10007;
const int INF=0x3f3f3f3f;
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 ee{
	int v;
	int nxt;
}e[404];
int h[205],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}
int sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;
inline void dfs0(int X,int FA){
	sz[X]=1;mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],totsz-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
		rt2=0;
	}else if(mx[X]==mx[rt]){
		rt2=X;
	}
}
int f[205][205],g[205][205];
inline void dfs1(int X,int FA){
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs1(e[i].v,X);
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			g[i][j]=0;
		}
	}
	f[X][1]=f[X][0]=g[0][0]=sz[X]=1;
	int nw=1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		sz[X]+=sz[e[i].v];
		for(int j=0;j<=sz[X];++j){
			for(int k=0;k<=j;++k){
				g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;
			}
		}
		++nw;
	}
	--nw;
	for(int i=1;i<=sz[X];++i){
		f[X][i]=g[nw][i-1];
	}
}
int ans=0;
inline void calc1(){
	ans=1;
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,0);
	for(int i=2;i<=n;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=n;++k){
				g[j][k]=0;
			}
		}
		g[0][0]=1;int nw=1;sz[rt]=1;
		Fv(E,rt){
			sz[rt]+=sz[e[E].v];
			for(int j=0;j<=Min(i-1,sz[rt]);++j){
				for(int k=0;k<=j;++k){
					if(2*k>=i){
						break;
					}
					g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;
				}
			}
			++nw;
		}
		--nw;
		ans=(ans+g[nw][i-1])%MOD;
	}
}
inline void calc2(){
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,rt2);dfs1(rt2,rt);
	ans=0;
	for(int i=1;i<=n/2;++i){
		ans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	et=rt=rt2=0;
	for(int i=1;i<=n;++i){
		h[i]=sz[i]=0;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	totsz=n;
	mx[0]=INF;
	dfs0(1,0);
	if(!rt2){
		calc1();
	}else{
		calc2();
	}
	printf("Case %d: %d\n",Tid,ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		++Tid;
		init();
	}
	return 0;
}

lp4630 APIO2018 Duathlon 铁人两项

圆方树是一种在仙人掌图上常用的数据结构,但是这并不意味着圆方树只在仙人掌图上有用。事实上,在任何一张图上,我们都可以用相似的方法来构造一棵圆方树。
对于一张图,我们预处理出它的所有点双,然后对每一个点双建一个方点,其他处理方法和仙人掌上圆方树几乎相同。
这里的点双要如何预处理呢?我们考虑一个性质:当我们预处理出一张图的DFS树后,任何一条边属于且仅属于一个点双。
那么,我们就可以尝试找到一个点双中深度最浅的节点,然后由它构造出这个方点。
我们发现,当我们搜索完一个节点的子树后,如果子节点中的某一个节点的lw是这个节点,那么这个节点就是它所在的点双中深度最浅的节点。
这是因为,如果一个节点的lw节点是它的父节点,那么它和它的子树就没有任何返祖边能够到达比当前节点更浅的节点,也就说明如果当前节点在点双内,那么它一定是点双内最浅的节点。
有没有可能当前节点不在点双内呢?这是不可能的。如果有返祖边连向当前节点,那么当前节点显然不会成为割点;如果没有,那么当前节点所属的点双就一定只有两个点。

现在把目光投到这道题。
首先考虑点双的基本性质。我们发现,对于至少有三个点的点双,任取三个点,它们总是一对满足题意的三元组。
这是由于点双的定义,点双里没有割点,自然总是可以找到两点间的两条不相交的简单路径。
拓展这个结论,我们发现,如果一条简单路径经过一个点双,那么显然无论固定哪个点,这条路径都始终是一条简单路径。
故而,对于选定的起点和终点,我们可以分两类讨论。
倘若它们位于同一个点双,那么显然它们之间的满足题意的三元组个数恰好是这个点双的点数-2
对于不属于同一个点双的情况,它们之间有可能经过其他的点双,也有可能不经过。每经过一个点双,它们之间的满足题意的三元组个数就会加上这个点双的点的个数。
同时,答案还要加上起点和终点各自处在的点双的点数个数各自-1。
这要怎么统计呢?我们可以让每个方点的权值为点双中的点的数量,每个圆点的权值为-1,然后枚举点对统计路径和即可。
仔细一想觉得有点不对劲儿:这样的复杂度岂不是要n^2logn级别?妥妥地T啊。
正难则反,我们可以统计每个点对答案的贡献,也就是经过它的路径数乘上它本身的权值。而前者可以通过一个普通的树形DP求得。
这就做完了。

注意:
要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。

#include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

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

struct ee{
	int v;
	int nxt;
}e[1200005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}

int n,m;
int dfn[100005],lw[100005],cnt=0,nm=0;
int st[100005],tp=0;
int val[200005],nwsz;
long long ans=0;
inline void dfs(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	++nwsz;
//	要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。 
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
//				注意这里应当判定的是lw(v)=dfn(u) 
				val[++nm]=1;
				for(int j=0;j!=e[i].v;--tp){
					++val[nm];
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}

int vis[200005],sz[200005];

inline void dfs2(int X){
	vis[X]=1;
	sz[X]=(X<=n);
	Fv(h,i,X){
		if(!vis[e[i].v]){
			dfs2(e[i].v);
			ans+=2ll*val[X]*sz[X]*sz[e[i].v];
			sz[X]+=sz[e[i].v];
		}
	}
	ans+=2ll*val[X]*sz[X]*(nwsz-sz[X]);
}

void init(){
	scanf("%d%d",&n,&m);
	nm=n;
	for(int i=1;i<=n;++i){
		val[i]=-1;
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			nwsz=0;
			dfs(i);
			dfs2(i);
			--tp;
		}
	}
	printf("%lld\n",ans);
}

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

lp3648 APIO2014 序列分割

首先证明序列分割的次序和最后的答案毫无关系。
这可以用乘法的基本性质证明。例如分成三段,我们有:
$$a(b+c)+bc=b(a+c)+ac$$

我们可以进行DP。
我们记\(f_{i,k}\)表示当前访问到第\(i\)个点,使用了\(k\)次切割的答案。
那么根据题目中贡献的定义,我们有:
$$f_{i,k}=max_{j=k}^{i-1}{f_{j,k-1}+sm_{j}(sm_{i}-sm_{j})}$$ 令\(k\le j_1(sm_i-sm_{j_1})\le f_{j_2,k-1}+sm_{j_2}(sm_i-sm_{j_2})\)$ 展开,移项,合并。 $$f_{j_1,k-1}+sm_{j_1}sm_i-sm_{j_1}^2\le f_{j_2,k-1}+sm_{j_2}sm_i-sm_{j_2}^2$$ $$f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2\le sm_{j_2}sm_i-sm_{j_1}*sm_i$$
$$\frac{f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2}{sm_{j_2}-sm_{j_1}}\le sm_i$$
这个式子显然是可以斜率优化的。
这样做的时空复杂度是\(O(nk)\)的。
考虑到这一题的空间限制比较紧张,我们可以用滚动数组把\(k\)这一维压掉。

#include<iostream>
#include<cstdio>

int q[100005];
long long f[100005][2],sm[100005];
int ans[100005][205],n,K;
inline double slope(int j1,int j2,int k){
	return (sm[j1]^sm[j2])?(double)(f[j1][(k&1)^1]-f[j2][(k&1)^1]+sm[j2]*sm[j2]-sm[j1]*sm[j1])/(double)(sm[j2]-sm[j1]):-1E18;
} 
void init(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;++i){
		scanf("%lld",&sm[i]);
		sm[i]+=sm[i-1];
	}
	for(int i=1;i<=K;++i){
		int l,r;
		l=r=1;
		for(int j=1;j<=n;++j){
			while(l<r&&slope(q[l],q[l+1],i)<=sm[j]){
				++l;
			}
			f[j][i&1]=f[q[l]][(i&1)^1]+sm[q[l]]*(sm[j]-sm[q[l]]);
			ans[j][i]=q[l];
			while(l<r&&slope(q[r-1],q[r],i)>slope(q[r],j,i)){
				--r;
			}
			q[++r]=j;
		}
	}
	int nw=n;
	printf("%lld\n",f[n][K&1]);
	for(int i=K;i>=1;--i){
		nw=ans[nw][i];
		printf("%d ",nw);
	}
}

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

lp3195 HNOI2008 玩具装箱TOY

一道斜率优化的经典例题。
对于这道题,DP式是容易得到的:
$$f_i=min\{f_j+(\sum_{j+1}^ia_{i}+i-j-1-L)^2\}$$
前缀和优化:
$$f_i=min\{f_j+(sm_i-sm_j+i-j-1-L)^2\}$$
考虑到这是一个与取值平方相关的式子,尝试用斜率优化来化简。
令:
$$u_i=sm_i+i$$
$$f_i=min{f_j+(u_i-u_j-1-L)^2}$$
对于右式,我们假定\(1\le j<k<i\)且从\(k\)转移较优。
那么我们有:
$$f_{k}+(u_{i}-u_{k}-1-L)^2\le f_{j}+(u_{i}-u_{j}-1-L)^2$$
展开并移项化简:
$$2u_{i}(u_{j}-u_{k})\le f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2$$
令:
$$g_{i}=(u_{i}+1+L)^2$$
并不妨假定:
$$u_{j}!=u_{k}$$
可得:
$$2u_{i}\le\frac{f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2}{(u_{j}-u_{k})}$$
故而,若要使得答案更大,则上式必然成立。
考虑到这个式子符合单调队列的性质,我们可以上一个类似单调队列的数据结构来维护右侧的式子,也就是俗称的“斜率”。
这就完成了斜率优化。

#include<iostream>
#include<cstdio>
#include<queue>


int n,L;
double sm[50005],f[50005];
int q[50005],l,r;
inline double u(int X){
	return sm[X]+X;
}
inline double g(int X){
	return u(X)+L+1;
}
inline double x(int X){
	return g(X);
}
inline double y(int X){
	return f[X]+g(X)*g(X);
}
inline double k(int A,int B){
	return (y(A)-y(B))/(x(A)-x(B));
}

void init(){
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;++i){
		scanf("%lf",&sm[i]);
		sm[i]+=sm[i-1];
	}
	l=r=1;
	for(int i=1;i<=n;++i){
		while(l<r&&k(q[l],q[l+1])<2*u(i)){
			++l; 
		} 
		f[i]=f[q[l]]+(u(i)-g(q[l]))*((u(i)-g(q[l])));
		while(l<r&&k(i,q[r-1])<k(q[r-1],q[r])){
			--r;
		}
		q[++r]=i;
	}
	printf("%lld\n",(long long)f[n]);
}

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

CF1098B Nice table

话说考场上这题距离正解只差一步了,可惜我走错方向变成枚举左上角的block然后瞎鸡儿乱搞求min了。
事实上这一题猜到结论之后可以想到另一个更科学的做法。
具体来说,可以考虑,要么是行上两种字符交替出现而列上随意,要么是列上两种字符交替出现而行上随意。
所以我们可以枚举这些信息,然后检验一下即可。
顺便提一句,这一题的数据范围真的是恶意满满。考场上是瞎jb哈希,但是现在个人觉得还是string比较科学。

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

#define MAXN 300005
char lst[6][2]={{'A','G'},{'A','C'},{'A','T'},{'C','T'},{'G','T'},{'C','G'}};
std::string ch[MAXN],out[MAXN];
int n,m,cnt[MAXN][2],val[MAXN][6][2],nw[2];

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=m;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[i][k-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[i][k-1]);
			}
			val[i][j][0]=(int)(nw[0]>=nw[1]);
			cnt[j][0]+=std::min(nw[0],nw[1]);
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<6;++j){
			nw[1]=nw[0]=0;
			for(int k=1;k<=n;++k){
				nw[0]+=(int)(lst[(j+(i&1)*3)%6][k&1]!=ch[k][i-1]);
				nw[1]+=(int)(lst[(j+(i&1)*3)%6][!(k&1)]!=ch[k][i-1]);
			}
			val[i][j][1]=(int)(nw[0]>=nw[1]);
			cnt[j][1]+=std::min(nw[0],nw[1]);
		}
	}
	int ans=0x3f3f3f3f;
	int pi,pj;
	for(int i=0;i<2;++i){
		for(int j=0;j<6;++j){
			ans=(cnt[j][i]<ans)?pi=i,pj=j,cnt[j][i]:ans;
		}
	}
	if(!pi){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				putchar(lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][0])]); 
			}
			puts("");
		}
	}else{
		for(int i=1;i<=m;++i){
			for(int j=1;j<=n;++j){
				out[j]+=lst[(pj+(i&1)*3)%6][(j&1)!=(val[i][pj][1])];
			}
		}
		for(int i=1;i<=n;++i){
			std::cout<<out[i]<<std::endl;
		}
	}
}

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

lp2597 ZJOI2012 灾难

这一题的思路还是比较清晰的。虽然可以当作支配树模板,但是事实上可以上一个LCA来代替支配树。
具体来说,就是把有多个食物的消费者连到它所有食物的LCA。然后计算一遍子树大小就好了。
注意连点之前要先拓扑排序。

#include<iostream>
#include<cstdio>
#include<queue>

#define Swap(A,B) (A^=B^=A^=B)

struct ee{
	int v;
	int nxt;
}e[2500005];
//h,树上的节点。g,拓扑排序的节点。to,每个节点的所有父亲。 
int h[70000],g[70000],et=0,dep[70000],fa[70000][18],in[70000],to[70000],sz[70000],loc[70000];
int n,tp=0;
inline void add(int *H,int U,int V){
	if(U==V){
		return;
	}
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void srt(){
	std::queue<int> q;
	for(int i=1;i<=n;++i){
		if(!in[i]){
			q.push(i);
		}
	}
	int p=0;
	while(!q.empty()){
		p=q.front();
		q.pop();
		loc[++tp]=p;
		for(int i=g[p];i;i=e[i].nxt){
			--in[e[i].v];
			if(!in[e[i].v]){
				q.push(e[i].v);
			}
		}
	}
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		Swap(X,Y);
	}
	for(int i=17;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i]; 
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=17;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
inline void prpr(){
	int nw=0;
	for(int i=1,j;i<=n;++i){
		j=loc[i];
		nw=e[to[j]].v;
		for(int k=to[j];k;k=e[k].nxt){
			nw=lca(nw,e[k].v);
		}
//		请注意这里的nw可能不存在任何父亲节点。 
		add(h,nw,j);
		fa[j][0]=nw;
		dep[j]=dep[nw]+1;
		for(int k=1;k<=17;++k){
			fa[j][k]=fa[fa[j][k-1]][k-1];
		}
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
		sz[X]+=sz[e[i].v];
	}
	++sz[X];
}
void init(){
	scanf("%d",&n);
	int x; 
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		while(x){
			++in[i];
			add(g,x,i);
			add(to,i,x);
			scanf("%d",&x);
		}
	}
	srt();
	prpr();
	dfs(0);
	for(int i=1;i<=n;++i){
		printf("%d\n",sz[i]-1);
	}
}

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

lp3615 如厕计划

观察题面我们可以发现,如果男性比女性多的话,显然是无法符合要求的;否则,女性使用男女通用单间的个数不应该超过男女性的人数差。
我们不妨把部分的男女性人数差个女性视为男性——这是一种贪心的做法。于是就把女性多于男性的情况归约成了男性和女性相同的情况。
在这种情况下,任何时候都不应该有女性进入男女通用单间。这也就意味着,如果令男性为1,女性为-1,那么在任何时候,数列的前缀和都应该保证为大于等于-1。
然而,要保证一个前缀和始终大于某个数是很难维护的——这是因为位于后面的信息我们无法得到。我们考虑维护后缀和,这样就可以预先得到位于后面的信息了。
于是,我们考虑对每一段计算它的贡献。

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

inline long long Max(long long A,long long B){
	return A>B?A:B;
}
inline long long Min(long long A,long long B){
	return A<B?A:B;
}

long long n,m;
int len;
char ch[200005];
long long dlt=0,a[200005],mx[200005],l[200005];
void init(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		len=strlen(ch+1);
		scanf("%lld",&l[i]);
		for(int j=len;j>=1;--j){
			a[i]+=(ch[j]=='M'?1:-1); 
			mx[i]=Max(mx[i],a[i]);
		}
		dlt+=a[i]*l[i];
	}
	if(dlt>0){
		puts("-1");
		return ;
	}
	long long nw=0,ans=1;
	for(int i=m;i>=1;--i){
		if(a[i]>0){
			ans=Max(ans,(l[i]-1)*a[i]+nw+mx[i]);
		}else{
			ans=Max(ans,nw+mx[i]);
		}
		nw+=l[i]*a[i];
	}
	printf("%lld",ans-1);
}

int main(){
	freopen("queue.in","r",stdin);
	freopen("queue.out","w",stdout);
	init();
	return 0;
}

lp2468 SDOI2010 粟粟的书架

简化题意。
有一个n*m的矩阵,q个询问,求问,在每个矩阵中最少取多少个数,使得和至少为h。
观察数据范围,我们惊讶地发现这一题不可避免地要做两次。
因为,n,m<=200显然不是用普通的数据结构可以维护的。我们考虑使用\(cnt_{i,j,k}\)表示大于k的数的数量,\(sm_{i,j,k}\)表示大于k的数的总和。然后二分这个k来求解即可。
对于n==1的情况,我们很容易可以想到维护一棵权值主席树。对于每一个询问,我们在两棵权值线段树上二分然后求差。

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int n,m,q;
int b[205][205],cnt[205][205][1005],sm[205][205][1005];
//不需要开longlong!!!MLE警告!!! 

inline long long cntQry(int X1,int Y1,int X2,int Y2,int K){
    return cnt[X2][Y2][K]-cnt[X1-1][Y2][K]-cnt[X2][Y1-1][K]+cnt[X1-1][Y1-1][K];
}
inline long long smQry(int X1,int Y1,int X2,int Y2,int K){
    return sm[X2][Y2][K]-sm[X1-1][Y2][K]-sm[X2][Y1-1][K]+sm[X1-1][Y1-1][K];
}
inline void slv2(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&b[i][j]);
        }
    }
    for(int k=0;k<=1000;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(int)(b[i][j]>=k);
                sm[i][j][k]=sm[i-1][j][k]+sm[i][j-1][k]-sm[i-1][j-1][k]+(int)(b[i][j]>=k)*b[i][j];
            }
        }
    }
    long long l,r,mid,h,ans;
    int X1,X2,Y1,Y2;
    while(q--){
        l=0,r=1001,ans=-1;
        scanf("%d%d%d%d%lld",&X1,&Y1,&X2,&Y2,&h);
        while(l<=r){
            mid=(l+r)>>1,smQry(X1,Y1,X2,Y2,mid)>=h?(ans=mid,l=mid+1):r=mid-1;
        }
        (~ans)?(printf("%lld\n",cntQry(X1,Y1,X2,Y2,ans)-(smQry(X1,Y1,X2,Y2,ans)-h)/ans)):(puts("Poor QLW"));
    }
    
//	 对于同一个k可能有多个值,而可能只需要选取部分。 
}
const int MAXN2=10000005;
int a[MAXN2];
//数组大小别算错 
class ChairmanTree{
    private:
        class Node{
            public:
                int l;
                int r;
                int fa;
                int sz;
                int sm;
        };
        Node tr[MAXN2];
        int cnt,rt[MAXN2];
        inline void build(int LST,int &NW,int L,int R,int V){
            NW=++cnt;tr[NW].sz=tr[LST].sz+1;tr[NW].sm=tr[LST].sm+V;
            if(L==R){return;}
            MID>=V?(build(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(build(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
            //如果值小等于MID。那么就更新右边的值;否则更新左边的值。一定要注意判断V==MID时的情况。 
            //如果更新的是右边的值,那么就把右边的节点与上一个版本的右边的节点一并下传,并修改本节点的左节点;否则反之。 
        }
        //从根往下搜索。注意减去的应当是右节点的值。 
        inline int qry(int A,int B,int L,int R,int V){
            int RT=0;
            while(L<R){(tr[tr[B].r].sm-tr[tr[A].r].sm)>V?(L=MID+1,B=tr[B].r,A=tr[A].r):(RT+=tr[tr[B].r].sz-tr[tr[A].r].sz,V-=(tr[tr[B].r].sm-tr[tr[A].r].sm),R=MID,B=tr[B].l,A=tr[A].l);}
            //同理,对于等于的情况也应当特别注意。 
            return RT+(V+L-1)/(L);
            //剩下的部分应该全部由大小为R的这些东西,也就是当前点的值来处理掉。故而要加上(V+L-1)/(L)
        }
    public:
        inline void ADD(int VER,int X){
            build(rt[VER-1],rt[VER],1,1000,X);
        }
        inline int QUREY(int LVER,int RVER,int X){
            return qry(rt[LVER-1],rt[RVER],1,1000,X);
        }
        inline int SUM(int L,int R){
            return tr[rt[R]].sm-tr[rt[L-1]].sm;
        }
        inline void INIT(){
            cnt=0;
        }
};
ChairmanTree T;
inline void slv1(){
    T.INIT();
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        T.ADD(i,a[i]);
    }
    int l,r,tmp,x;
    while(q--){
        scanf("%d%d%d%d%d",&tmp,&l,&tmp,&r,&x);
        if(T.SUM(l,r)<x){
            puts("Poor QLW");
            continue;
        }
        printf("%d\n",T.QUREY(l,r,x));
    }
}

void init(){
    scanf("%d%d%d",&n,&m,&q);
    n==1?slv1():slv2();
}

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

lp1131 ZJOI2007 时态同步

有一棵树,每次将一条边的长度增加1的代价为1,求,使得所有叶节点到根节点距离相同的最小代价。
很显然,对于一棵树来说,贪心地考虑,最终的距离显然是最开始的最远叶节点的距离。
然后,继续贪心地考虑,每一次增加的代价,应当避免那些已经是最远距离的节点。
但是这样做的话复杂度最坏是n^2的。
故而我们考虑树形DP。对于每个节点临时记以这个节点为根的子树完成时态同步需要的代价。然后每一次修改把修改结果记下来即可。

#include<iostream>
#include<cstdio>

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[500005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int n,s,f[500005];
long long ans=0;
inline void dfs(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs(e[i].v,X);
	}
	int mx=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		mx=Max(mx,f[e[i].v]+e[i].w);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		ans+=mx-(f[e[i].v]+e[i].w);
	}
	f[X]=mx;
}
void init(){
	scanf("%d%d",&n,&s);
	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);
	}
	dfs(s,0);
	printf("%lld\n",ans);
}

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

lp2150 NOI2015 寿司晚宴


将2~n的整数划分到两个集合,使得两个集合中任意两个元素互质,求方案数。
对于n<=30的情况是很容易想到的,将每个数\(i\)求出它的质因子集合\(K_{i}\)。
很容易可以发现,30以内的质数仅有10种。故而我们就有了一个\(O(2^{202}n)\)的做法。
对于n<=500的情况,似乎用上述的做法并不是十分可行,无论是时间复杂度还是空间复杂度都是不可接受的。
但是我们发现,有且仅有7个质数,在500以内会作为因数出现多次。我们是不是可以用一种奇技淫巧把大于19的质数处理掉呢?
我们惊讶地发现,由于所有较大的质数会且只会出现一次,那么很显然所有最大质因子是较大质数且最大质因子相同的数只能放到一个集合里。
故而我们把所有数按照最大质因子排序,然后从小到大遍历。当最大质因子成为较大质数的时候,不再使用原来的数组,而是将「这个质因子一个都没选」的情况复制到两个新的数组f2[2][1<<7][1<<7]。
每一次更换最大质因子的时候都从原数组继承DP值,然后在这里面对每一个是放在A还是放在B的情况来更新:

$$f_{S_1,S_2} = f2_{0,S_1,S_2} + f2_{1,S_1,S_2} – f_{S_1,S_2}$$

之所以最后还要减去原来的值是因为,两个新数组的最终结果各自都是从原来的「这个质因子一个都没选」的情况复制过来的,因此「这个质因子一个都没选」的情况就会被统计两次。


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

*/ 
const int P[8]={2,3,5,7,11,13,17,19};
const int MAX=1<<8;
long long MOD;
long long f[MAX][MAX],f2[2][MAX][MAX];
struct data{
	int v;
	int big;
	int K;
	inline void init(int X){
		v=X,big=0;
		int nw=v;K=0;
		for(int i=0;i<8;++i){
			if(!(nw%P[i])){
				K|=(1<<i);
			}
			while(!(nw%P[i])){
				nw/=P[i];
			}
		}
		if(nw>1){
			big=nw;
		}
	}
	inline bool operator<(const data &B)const{
		return big<B.big;
	}
}a[505];
int n;
void init(){
	scanf("%d%lld",&n,&MOD);
	--n;
	for(int i=1;i<=n;++i){
		a[i].init(i+1);
	}
	std::sort(a+1,a+1+n);
	int lst=0x3f3f3f3f;
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		if(a[i].big){
			lst=i;
			break;
		}
		for(int j=MAX-1;~j;--j){
//			注意这里要-1 
			for(int k=MAX-1;~k;--k){
				f[j][k|a[i].K]+=f[j][k];f[j|a[i].K][k]+=f[j][k];
				f[j][k|a[i].K]%=MOD;f[j|a[i].K][k]%=MOD;
			}
		}
	}
	for(int i=lst;i<=n;++i){
		if(a[i].big!=a[i-1].big){
			for(int j=0;j<MAX;++j){
				for(int k=0;k<MAX;++k){
					f2[0][j][k]=f2[1][j][k]=f[j][k];
				}
			}
		}
		for(int j=MAX-1;~j;--j){
			for(int k=MAX-1;~k;--k){
				if(j&k){
					continue;
				}
				if(!(k&a[i].K)){
					f2[0][j|a[i].K][k]+=f2[0][j][k];
					f2[0][j|a[i].K][k]%=MOD;
				}
				if(!(j&a[i].K)){
					f2[1][j][k|a[i].K]+=f2[1][j][k];
					f2[1][j][k|a[i].K]%=MOD;
				}
			}
		}
		if(a[i].big!=a[i+1].big){
			for(int j=0;j<MAX;++j){
				for(int k=0;k<MAX;++k){
					f[j][k]=(f2[0][j][k]+f2[1][j][k]+(MOD-f[j][k]))%MOD;
				}
			}
		}
	}
	long long ans=0;
	for(int i=MAX-1;~i;--i){
		for(int j=MAX-1;~j;--j){
			if(i&j){
				continue;
			}
			ans+=f[i][j];
			ans%=MOD;
		}
	}
	printf("%lld\n",ans);
}

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

 

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

 

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