lp4244 SHOI2008 仙人掌图 II

仙人掌图是每一个点双都只有一个环的连通图。
对于一个仙人掌图,它在许多方面都有树的性质,只是其中的有一些节点被换成了环。
我们不妨依然采用一种伪树形DP的方式来处理这棵树,我们发现,非环节点的转移都是非常容易达成了,问题在于环上的节点的转移。

首先,我们要找到这个环,这可以用Tarjan算法来完成。
具体来说,我们维护两个数组:dfn和lw,其中前者表示的是某一个节点的dfs序,后者表示的是某一个节点至多走一条返祖边或者父亲边能够到达的最小dfs序。
显然,在搜索中,如果下一个节点未被访问过,我们就可以在搜索完它以后将当前节点的lw与它的lw取较小值。
否则,当前节点通向它的边一定是一条返祖边或者父亲边,那么当前节点的lw值应当与它的dfs序取较小值。

对于一个环,我们如果将它视为一个节点,我们想一想要怎么从它的「孩子」们处转移呢?
我们发现,依次枚举它的每一个孩子,答案显然是:
$$max(f_i+f_j+dis_{i,j})$$
这个式子可以使用单调队列优化。所以我们每一次把一个环提出来瞎DP一下就好了。

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

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 nxt;
}e[200005];
int et=0,h[100005];
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 n,m;
int dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;
int ans=0,f[100005],a[100005];
std::deque<int> q;
inline void calc(int X,int Y){
	int tot=dep[Y]-dep[X]+1;
	int nw=tot;
	for(int i=Y;i!=X;i=fa[i]){
		a[nw--]=f[i];
	}
	a[nw]=f[X];
	for(int i=1;i<=tot;++i){
		a[tot+i]=a[i];
	}
	while(!q.empty()){
		q.pop_front();
	}
	q.push_back(1);
	for(int i=2;i<=(tot<<1);++i){
		while(!q.empty()&&i-q.front()>(tot>>1)){
			q.pop_front();
		}
		if(!q.empty()){
			ans=Max(ans,a[i]+a[q.front()]+i-q.front());
		}
		while(!q.empty()&&a[q.back()]-q.back()<a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i=2;i<=tot;++i){
		f[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));
	}
}
inline void dfs(int X,int FA){
	dfn[X]=lw[X]=++cnt;
	Fv(i,X){
		if(e[i].v!=FA){//这一句如果不加会无形降低很多点的lw值,从而使环的大小变成0。 
			if(!dfn[e[i].v]){
				fa[e[i].v]=X;
				dep[e[i].v]=dep[X]+1;
				dfs(e[i].v,X);
				lw[X]=Min(lw[X],lw[e[i].v]);
			}else{
				lw[X]=Min(lw[X],dfn[e[i].v]);
			}
			if(lw[e[i].v]>dfn[X]){
				ans=Max(ans,f[X]+f[e[i].v]+1);
				f[X]=Max(f[X],f[e[i].v]+1);
			}
		}
		
	}
	Fv(i,X){
		if(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){
			calc(X,e[i].v);
		}
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,x;
	for(int i=1;i<=m;++i){
		u=0;
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d",&v);
			if(u){
				add(u,v);
			}
			u=v;
		}
	}
	dfs(1,0);
	printf("%d\n",ans);
}

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

lp4382 八省联考2018 劈配

扫一眼题目,看到n个点和m个点匹配的问题,你就会有一种预感——是不是要跑二分图匹配?
是的,就是要跑二分图匹配。
第一问很显然,大力让一个导师能够被多个学生匹配,然后跑一个类似于匈牙利的操作。然后如果匹配满了,我们就考虑将这个导师匹配的其他学生尝试匹配同一个优先级的其他节点。
这个复杂度肯定是很松的。
那么关键在于第二问要怎么处理。
观察发现答案具有单调性。也就是说,如果一个选手在较高的优先度会感到沮丧,那么他在一个较低的优先度也会感到沮丧;
因此我们考虑二分答案来检验。
这样的复杂度大概是三方乘对数级的。时间比较紧张。
我们考虑一种优化策略:发现选手提高到某个优先度了以后,他就相当于顶替了本来在这个优先度的选手的位置。
故而,我们可以对于前缀的选手,储存到每个选手时的匹配状态。每次找到某个优先度,就把他的信息加入到对应的匹配状态中,然后跑上述操作。
这样可以优化到平方乘对数级,可能可以通过此题。
这一题的具体操作——也就是那个一点多匹配的操作并不是特别会,以后需要重新研究。
我好菜啊。

#include<iostream>
#include<cstdio>

int c,n,m;
int mx[205],a[205][205],val[205][205][15],exp[205];
int usd[205],usd1[205],usd2[205][205],vis[205];
int prusd[205][205],prusd1[205][205],prusd2[205][205][205];
inline bool dfs(int X,int V){
	int nw,nxt;
	for(int i=1;i<=val[X][V][0];++i){
		nw=val[X][V][i];
		if(vis[nw]){
			continue;
		}
		vis[nw]=1;
		if(usd[nw]<mx[nw]){
			usd1[X]=nw;
			usd2[nw][++usd[nw]]=X;
			return 1;
		}
		for(int j=1;j<=mx[nw];++j){
			nxt=usd2[nw][j];
			if(dfs(nxt,a[nxt][nw])){
				usd1[X]=nw;
				usd2[nw][j]=X;
				return 1;
			}
		}
	}
	return 0;
}
inline void calc1(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		for(int j=1;j<=m;++j){
			if(!val[i][j][0]){
				continue;
			}
			if(dfs(i,j)){
				break;
			}
		}
		for(int j=1;j<=m;++j){
			prusd[i][j]=usd[j];
		}
		for(int j=1;j<=i;++j){
			prusd1[i][j]=usd1[j];
		}
		for(int j=1;j<=m;++j){
			for(int k=1;k<=usd[j];++k){
				prusd2[i][j][k]=usd2[j][k];
			}
		}
	}
}
inline bool chck(int X,int Y){
	for(int i=1;i<=m;++i){
		usd[i]=prusd[Y-1][i];
	}
	for(int i=1;i<=Y-1;++i){
		usd1[i]=prusd1[Y-1][i];
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=usd[i];++j){
			usd2[i][j]=prusd2[Y-1][i][j];
		}
	}
	for(int i=1;i<=m;++i){
		vis[i]=0;
	}
	for(int i=1;i<=exp[X];++i){
		if(!val[X][i][0]){
			continue;
		}
		if(dfs(X,i)){
			return 1;
		}
	}
	return 0;
}
void init(){
//	注意清空数组!!!
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&mx[i]);
	}
	for(int i=1;i<=200;++i){
		usd1[i]=0;
		usd[i]=0;
		for(int j=1;j<=200;++j){
			for(int k=0;k<=10;++k){
				val[i][j][k]=0;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
			if(a[i][j]){
				val[i][a[i][j]][++val[i][a[i][j]][0]]=j;
			}
		}
	}
	for(int i=1;i<=n;++i){
		a[i][0]=m+1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&exp[i]);
	}
	calc1();
	for(int i=1;i<=n;++i){
		printf("%d ",a[i][usd1[i]]);
	}
	puts("");
	int l,r,mid,ans;
	for(int i=1;i<=n;++i){
		if(a[i][usd1[i]]<=exp[i]){
			printf("0 ");
			continue;
		}
		l=1,r=i-1,ans=0;
		while(l<=r){
			mid=(l+r)>>1;
			if(chck(i,mid)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			} 
		}
		printf("%d ",i-ans);
	}
	puts("");
}

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

lp4363 九省联考2018 一双木棋chess

快要省选了,需要学习一些乱搞操作。
在这里学习一下Min-Max对抗搜索。
首先了解一下Min-Max对抗搜索。
首先我们知道,对于一个零和有限信息确定性博弈游戏,我们可以将整个游戏的所有局面建成一个有向图。而在几乎所有此类游戏中,整个游戏的所有局面应当能组成一个DAG。
对于这样一个DAG,我们可以对它进行分层,最后得到的应当是一张分层图。这张分层图上的每一层象征着一方正在进行操作。
那么显然这个游戏的最终解是可以知道的。无非就是直接把整张图DFS一遍罢了。
然而,在绝大部分游戏中,这么做的复杂度都太大了,以至于根本无法接受。我们考虑一种被称为Min-Max对抗搜索的搜索方法。
我们首先定义先手方为Max方,后手方为Min方,然后设置一个搜索范围。那么每一个节点的值是这样确定的:
如果它的深度是搜索深度边缘,亦或者它干脆就是一个终止局面,那么它的值就是一个精心设计的估价函数的值。这个估价函数应当能够较好地估计整个局面倾向于哪一方。
如果这个节点是由Max方行动,那么它的值是所有子局面里的值的最大值,因为Max方会向对自己最有利的局面走。
如果这个节点是由Min方行动,那么它的值是所有子局面里的值的最小值,因为Min方会向对Max方最不利的局面,也就是对自己最有利的局面走。
这样就能够求得当前局面的权值,从而得到一个较优秀的决策支了。
本来打算学一下alpha-beta剪枝的,但是这一题好像不是很需要…

回到这一题,如果我们暴力储存每一个状态,那么很显然时间会爆炸。有没有更好的思路呢?
直觉告诉我们,一个格子放置的次序和答案是没有关系的。所以我们不妨假定当前放置的格子总是左上角的一整个块。这样状态数大概就在10^10以内了。
然而实际上并不需要这么多的状态。所以可以Hash以后用map离散化。

#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>

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 INF=0x3f3f3f3f;
std::tr1::unordered_map<long long,int> mp;
int a[11][11],b[11][11],f[11],n,m;

inline long long hsh(){
	long long RT=0;
	for(int i=1;i<=n;++i){
		RT*=12;
		RT+=f[i];
	}
	return RT;
}

inline void ahsh(long long X){
	for(int i=n;i>=1;--i){
		f[i]=X%12;
		X/=12;
	}
}

inline int dfs(long long X,bool typ){
	if(mp.count(X)){
		return mp[X];
	}
	int RT=typ?-INF:INF;
	long long nw;
	ahsh(X);
	for(int i=1;i<=n;++i){
		if(f[i]<f[i-1]){
			++f[i];nw=hsh();
			RT=typ?Max(RT,dfs(nw,0)+a[i][f[i]]):Min(RT,dfs(nw,1)-b[i][f[i]]);
			--f[i];
		}
	}
	return mp[X]=RT;
}

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<=n;++i){
		f[i]=m;
	}
	mp[hsh()]=0;
	printf("%d\n",dfs(0,1));
}

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

lp3868 TJOI2009 猜数字

这是一道中国剩余定理(又名孙子定理、CRT)的模板题。
它最早来自于「孙子算经」,形式化的说,它是一种用于求解如下的线性同余方程组的解的算法。
$$ \left\{ \begin{matrix}x\equiv a_{1} \pmod{p_1} \\x\equiv a_{2}\pmod{p_2}\\\cdots\\x\equiv a_{n}\pmod{p_i}\end{matrix} \right.$$
我们令:
$$\begin{equation}\begin{split}P&=&\prod_{i=1}^{n}p_{i}\\t_{i},st: \frac{P}{p_{i}}t_{i}&\equiv &1\pmod{p_i}\\\exists x,st: x&\equiv &\sum_{i=1}^n \frac{P}{p_{i}}a_{i}t_{i}\\x&\in&\{x_0+kP,k\in Z\pmod{P}\}\end{split}\end{equation}$$
然而这是怎么证明的呢?我们有如下推导:
$$\begin{equation}\begin{split}\forall i,\forall j,st:i\neq j, a_{i}t_{i}\frac{P}{p_{i}}&\equiv&0&\pmod{p_i}\\a_{i}t_{i}\frac{P}{p_i}&\equiv&a_{i} &\pmod{p_i}\\\forall j,\sum_{i=1}^{n}a_{i}t_{i}\frac{P}{p_{i}}&\equiv&a_{j}t_{j}\frac{P}{p_{j}} \equiv a_{j}&\pmod{p_{j}}\\\exists x_0&\equiv& \sum_{i=1}^{n}a_{i}t_{i}\frac{P}{p_{i}}&\pmod{p_{j}}\\\end{split}\end{equation}$$
故而我们就可以求得上述方程的最小正整数解。
另外,看到这题的数据范围就可以猜到又是龟速乘登场的时刻了。
这一题还有个坑点就是读入的数可能是负数…

#include<iostream>
#include<cstdio>

long long MOD=1;


inline long long mlt(long long A,long long X){
	long long BS=A,RT=0;
	while(X){
		if(X&1){
			RT+=BS;
			RT%=MOD;
		}
		BS+=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}
inline long long exgcd(long long A,long long B,long long &X,long long &Y,long long D=0){
	return B?(D=exgcd(B,A%B,Y,X),Y-=A/B*X,D):(X=1,Y=0,A);
}
inline long long pw(long long A,long long X){
	long long BS=A,RT=1;
	while(X){
		if(X&1){
			RT=mlt(RT,BS)%MOD;
		}
		BS=mlt(BS,BS)%MOD;
		X>>=1;
	}
	return RT;
}
long long n,a[100005],b[100005];
void init(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&b[i]);
		a[i]=(a[i]%b[i]+b[i])%b[i];//注意负数!! 
		MOD*=b[i];
	}
	long long X,Y,T,ans=0;
	for(int i=1;i<=n;++i){
		T=MOD/b[i];
        exgcd(T,b[i],X,Y);
        X=(X%b[i]+b[i])%b[i];;
        ans=(ans+mlt(mlt(T,X),a[i]))%MOD;
	}
	printf("%lld\n",(ans+MOD)%MOD);
}

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

lp2604 ZJOI2010 网络扩容

第一问没什么好说的。直接看第二问。
一个很直接的想法就是,在每条边上都加上一条容量为\(k\),费用为\(c_{e}\)的边。
但是仔细一想会发现一个问题:如果s到t有多条路径的话,上述的方法就会使得流量总额过大。
有什么好方法呢?
第一个直接的想法是发现源汇之间如果有多条路径的话,那么必然是将所有的流量k全都贪心地放在花费最小的那条路径上是最优的。
但是这显然是不可能的,考虑一个残余网络非空的情况。
故而我们换一种思路:在原来所有边上额外连流量为k的边的同时,再从n向一个虚拟汇点t连一条边。这样既可完成。

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

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[20005];
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,K,dis[20005],nw[20005],val[20005],fa[20005],vis[20005];
int u[20005],v[20005],w[20005],c[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		dis[i]=INF;
		val[i]=INF;
		vis[i]=0;
	}
	q.push(s);
	dis[s]=0,vis[s]=1,fa[t]=-1;
	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(dis[e[i].v]>dis[p]+e[i].c&&e[i].w>0){
				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;;
}

int answ=0,ansc=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=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(){
	scanf("%d%d%d",&n,&m,&K);
	s=1,t=n;
	for(int i=1;i<=n+1;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",u+i,v+i,w+i,c+i);
		add(u[i],v[i],w[i],0);
	}
	EK();
	printf("%d ",answ);
	for(int i=1;i<=m;++i){
		add(u[i],v[i],INF,c[i]);
	}
	add(t,t+1,K,0);
	++t;
	EK();
	printf("%d\n",ansc);
}

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

lp3159 CQOI2012 交换棋子

首先是一个常见套路:将棋子的交换等价为棋子的移动——这很重要。我们不妨把交换看做黑子的移动。
那么我们考虑这个问题的弱化版:假设每个格子的移动次数没有限制,该怎么做。
很显然将每个格子拆成两个点,然后每个右点向相邻的左点连边,跑最大流即可。
对于一个黑子的移动,我们发现,如果一个格子是这个黑子中途经过的点,那么这个格子必然会消耗两次交换次数。
故而,我们给从左点到右点的边设置一个容量上限,其值为交换次数上限的一半。
但是这么做的话我们发现了一个问题:倘若一个点起始状态和结束状态不一样,这个模型是无法有效描述结果的。
这是因为,如果一个点的起始状态和结束状态不一样,那么它通过的次数必然是奇数。
我们考虑这样拆点:将每个点拆成左,中,右三个点。然后,将每个点的右点向它的所有相邻点的左点连边,流量1,费用0。表示某个棋子走向了它的另一个相邻的棋子。
从中点向右点连一条边,表示这个点移出去的次数。显然,如果最终情况是白的而初始情况是黑的,这个点应该会多移出去一次。
从左点向中点连一条边,表示这个点移进来的次数。显然,如果最终情况是黑的而初始情况是白的,这个点应该会多移进来一次。
我们考虑这个「多移进来」和「多移出去」对这个点可以参与的交换次数的影响。
假若限定次数是偶数,那么多出来的这一次移动将使得这个点能参与的交换次数少一次;倘若限定次数是奇数,那么多出来的这一次移动将不影响这个点能参与的交换次数。
所以,我们可以用形如\(\lfloor \frac{limit+[end>begin]}{2} \rfloor \)和\(\lfloor \frac{limit+[begin>end]}{2} \rfloor \)的式子来描述这两条边的流量。
然后,对于题目要求的最小交换次数,我们考虑将原来就存在的连边加上费用。这样就满足了题目的要求。

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

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={1,0,-1,1,-1,1,0,-1};

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[200005];
int h[1205],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[1205],dis[1205],val[1205],fa[1205],nw[1205];

std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,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;
}
int answ=0,ansc=0;
inline void zkw(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}

char begin[25][25],end[25][25],limit[25][25];
inline int calc(int X,int Y,int T){
	return T*n*m+(X-1)*m+Y;
}

void init(){
	scanf("%d%d",&n,&m);
	s=3*n*m+1,t=3*n*m+2;
	int cnt=0;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>begin[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>end[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>limit[i]+1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(begin[i][j]=='1'){
				++cnt;
				add(s,calc(i,j,1),1,0);
			}
			add(calc(i,j,1),calc(i,j,2),(limit[i][j]-'0'+(int)(begin[i][j]>end[i][j]))>>1,1);
			if(end[i][j]=='1'){
				add(calc(i,j,1),t,1,0);
			}
			add(calc(i,j,0),calc(i,j,1),(limit[i][j]-'0'+(int)(end[i][j]>begin[i][j]))>>1,1);
			for(int k=0;k<8;++k){
				int x=i+dx[k],y=j+dy[k];
				if(x>=1&&x<=n&&y>=1&&y<=m){
					//n,m!!!
					add(calc(i,j,2),calc(x,y,0),INF,0);
				}
			}
		}
	}
	zkw();
	printf("%d\n",(answ==cnt?ansc:-1)>>1);
}

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

lp2153 SDOI2009 晨跑

题意简述:求一张图上不共点两点间最大路径数。
首先考虑不共边最大路径数,很容易可以想到大力上一个最大流,边流量为一。
然后考虑不共点最大路径数。我们发现,可以通过拆点来构成约束条件。具体来说就是将每个点拆成入点和出点,然后跑一个网络流。
现在还要求一个最短总路径长度,很容易可以想到费用流。具体来说,就将每一条边的费用设置为它的长度。然后跑一遍即可。

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

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[100005];
int h[405],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,dis[405],val[405],fa[405],nw[405];
bool vis[405];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,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(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

void init(){
	scanf("%d%d",&n,&m);
	s=1,t=2*n;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&c);
		add(n+u,v,1,c);
	}
	for(int i=2;i<n;++i){
		add(i,n+i,1,0);
	}
	add(1,n+1,1926,0);
	add(n,2*n,1926,0);
	int ansW=0,ansC=0,p;
	while(spfa()){
		p=t;
		ansW+=val[t];
		ansC+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
	printf("%d %d\n",ansW,ansC);
}

int main(){
	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;
}

lp1640 SCOI2010 连续攻击游戏

一般地,对于兼具可行性和唯一性的问题,我们考虑二分图匹配。
对于这一题来说,我们考虑拆点。
值得一提的是,这里的拆点并不是将一个点的两个属性拆开来,而是将一个点的属性和编号拆开来。然后跑匈牙利。
如果可以匹配,那就继续匹配;如果不能匹配,那就说明这个属性无论如何也取不到;或者取到它需要付出「前面有某个属性无法取到」的代价,那么就是没有答案了。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[2000005];
int h[10005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}

int n;
int vis[1000005],dep;
int usd[1000005];

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a,&b);
		add(a,i),add(b,i);
	}
	int ans=0;
	dep=0;
	for(int i=1;i<=n;++i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	printf("%d\n",ans);
}

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

lp1129 ZJOI2007 矩阵游戏

提示:行列匹配。


当知道这一题是行列匹配之后,做法就非常显然了。
我们观察发现,如果将每个行与每个列标上序号的话,题目的要求就是求两个排列,使得黑格子排在主对角线上。
然后我们考虑每一个黑格子,我们发现,在最终情况下的每一个黑格子,它所在的行的序号和列的序号均与开始时的序号相同。
故而,所求的两个排列中,相同位置的行和列在开始时的交点必然是黑色的。
所以,每个黑格子就在行列之间连一条边,用行来匹配列,如果都能一一匹配则说明有解。

#include<iostream>
#include<cstdio>
int mp[205][205];
int n,usd[205],vis[205],dep;
inline bool dfs(int X){
	for(int i=1;i<=n;++i){
		if(!mp[X][i]){
			continue;
		}
		if(vis[i]!=dep){
			vis[i]=dep;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	return 0;
} 
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		usd[i]=0,vis[i]=0;
		for(int j=1;j<=n;++j){
			scanf("%d",&mp[i][j]);
		}
	}
	dep=0;
	for(int i=1;i<=n;++i){
		++dep;
		if(!dfs(i)){
			puts("No");
			return;
		}
	}
	puts("Yes");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		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;
}

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

 

lp2572 SCOI2010 序列操作

操作要求:
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
我们考虑维护线段树来处理这些询问。
考虑线段树的基本性质。线段树的特性决定了它能够\(O(nlogn)\)来处理各种能够\(O(1)\)合并两个子区间信息的信息。
上述询问中,总共有多少个1是很容易可以维护的。最大的问题在于维护“最多有多少个连续的1”
实际上,对于这里的每一种信息,我们都需要对称地维护它们——即,在维护1的信息的同时也要维护0的信息。这是操作\(2\)导致的。
我们考虑对于两种询问分别考虑。
首先是\(3\),这个很好维护,直接维护\(1\)的个数即可。合并的时候简单相加即可。
对于\(4\),第一个想到的肯定是可以维护区间的最长连续1。
但是我们发现,仅仅维护这个信息还是不够的。因为这样是无法把子区间的信息合并的。
我们反过来考虑,对于一个区间,它的最长连续1有可能怎样从两个子区间转移过来。
首先,可能是完全被包含在两个区间之一。这种情况的话,只需要维护区间的最长连续1,然后取Max即可。
但是,还有可能这个区间是跨越了两个区间的。这时候我们需要维护,子区间左起最长连续1与右起最长连续1。
然后,在转移区间信息的时候,我们只需要再考虑两个子区间的左起最长连续1与右起最长连续1即可。
接着我们考虑对于端点起最长连续1的转移——这种转移存在一种特殊情况,也就是,这个区间的端点起最长连续1的长度超过了中点。
这时候需要特殊判定。
这样就做完了。
写了5k,的确是一道麻题。

另,我莫名其妙RE了,估计是不知道哪里边界判挂了。考试的时候要注意在不MLE的情况下多开几倍的数组保险。

#include<iostream>
#include<cstdio>

#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
int n,m,a[100005],A,B,op;
inline int Max(int AA,int BB){
    return AA>BB?AA:BB;
}
struct data{ 
    int sm0;int sm1;
    int mx0;int mx1;
    int lmx0;int lmx1;
    int rmx0;int rmx1;
    //有翻转标记为1,否则为0;没有赋值为-1,有为0或1; 
    int lzy;int st;
    data(int sm0=0,int sm1=0,int mx0=0,int mx1=0,int lmx0=0,int lmx1=0,int rmx0=0,int rmx1=0,int lzy=0,int st=-1):
        sm0(sm0),sm1(sm1),mx0(mx0),mx1(mx1),lmx0(lmx0),lmx1(lmx1),rmx0(rmx0),rmx1(rmx1),lzy(lzy),st(st){}
}tr[300005];//262144
inline data mrg(const data &X,const data &Y,const data BS){
    data RT;
    RT.mx0=Max(X.mx0,Y.mx0);
    RT.mx0=Max(RT.mx0,X.rmx0+Y.lmx0);
    RT.sm0=X.sm0+Y.sm0;
    //一个巧妙的技巧,如果存在1,那么肯定不是全0,反之亦然。 
    RT.lmx0=X.sm1?X.lmx0:X.lmx0+Y.lmx0;
    RT.rmx0=Y.sm1?Y.rmx0:Y.rmx0+X.rmx0;
    
    RT.mx1=Max(X.mx1,Y.mx1);
    RT.mx1=Max(RT.mx1,X.rmx1+Y.lmx1);
    RT.sm1=X.sm1+Y.sm1;
    RT.lmx1=X.sm0?X.lmx1:X.lmx1+Y.lmx1;
    RT.rmx1=Y.sm0?Y.rmx1:Y.rmx1+X.rmx1;
    RT.lzy=BS.lzy;RT.st=BS.st;
    return RT;
}
inline void updt(int X){
    tr[X]=mrg(tr[LS],tr[RS],tr[X]);
}
inline void rnw1(int X,int L,int R){
    std::swap(tr[X].lmx0,tr[X].lmx1);
    std::swap(tr[X].rmx0,tr[X].rmx1);
    std::swap(tr[X].mx0,tr[X].mx1);
    std::swap(tr[X].sm0,tr[X].sm1);
}
inline void rnw20(int X,int L,int R){
    tr[X].lmx0=LEN;tr[X].lmx1=0;
    tr[X].rmx0=LEN;tr[X].rmx1=0;
    tr[X].mx0=LEN;tr[X].mx1=0;
    tr[X].sm0=LEN;tr[X].sm1=0;
}
inline void rnw21(int X,int L,int R){
    tr[X].lmx0=0;tr[X].lmx1=LEN;
    tr[X].rmx0=0;tr[X].rmx1=LEN;
    tr[X].mx0=0;tr[X].mx1=LEN;
    tr[X].sm0=0;tr[X].sm1=LEN;
}
inline void rnw(int X,int L,int R,int TYP){
    if(TYP==0){
        tr[X].lzy=0;tr[X].st=0;
        rnw20(X,L,R);
    }else if(TYP==1){
        tr[X].lzy=0;tr[X].st=1;
        rnw21(X,L,R);
    }else{
        tr[X].lzy^=1;
        rnw1(X,L,R);
    }
}
inline void pshd(int X,int L,int R){
    if(tr[X].st>-1){
        rnw(LS,L,MID,tr[X].st);rnw(RS,MID+1,R,tr[X].st);
        tr[X].st=-1;
    }
    if(tr[X].lzy){
        rnw(LS,L,MID,2);rnw(RS,MID+1,R,2);
        tr[X].lzy=0;
    }
}
inline void chg(int X,int L,int R,int TYP){
    if(A<=L&&R<=B){
        //如果完全被包含则直接更新。 
        rnw(X,L,R,TYP);
        return;
    }
    pshd(X,L,R);
    if(A<=MID){
        chg(LS,L,MID,TYP);
    }
    if(B>MID){
        chg(RS,MID+1,R,TYP);
    }
    updt(X);
}
inline data qry(int X,int L,int R){
    if(A<=L&&R<=B){
        pshd(X,L,R);
        return tr[X];
    }
    pshd(X,L,R);
    if(A<=MID){
        if(B>MID){
            return mrg(qry(LS,L,MID),qry(RS,MID+1,R),data());
        }else{
            return qry(LS,L,MID);
        }
    }else{
        if(B>MID){
            return qry(RS,MID+1,R);
        }else{
            return data();
        }
    }
}

inline void build(int X,int L,int R){
    if(L==R){
        tr[X]=(data){a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],0,-1};
        return;
    }
    build(LS,L,MID);
    build(RS,MID+1,R);
    updt(X);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    data ans;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&op,&A,&B);
        ++A,++B;
        if(op<3){
            chg(1,1,n,op);
        }else if(op==3||op==4){
            ans=qry(1,1,n);
            if(op==3){
                printf("%d\n",ans.sm1);
            }else if(op==4){
                printf("%d\n",ans.mx1);
            }
        }
    }
}
int main(){
    init();
    return 0;
}

 

lp4578 FJOI2018 所罗门王的宝藏

首先,我们可以知道,令每一行、列数字的变化为\(dx_{i},dy_{i}\),那么对于\(z_{i,j}\),一定有:
$$dx_{i}+dy_{j}=z_{i,j}$$
对这个线性方程组变形,我们可以发现,如果指定序列合法,那么:
$$ \forall x ,z_{x,j_{1}}-z_{x,j_{2}}=dy_{j_{1}}-dy_{j_{2}} $$
$$ \forall y ,z_{i_{1},y}-z_{i_{2},y}=dx_{i_{1}}-dx_{i_{2}} $$
而,当\(dx\)和\(dy\)的相对关系不矛盾时,一定可以导出一个符合题意的矩阵。
因此,我们对于每组\(x,y\),统计它们的相对关系即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k; 
int dx[1005][1005],dy[1005][1005];
bool visx[1005][1005],visy[1005][1005];
int x[1005],y[1005],z[1005];
void init(){
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    memset(visx,0,sizeof(visx));
    memset(visy,0,sizeof(visy));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    int nw;
    for(int i=1;i<k;++i){
        for(int j=i+1;j<=k;++j){
            if(x[i]==x[j]&&y[i]==y[j]&&z[i]!=z[j]){
                puts("No");
                return; 
            }
            if(x[i]==x[j]){
                nw=y[i]>y[j]?z[j]-z[i]:z[i]-z[j];
                if(visx[y[i]][y[j]]&&dx[y[i]][y[j]]!=nw){
                    puts("No");
                    return;
                }
                dx[y[i]][y[j]]=dx[y[j]][y[i]]=nw;
                visx[y[i]][y[j]]=visx[y[j]][y[i]]=1; 
            }
            if(y[i]==y[j]){
                nw=x[i]>x[j]?z[j]-z[i]:z[i]-z[j];
                if(visy[x[i]][x[j]]&&dy[x[i]][x[j]]!=nw){
                    puts("No");
                    return;
                }
                dy[x[i]][x[j]]=dy[x[j]][x[i]]=nw;
                visy[x[i]][x[j]]=visy[x[j]][x[i]]=1; 
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(dx[i][i]||dy[i][i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
} 

 

lp4568 JLOI2011 飞行路线

首先看到点数,就考虑拆点。
把每一个点拆成k个点,分别表示已经吃了k次免费午餐的距离。
然后大力跑堆优化dij即可。可以用pair加伪函数套STL。
特别要注意是小根堆。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B)) 

struct ee{
    int v;int w;int nxt;
}e[100005];
int h[10005],et=0,f[10005][12],n,m,k,s,t;
inline void add(const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,h[u]};
    h[u]=et;
}
typedef pair<int,int> pii;
struct cmp{
	bool operator ()(const pii &A,const pii &B){
		return f[A.first][A.second]>f[B.first][B.second];
	}
};
priority_queue<pii,vector<pii>,cmp> q;
void bfs(int s){
    pii p(s,0);
    q.push(p);
    while(!q.empty()){
        p=q.top();
        q.pop();
        for(int i=h[p.first];i;i=e[i].nxt){
            if(f[e[i].v][p.second]>f[p.first][p.second]+e[i].w){
                f[e[i].v][p.second]=f[p.first][p.second]+e[i].w;
                q.push((pii){e[i].v,p.second});
            }
            if(p.second+1<=k){
                if(f[e[i].v][p.second+1]>f[p.first][p.second]){
                    f[e[i].v][p.second+1]=f[p.first][p.second];
                    q.push((pii){e[i].v,p.second+1});
                }
            }
        }
    }
}
void init(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&s,&t);
    memset(f,0x3f,sizeof(f));
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(u==v){
            continue;
        }
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=0;i<=k;++i){
        f[s][i]=0;
    }
    bfs(s);
    int ans=0x3f3f3f3f;
    for(int i=0;i<=k;++i){
        ans=Min(ans,f[t][i]);
    }
    printf("%d",ans);
    
}
int main(){
    init();
    return 0;
}

 

lp2161 SHOI2009 会场预约

这一题据说被放在了线段树这个模块下面。
我想了很久很久。想到了一种做法。但是一写就感觉很麻。
想着想着,算了一下复杂度,然后大喊一声,MADE!
仔细一想,询问2E5,值域1E5。大力上分块啊,\(O(Nsqrt(M))\approx 6E7\)不满。搞什么线段树啊,真是的。
好的,那么大力上分块。
具体应该要怎么分块呢?
对于每一块,我们定义一种标记。
如果标记是0,说明这个块是空的,那么就可以直接修改;
如果标记是一个正整数,说明这个块被该正整数完全包含,也可以直接修改,并将该标记指的数放入删除集合;
如果标记是-1,说明这个块里面包含多个询问。此时同样暴力修改。
为什么这样做的复杂度是对的呢?首先,如果一个块,如果它包含多个询问,那么要么它包含的是整个询问,要么它包含的是询问的一段。
因此,对于一个询问,它最多只可能被暴力修改两次。
所以这种做法是可行的。

不过分块写起来还是挺麻的。调了半天没调出来,然后看到了一个神仙做法,就抄过来了:
具体来说,就是把Set当作红黑树用。
太猛了。

#include<cmath>
#include
#include
#include<cstring>
#include<set> 
using namespace std;
#define MAXN 100000
int n;
struct data{
	int l,r;
	bool operator <(const data &A)const{
		return (this->l==A.l)?(this->l<A.r):(this->l<A.l);
	}
};

set<data> st;
void init(){
	scanf("%d",&n);
	char ch[5];
	int l,r,ans;
	for(int i=1;i<=n;++i){
		cin>>ch;
		if(ch[0]=='B'){
			printf("%lld\n",st.size());
		}else{
			scanf("%d%d",&l,&r);
			data X=(data){l,r};
			ans=0;
			set<data>::iterator it=st.lower_bound(X);
			while(1){
				it=st.lower_bound(X);
				if(it->l<=X.r&&X.l<=it->r){
					++ans;
					st.erase(it);
					continue;
				}
				it=st.lower_bound(X);
				if(it!=st.begin()){
					--it;
					if(it->l<=X.r&&X.l<=it->r){
						++ans;
						st.erase(it);
						continue;
					}
				}
				break;
			}
			st.insert(X);
			printf("%d\n",ans);
		}
	}
}
int main(){
	init();
	return 0;
}

//大力分块的假做法,直到现在都不懂bug在哪里。第k块表示k*blck~(k+1)*blck-1的值。 
int n,cnt=0,blck,L[200005],R[200005],rst,TOP;
int V[317],v[100005];
char ch[4];
bool bo[200005];
inline void prpr(){
    blck=sqrt(MAXN);
    rst=MAXN%blck;
    TOP=MAXN-rst;
    memset(V,0,sizeof(V));
    memset(v,0,sizeof(v));
    memset(bo,0,sizeof(bo));
}
int rt=0;
inline void delB(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
        if(V[i]==x){
            V[i]=0;
        }
    }
}
inline void delb(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
        if(v[i]==x){
            v[i]=0;
        }
    }
}
inline void del(const int &x){
    bo[x]=0;
    ++rt;--cnt;
    int l=L[x],r=R[x];
    if(r/blck-1<(l/blck+1)){
        delb(l,r,x);
        return;
    }
    delB(l/blck+1,r/blck-1,x);
    delb(l,(l/blck+1)*blck-1,x),delb((r/blck)*blck,r,x);
    
}
inline void addb(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
    	if(V[i/blck]!=x){
    		V[i/blck]=-1;
		} 
        if(!bo[v[i]]){
            v[i]=x;
        }else{
            del(v[i]);
            v[i]=x;
        }
    }
}
inline void clr(const int &x){
    for(int i=x*blck;i<(x+1)*blck;++i){
        if(bo[v[i]]){
            del(v[i]);
        }
    }
}
inline void addB(const int &l,const int &r,const int &x){
    for(int i=l;i<=r;++i){
        if(!V[i]){
            V[i]=x;
        }else if(V[i]>0){
            if(bo[V[i]]){
                del(V[i]);
            }
            V[i]=x;
        }else{
            clr(i);
            V[i]=x;
        }
    }
}
inline int add(const int &l,const int &r,const int &x){
    rt=0;
    if(r/blck-1<(l/blck+1)){
        addb(l,r,x);
        return rt;
    }
    addB(l/blck+1,r/blck-1,x);
    addb(l,(l/blck+1)*blck-1,x),addb((r/blck)*blck,r,x);
    return rt;
}
void init(){
    prpr();
    scanf("%d",&n);
    int l,r;
    for(int i=1;i<=n;++i){
        cin>>ch;
        if(ch[0]=='B'){
            printf("%d\n",cnt);
        }else{
            bo[i]=1;++cnt;
            scanf("%d%d",&l,&r);
            printf("%d\n",add(l-1,r-1,i));
            L[i]=l-1,R[i]=r-1;
        }
    }
}
int main(){
    init();
    return 0;
}

 

lp2467 SDOI2010 地精部落

这一题的题面很复杂,但形式化地概括则很简单:

对于一个长度为n的全排列,求出其中有多少排列A满足,对于任意i属于n,$$(A_{i}-A{i-1})*(A_{i}-A_{i+1})>=0;$$

然后我们观察排列的特点,我们可以发现,对于排列A中的一个元素\(A_{i}\),我们可以发现,如果\(A_{i}\)是山峰,那么将\(A_{i}\)的值无论添加多少,都不改变这个序列的可居住性;对于山谷,则反之。
于是,我们可以发现,一个合法的排列,如果我们要在它末尾添上一个数让它形成一个新的合法排列,对于除了最后一个数以及这个数是属于山峰以及山谷以外,我们不关心其他的属性。
因此我们可以用\(f[i][j][k]\)表达当前长度为i,最后一个数为j,最后一个数的状态为k的时候的状态数。其中k==0表示山谷,而k==1表示山峰。
则很容易可以得到状态转移方程:
$$f[i][j][k]+=f[i-1][l][k\ xor\ 1](k?(0<l<=j-1):(j-1<l<=i))$$
但是这样子的复杂度是N^3的,对于4200的数据显然是不能通过的。这时候考虑优化。
我们发现求和的东西是一段区间,因此我们可以考虑前缀优化。
这样子就将复杂度从\(n^3\)降低到了\(n^2\),于是可以通过。
但是这样子需要的空间是3E7的,对于128MB的空间是非常危险的,这时候考虑滚动数组优化,这样是可以通过的。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,p,f[4205][2],pre[4205][2];
void init(){
    scanf("%lld%lld",&n,&p);
    int l,r;
    f[1][1]=f[1][0]=pre[1][0]=pre[1][1]=1;
    for(int i=2;i<=n;++i){
        pre[i][0]=pre[i-1][0],pre[i][1]=pre[i-1][1];
        for(int j=1;j<=i;++j){
            for(int k=0;k<=1;++k){
                l=k?0:j-1;
                r=k?j-1:i;
                f[j][k]=(pre[r][k^1]-pre[l][k^1]+p)%p;
//                printf("(%d,%d)[%d,%d]%lld|",l,r,pre[l][k^1],pre[r][k^1],f[j][k]);
            }
//            printf(" ");
        }
        pre[0][0]=pre[0][1]=0;
        for(int j=1;j<=i;++j){
            pre[j][0]=(pre[j-1][0]+f[j][0])%p;
            pre[j][1]=(pre[j-1][1]+f[j][1])%p;
        }
//        puts("");
    }
    long long ans=(pre[n][0]+pre[n][1])%p;
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
}

 

Q:为什么这个方程不会重复统计呢?
如果只关心上一个元素的大小,排列中的元素可能重复出现了。

A:不会重复统计,感性证明如下:

首先我们假定对于上一个A,使得:

$$ |A|==i-1 $$

并没有重复统计。
那么我们插入一个新的元素\(i\)时,产生的新序列必然是 本质不同 的。
我们对于\(A_{i-1}\)是山峰和山谷分别讨论。
如果\(A_{i-1}\)是山峰,那么新插入的元素,必然比\(A_{i-1}\)小,并且一定是由将序列中大等于【某个小于等于\(A_{i-1}\)的一个数\(l\)】的所有数提升一,然后将新插入的元素定义为\(l\)。
这时候,\(i-1\)位上的数是\(A_{i-1}+1\),而\(i\)位上的数则是\(l\)。
在这种情况下,最后两位是\(A_{i-1}+1\)与\(l\)。显然对于每一个本来已有的\(A_{i-1}\),它们在新的序列中都会加且仅加1。
这样,所有新增的组合的最后两位都是 本质不同 的,因此序列本质不同。
对于山谷,情况类同于山峰,同样可以证明不会产生重复的后两位,进而不会产生本质相同的数列。

而对于 $$|A|==1$$ ,结果显然是1,没有重复统计。
从而归纳得出全部都没有重复统计。