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

lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。
我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点;第二个步骤,是找到这些点中到原点最小的点的距离。
我们容易发现,第一个步骤和长度无关,第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构:当你使用克鲁斯卡尔算法建最小/最大生成树的时候,每一次合并,你新建一个节点p,这个点的点权是这一次合并通过的边的边权,然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树,其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例,我们构造一棵最大生成树,那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说,从u在d的降水下可以到的节点,就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树,每个点的父亲节点的点权不会大于这个节点。这也就意味着,我们需要找到u的最高的祖先,使得这个祖先的点权大于等于d。不妨称这个祖先为w,那么w的子树的所有叶子节点,就是u在d的降水下能抵达的节点。
于是,我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图,我们先求出1号节点到所有节点的距离,然后把这些值赋到叶子节点上,不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」,那么就可以进行树形dp,把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。

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

const int N=800005,M=800005;
const int INF=0x3f3f3f3f;

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

struct ee{
	int v;
	int w;
	int a;
	int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
	e[++et]=(ee){V,W,A,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int A){
	Eadd(U,V,W,A);
	Eadd(V,U,W,A);
}
struct tee{
	int v;
	int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
	te[++et]=(tee){V,g[U]};
	g[U]=et;
}
inline void tadd(int U,int V){
	tEadd(U,V);
	tEadd(V,U);
}
struct data{
	int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
	return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
	return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	tadd(ff[X],cnt);tadd(ff[Y],cnt);
	ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
	cnt=n;
	for(int i=1;i<=m;++i){
		if(fa(lst[i].u)==fa(lst[i].v)){
			continue;
		}
		val[++cnt]=lst[i].a;
		uni(lst[i].u,lst[i].v);
		if(cnt==n*2-1){
			break;
		}
	}
	rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
	inline bool operator()(int A,int B){
		return dis[A]>dis[B];
	}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
	for(int i=2;i<=n*2;++i){
		dis[i]=INF;vis[i]=0;
	}
	vis[1]=1,dis[1]=0;
	q.push(1);
	int p;
	while(!q.empty()){
		p=q.top();q.pop();vis[p]=0; 
		for(int i=h[p];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].w){
				dis[e[i].v]=dis[p]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
}
inline void dfs0(int X){
	for(int i=g[X];i;i=te[i].nxt){
		if(te[i].v==f[X][0]){
			continue;
		}
//		printf("%d %d\n",X,te[i].v);
		f[te[i].v][0]=X;
		for(int j=1;j<=18;++j){
			f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
		}
		dfs0(te[i].v);
		dis[X]=Min(dis[X],dis[te[i].v]);
	}
}
inline int qry(int X,int D){
	for(int i=18;i>=0;--i){
		if(val[f[X][i]]>D){
			X=f[X][i];
		}
	}
	return dis[X];
}
void init(){
	scanf("%d%d",&n,&m);
	et=tet=0;
	for(int i=1;i<=n*2;++i){
		g[i]=h[i]=0;
	}
	int u,v,w,a;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&w,&a);
		add(u,v,w,a);
		lst[i]=(data){u,v,a};
	}
	std::sort(lst+1,lst+1+m,cmp);
	for(int i=1;i<=n*2;++i){
		ff[i]=i;val[i]=INF;
	}
	kruskal();
	dij();
	dfs0(rt);
//	for(int i=1;i<=rt;++i){
//		printf("%d ",dis[i]);
//	}
//	puts("");
	int Q,K,S,lans=0,x,d;
	scanf("%d%d%d",&Q,&K,&S);
	for(int i=1;i<=Q;++i){
		scanf("%d%d",&x,&d);
		x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
		printf("%d\n",lans=qry(x,d));
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp2146 NOI2015 软件包管理器

简化题意:
存在一棵树,其上所有点的初始值为0。
存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一个点的所有儿子节点改为0。
要求维护这个修改,并能得知每一次修改的节点个数。
当然地,考虑到这棵树是静态的,我们可以预处理出每个点的子树大小和它到根的路径长度。
于是,问题就转化为:
把目标节点到根节点的所有点变成1,把目标节点的子树变成0,查询目标节点到根节点的1的数量,查询目标节点的子树的1的数量。
这个问题似乎有些困难。我们考虑它的弱化版,也就是只有目标节点到根节点的这样一种情况。
显然,只需要上一个树剖就可以解决问题。
那么加上子树修改呢?
我们意识到一个很有趣的事情,那就是,一棵子树中的点,在树剖后,仍然是DFS序序列上连续的一段。又,这一段的长度显然是子树大小,由此问题可解。

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

const int N=100005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
int n,q;
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[N],sn[N],dep[N],fa[N];
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0,dep[X]=dep[FA]+1,fa[X]=FA;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
int dfn[N],cnt=0,tp[N]; 
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP,dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
int tr[N<<2],tg[N<<2];
inline void rnw(int X,int L,int R,int C){
	tr[X]=LEN*C,tg[X]=C+1;
}
inline void updt(int X,int L,int R){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(tg[X]){
		rnw(LS,L,MID,tg[X]-1),rnw(RS,MID+1,R,tg[X]-1);
		tg[X]=0;
	}
}
inline void chg(int X,int L,int R,int A,int B,int C){
	if(A<=L&&R<=B){
		rnw(X,L,R,C);
		return;
	}
	if(R<A||L>B){
		return;
	}
	pshd(X,L,R);
	chg(LS,L,MID,A,B,C),chg(RS,MID+1,R,A,B,C);
	updt(X,L,R);
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	pshd(X,L,R);
	return qry(LS,L,MID,A,B)+qry(RS,MID+1,R,A,B);
}

inline int dwqry(int X){
	return qry(1,1,n,dfn[X],dfn[X]+sz[X]-1);
}
inline void dwchg(int X){
	chg(1,1,n,dfn[X],dfn[X]+sz[X]-1,0);
}
inline int up(int X){
	int RT=0;
	while(X){
		RT-=qry(1,1,n,dfn[tp[X]],dfn[X]);
		RT+=dfn[X]-dfn[tp[X]]+1;
		chg(1,1,n,dfn[tp[X]],dfn[X],1);
		X=fa[tp[X]];
	}
	
	return RT;
}
void init(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<n;++i){
		scanf("%d",&x);
		add(i+1,x+1);
	}
	dfs0(1,0);
	dfs1(1,0,1);
	scanf("%d",&q);
	char ch[10];
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d",&x);
		++x;
		if(ch[1]=='i'){
			printf("%d\n",up(x));
		}else{
			printf("%d\n",dwqry(x));
			dwchg(x);
		}
	}
}
int main(){
	init();
	return 0;
}

lp2387 NOI2014 魔法森林

这一题据说是LCT维护边权的题目。但是我们观察一下感觉可以用动态加边SPFA来跑这道题。 具体来说,对于每一条加进来的边,我们知道,并不是整张图都因为这条边而改变。这条边会改变的有且仅有图的一部分。 因此,我们不妨将所有边按照a的大小排序,然后将b节点作为关键字,跑动态加边SPFA。 然后答案对dis[n]+e[i].a去min即可。这是因为如果它没有影响原来的最短路,那么选择这条边的a肯定不会更优;如果更新了,那么就必须要选择这条边的a。 复杂度大概是松松松,构造了菊花套菊花也没有卡掉,就假装能过吧…求大佬证明。

#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;
}
const int N=50005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
struct data{
	int u;int v;int a;int b;
	inline bool operator<(const data &B){
		return a^B.a?a<B.a:b<B.b;
	}
}ed[100005];
int h[N],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W),Eadd(V,U,W);
}
int dis[N];
bool vis[N];
queue<int> q;
inline void SPFA(int s1,int s2){
	vis[s1]=vis[s2]=1;
	q.push(s1),q.push(s2);
	int p;
	while(!q.empty()){
		p=q.front();q.pop();
		for(int i=h[p];i;i=e[i].nxt){
			if(Max(dis[p],e[i].w)<dis[e[i].v]){
				dis[e[i].v]=Max(dis[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
		vis[p]=0;
	}
}
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i){
		dis[i]=INF;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&ed[i].u,&ed[i].v,&ed[i].a,&ed[i].b);
	}
	sort(ed+1,ed+1+m);
	int ans=INF;
	for(int i=1;i<=m;++i){
		add(ed[i].u,ed[i].v,ed[i].b);
		SPFA(ed[i].u,ed[i].v);
		ans=Min(ans,dis[n]+ed[i].a);
	}
	printf("%d\n",ans<INF?ans:-1);
}
int main(){
	init();
	return 0;
}

lp2044 NOI2012 随机数生成器

我们不妨将原式递归展开,可以得到形如此的式子:
$$f_{n}=a^nf_{0}+\frac{(a^{n}-1)c}{a-1}$$
对于这个式子的值,我们看似可以上一个快速幂直接求得。
然而仔细观察上式的情况,发现如果出现了奇妙的模数时,\(a-1\)是不一定有逆元的!
这就很令人难受了。
我们找到原来的问题,我们不得不求下述式子的值:
$$f_{n}=a^nf_{0}+\sum_{i=0}^{n-1}a^ic=a^nf_{0}+(\sum_{i=0}^{n-1}a^i)c$$
求值的最大障碍是这个式子:
$$\sum_{i=0}^{n-1}a^i$$
将这个式子分奇偶讨论后递归求解。
我们令:
$$u_{x}=\sum_{i=0}^{x-1}a^i$$
若是偶数,则有:
$$u_x=\sum_{i=0}^{\frac{x-1}{2}}a^i+a^{\frac{x+1}{2}} (\sum_{i=0}^{\frac{x-1}{2}}a^i)$$
即,
$$u_x=(a^{\frac{x+1}{2}}+1)u_{\frac{x-1}{2}}$$
若是奇数,则只需将第一项单独计算。
这样就可以在对数复杂度内对式子求解了。
另外,考虑到模数的数据范围,我们需要使用一种被称为「龟速乘」,也就是「快速幂」在乘法意义上的等同的操作,使得不会出现乘法,也就不会爆范围。

#include<iostream>
#include<cstdio>

long long MOD,a,c,x0,n,g;
//必须注意,不能重载一个全部是标准型的运算符。 
inline long long mlt(long long A,long long X){
	long long BS=A,RT=0,CNT=X;
	while(CNT){
		if(CNT&1){
			RT+=BS;
			RT%=MOD;
		}
		CNT>>=1;
		BS+=BS;
		BS%=MOD;
	}
	return RT;
}
inline long long pw(long long A,long long X){
	long long BS=A,RT=1,CNT=X;
	while(CNT){
		if(CNT&1){
			RT=mlt(RT,BS)%MOD;
		}
		CNT>>=1;
		BS=mlt(BS,BS)%MOD;
	}
	return RT;
}
inline long long calc(long long X){
	if(X==2){
		return (a+1)%MOD;
	}
	if(X==1){
		return 1;
	}
	if(X&1){
		return (pw(a,X-1)+calc(X-1))%MOD;
	}
	return mlt((pw(a,(X+1)>>1)+1),calc(X>>1));
}
void init(){
	scanf("%lld%lld%lld%lld%lld%lld",&MOD,&a,&c,&x0,&n,&g);
	printf("%lld",((mlt(pw(a,n),x0)+mlt(calc(n),c))%MOD)%g);
}

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

lp3980 NOI2008 志愿者招募

一开始YY了一种连边方式,就是源点向第一个点连边,第一个点向最后一个点连边,每个边的流量是1,希望能通过一些奇奇怪怪的约束条件来保证能从1跑到n。
但是很快这个想法就被枪毙了——每一天需要消耗的人力是不同的。
怎么办呢?
我们可以考虑一种(我瞎取名叫)替换法的建模方法。
具体来说就是,先确定一个最大流,然后将其中的一些流量替换为必须要通过实际需要的路径才能跑过,这样就保证了答案的合法性。

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

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

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[400005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,vis[20005],dis[20005],val[20005],nw[20005],fa[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

long long ans=0,ans2=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		ans2+=val[t];
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
int a[20005],tot=0;
//tot不能想当然地取最大值,而应该取和。
//这是因为,过程中可能存在一些情况,使得先雇佣某个志愿者会更优。 
void init(){
	scanf("%d%d",&n,&m);
	s=n+2,t=n+3;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		tot+=a[i];
	}
	++tot;
	add(s,1,tot,0),add(n+1,t,tot,0);
	for(int i=1;i<=n;++i){
		add(i,i+1,tot-a[i],0);
	}
	int l,r,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&l,&r,&c);
		add(l,r+1,tot,c);
	}
	EK();
	printf("%lld\n",ans);
}

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

lp2050 NOI2012 美食节

这一题是SCOI2007修车的威力加强版。
用常规的写法显然是无法通过的。
我们考虑动态加边。
这样就可以最小化每一次松弛带来的影响,于是复杂度就变成了O(能过)
(才怪呢。我卡常卡了半天结果还是开了O2才过。)
(赶紧学zkw费用流)

#include<iostream>
#include<cstdio>
#include<queue>
#define calc(I,J) ((J-1)*sm+I)
#define calc2(I) (I+sm*m)

namespace IO{
	const int S = 1E6;
	char buf[S];
	int len=0,pos=0;
	inline char frc(){
		if(len==pos){pos=0,len=fread(buf,1,S,stdin);}
		if(len==pos){exit(0);}else{putchar(buf[pos]);return buf[pos++];};
	}
	inline int fri(){
		int fr=1,ch=frc(),x=0;
		while(ch<=32)ch=frc();
		if(ch=='-')fr=-1,ch=frc();
		while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=frc();
		putchar(ch);
		return x*fr;
	}
}

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[6600005];
int h[90005],et=-1;

inline void add(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
	e[++et]=(ee){U,0,-C,h[V]};
	h[V]=et;
}
//mp[i][j]表示第i种菜由第j名厨师做需要消耗的时间。 
int n,m,s,t,sm,vis[90005],dis[90005],val[90005],fa[90005],nw[90005],po[45],mp[45][105];
int q[90005];
int l,r;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	dis[s]=0,vis[s]=1,fa[t]=-1;
	l=1,r=0;
	q[++r]=s;
	register int p;
	while(l<=r){
		p=q[l++];
		vis[p]=0;
		for(register int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q[++r]=e[i].v;
				}
			}
		}
	}
	return fa[t]!=-1;
}
//倒数第I个,厨师J 
int ans;
inline void EK(){
	register int p,cnt,ck;
	while(SPFA()){
		cnt=fa[t]%sm,ck=fa[t]/sm+1;
		++cnt;
		//注意这里的逆hash 
		for(int i=1;i<=n;++i){
			add(calc2(i),calc(cnt,ck),1,cnt*mp[i][ck]);
		}
		p=t;
		ans+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}
void init(){
	puts("2333");
	n=IO::fri(),m=IO::fri();
	for(int i=1;i<=n;++i){
		po[i]=IO::fri();
		sm+=po[i];
	}
	s=sm*m+n+1,t=sm*m+n+2;
	for(register int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m;++j){
			mp[i][j]=IO::fri();
			add(calc2(i),calc(1,j),1,mp[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		add(s,calc2(i),po[i],0);
	}
	for(register int i=1;i<=sm*m;++i){
		add(i,t,1,0);
	}
	EK();
	printf("%d\n",ans);
}

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

lp2805 NOI2009 植物大战僵尸

仔细阅读题意,我们发现,这道题本质上就是一个约束类问题:对于每一株植物,都存在一些植物,需要消灭掉它们才能消灭它。
故而,它就变成了一个这样的问题:存在一些植物,其中的一些要消灭了另外一些之后才能消灭,问收益最大化的方法。
如果我们对每一棵植物建点,然后从一棵植物向它的约束植物连边,那么问题就转化为:一张有向图,每个点都有点权,请选中其中的某些点,使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是,从源点向正权点连权值为点权的边;从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么,答案就是总权值减去最小割。


下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点,连向汇点的边被割掉表示选中这个点。
那么,最终的结果必然是一个闭合子图。
这是因为,对于这张图的最小割,当你选中一个节点之后,这个点的所有后继负权节点都一定被割掉/选中了(根据割的性质显然);
这个点的所有后继正权节点都一定不被割/选中了(根据最小割的性质,割掉这些边没有意义)。
并且,任何一个闭合子图的选法都至少可以对应一个割法。
这是因为,对于原图中的某一种连接方法,都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时,根据我们此前的定义,最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而,答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的,故而最小割可以得到最优答案。


PS:
这一题应当考虑死锁情况,想象一个无限攻击力和攻速的豌豆射手。(不考虑连样例都过不了)(但是尽管这样还是能够拿到80分)
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记,然后令这些点在网络流中不存在。
然而,如果我们直接写一个拓扑排序的话,还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想,因为这张图上每一条有向边的终点一旦被删去,那么它的所有前驱也都是不能存在的。
故而,对反图进行拓扑排序找环并删去才能符合题目的要求。


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

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

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

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

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

lp1963 NOI2009 变换序列

如果知道这道题是一个二分图匹配,就显得非常简单了。
首先我们对原序列和变换序列各自建一个点。
然后,对于每一组约束条件\(D_{i}\),我们向所有到\(i\)的距离为\(D_{i}\)的点连一条边。
然后先跑一遍二分图最大匹配。如果全部都能匹配上就说明有解。

但是题目要求字典序输出这组解,怎么办呢?
这么做的意思就是,对于一个尽可能小的数\(i\),它匹配的数\(T_{i}\)也要尽可能小。
故而,搜索的时候从大往小即可。

#include<iostream>
#include<cstdio>
int n,D[10005];
int vis[10005],dep=0;
int usd[10005];

inline bool dfs(int X){
	int up=(X+D[X]-1)%n+1,dw=(X-D[X]+n-1)%n+1;
	if(up<dw){
		std::swap(up,dw);
	}
//	printf("%d %d\n",up,dw);
	if(!usd[dw]&&vis[dw]!=dep){
		vis[dw]=dep;
		usd[dw]=X;
		return 1;
	}
	if(vis[dw]!=dep){
		vis[dw]=dep;
		if(dfs(usd[dw])){
			usd[dw]=X;
			return 1;
		}
	}
	if(!usd[up]&&vis[up]!=dep){
		vis[up]=dep;
		usd[up]=X;
		return 1;
	}
	if(vis[up]!=dep){
		vis[up]=dep;
		if(dfs(usd[up])){
			usd[up]=X;
			return 1;
		}
	}
	
	return 0;
}
int Ans[10005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&D[i]);
	}
	int ans=0;
	for(int i=n;i>=1;--i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	if(ans<n){
		puts("No Answer");
	}else{
		for(int i=1;i<=n;++i){
			Ans[usd[i]]=i;
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]-1);
		}
	}
}

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

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

 

lp1486 NOI2004 郁闷的出纳员

(似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话,是可以跑得飞快的。)
首先看一下题面,发现值域很小,很容易就可以想到用权值线段树维护。
支持:单点加,区间清零,查询第k大的权值线段树。
当然这题有一些细节。
一:如果初始工资低于工资下限,那么这个人就不存在。
二:维护的是第\(k\)大的而非第\(k\)小的。
三:由于是严格小于工资下限,要注意边界的开闭性。最好将公式写出来。

#include<iostream>
#include<cstdio>
using namespace std;
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID) 
//支持:单点加,区间清零,查询第k大的权值线段树。
int tr[2000005],cnt=0; 
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(!tr[X]){
		tr[LS]=tr[RS]=0;
	}
}
inline void add(int X,int L,int R,int A){
	if(L==R){
		++tr[X];
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A);
	}else{
		add(RS,MID+1,R,A);
	}
	updt(X);
}
inline void clr(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		cnt+=tr[X];
		tr[X]=0;
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		clr(LS,L,MID,A,B);
	}
	if(B>MID){
		clr(RS,MID+1,R,A,B);
	}
	updt(X);
}
inline int srch(int X,int L,int R,int K){
	if(L==R){
		return L;
	}
	pshd(X,L,R);
	if(tr[RS]<K){
		return srch(LS,L,MID,K-tr[RS]);
	}else{
		return srch(RS,MID+1,R,K);
	}
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	pshd(X,L,R);
	int rt=0;
	if(A<=MID){
		rt+=qry(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qry(RS,MID+1,R,A,B);
	}
	updt(X);
	return rt;
}
//1 k 插入大小为k的点
//2 k 全部数加上k
//3 k 全部数减去k
//4 k 查询第k大的值 
int n,m,tg=0,k;
char op[4];
void init(){
	scanf("%d%d",&n,&m);
	--m;
	for(int i=1;i<=n;++i){
		cin>>op;
		scanf("%d",&k);
		if(op[0]=='I'){
			//注意大于与大等于。 
			if(k>m){
				add(1,1,300001,k+100001+tg);
			}
		}else if(op[0]=='A'){
			tg-=k; 
		}else if(op[0]=='S'){
			tg+=k;
			clr(1,1,300001,1,m+100001+tg);
		}else if(op[0]=='F'){
			if(qry(1,1,300001,1,300001)<k){
				puts("-1");
			}else{
				printf("%d\n",srch(1,1,300001,k)-100001-tg);
			}
		}
	}
	printf("%d",cnt);
}
int main(){
	init();
	return 0;
}