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

lp1792 国家集训队 种树

首先拿到题面很容易可以想到的是状压DP,状态转移方程很容易可以推出来。
但是这么做的复杂度是\(O(n^2)\)的,只能拿到50分。
我们深入地考虑这一题的性质,我们发现,对于这个环,如果取用了上面的某一个点,那么这个点的两个邻点都不可取。
贪心地依据权值从大到小考虑,如果一个点的两个邻点加起来都不如它大的话,那么取邻点中的任意一个都不如取这个点。
如果这个点的两个邻点加一起比它大,那就考虑两种情况,一种情况是选择这个点,一种情况是选择这个点的两个邻点。
(很容易可以知道,如果两个邻点只选一个,那是一定没有选这个点优的。)
我们考虑先取了这个点,再转变为取这个点的两个邻点的情况。这种情况下,总权值就会减去这个点的权值,并且加上这个点的两个邻点的权值。
我们考虑一个有趣的性质。如果一个点的两个邻点都选取了,那么影响到的“不可被选取区域”的大小,是和三个都选是相同的。
因此,我们考虑究竟应该选取这个点还是这个点的两个邻点。我们考虑每当挖去一个点的时候,都把它的两个邻点标记为消失。
这时候对不可选取区域的影响已经确定了,因此只要确定对对权值的影响。
那么我们考虑建一个虚点,替代在贪心选取的那个点以及两个相邻的位置。这个虚点的权值相当于邻点的权值和减去原点的权值。
对于这个虚点,我们把它当做这个环上本来就存在的一个点来处理即可。
所以可以考虑用堆+双向链表来维护。

顺便提一句,这是一道三倍经验题,它的亲人们:
lp3620 APIO/CTSC2007 数据备份,lp1484 种树
前者只要差分一下,边转点,改大小判断以后的边界,再改一下单调队列;后者只要判一下负数情况。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int n,m,a[200005],l[200005],r[200005],nw,nw2;
bool ext[200005];
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q.push((pii){a[i],i});
		ext[i]=0;
	}
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=2;i<=n;++i){
		l[i]=i-1;
	}
	l[1]=n;
	for(int i=1;i<n;++i){
		r[i]=i+1;
	}
	r[n]=1;
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

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

顺便贴一下后面两题的代码:

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,a[500005],l[500005],r[500005],nw,nw2;
bool ext[500005];
//lp1484 种树 
typedef pair<int,int> pii;
priority_queue<pii> q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		q.push((pii){a[i],i});
		ext[i]=0;
	}
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=1;i<=n;++i){
		l[i]=i-1;
	}
	for(int i=1;i<=n;++i){
		r[i]=i+1;
	}
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		if(q.top().first<0){
			break;
		} 
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,m,a[100005],l[100005],r[100005],nw,nw2;
bool ext[100005];
//lp3620 APIOCTSC2007 数据备份 
typedef pair<int,int> pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ext[i]=0;
	}
	for(int i=n;i>=1;--i){
		a[i]-=a[i-1];
	}
	for(int i=1;i<n;++i){
		a[i]=a[i+1];
		q.push((pii){a[i],i});
	} 
	a[0]=a[n]=0x3f3f3f3f; 
	if(m>(n>>1)){
		puts("Error!");
		return;
	}
	for(int i=1;i<n;++i){
		l[i]=i-1;
	}
	for(int i=1;i<n;++i){
		r[i]=i+1;
	}
	long long ans=0;
	for(int i=1;i<=m;++i){
		while(!q.empty()&&ext[q.top().second]){
			q.pop();
		}
		nw=q.top().second;
		ans+=q.top().first;
		ext[l[nw]]=1,ext[r[nw]]=1;
		nw2=a[l[nw]]+a[r[nw]]-q.top().first;
		a[nw]=nw2;
		l[nw]=l[l[nw]],r[nw]=r[r[nw]];
		r[l[nw]]=nw,l[r[nw]]=nw;
		q.pop();
		q.push((pii){nw2,nw});
	}
	printf("%lld",ans);
}

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