• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P5391 – 青染之心 题解

开发技术 开发技术 5小时前 3次浏览

自己想出来一个奇怪的(复杂度是严格的)序列分块(遇到困难分大块!)。看了题解发现是巧妙的链分治(想不到啊想不到)。两种方法都写一下吧。

首先这是个显然的带撤销完全背包。但是带撤销要求记录所有历史版本,这样空间也是平方的,就爆炸了。于是考虑优化空间同时保证时间是平方(第一次见到用空间限制加强题目难度的)。

正解:重链剖分

这题允许离线,我们将加入和撤销操作离线下来可以得到一个与之对应的操作树(我曾经点开过一个建撤销树 + LCT 的 CF 题,然而不会 LCT 就关闭了页面,只记得这个建树的套路),那么某个节点处的答案就是根节点到它的路径上物品的完全背包。

考虑一遍 dfs,维护递归栈。那么这和朴素做法根本没有任何区别,因为递归栈是 (mathrm O(max dep)) 的,一条链就到 (mathrm O(n))​ 了。。。。不过我们有这样一个优化的思路:考虑当前在点 (x),那么在它访问最后一个访问的儿子树时,可以不在递归栈中保留 (x) 处的背包,直接修改成最后一个儿子处的背包,因为最后一个儿子后面没有撤销操作了(这体现了离线的优点:可以知道当前是不是最后一个撤销)。这样看似只能省一点点空间,但是我们可以改变儿子的访问顺序,钦定某个儿子最后一个访问。「钦定一个特殊的儿子」是不是想到了链分治?考虑重剖,那么每条链上经过的不特殊的儿子数量是 log,也就是说递归栈中时刻只有 log 个元素,空间就是 (mathrm O(mlog n)) 了。或者你长剖可以做到 (mathrm O(msqrt n))​​ 也可以。

结构体写背包比较爽。

code
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2e4+10;
int m,qu,n;
int v[N],w[N];
int fa[N];
vector<int> nei[N];
vector<int> qry[N];
int wson[N],sz[N];
void dfs1(int x=n+1){
	sz[x]=1;
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i];
		dfs1(y);
		sz[x]+=sz[y];
		if(sz[y]>sz[wson[x]])wson[x]=y;
	}
}
struct knap{
	int dp[N];
	knap(){memset(dp,0,sizeof(dp));}
	void add(int V,int W){
		for(int i=W;i<=m;i++)dp[i]=max(dp[i],dp[i-W]+V);
	}
};
vector<knap> stk;
int ans[N];
void dfs(int x=n+1){
	for(int i=0;i<qry[x].size();i++)ans[qry[x][i]]=stk.back().dp[m];
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i];
		if(y==wson[x])continue;
		stk.pb(stk.back());stk.back().add(v[y],w[y]);
		dfs(y);
		stk.pop_back();
	}
	if(wson[x])stk.back().add(v[wson[x]],w[wson[x]]),dfs(wson[x]);
}
int main(){
	cin>>qu>>m;
	int now=0;
	for(int i=1;i<=qu;i++){
		char op[10];
		scanf("%s",op);
		if(op[0]=='a')n++,scanf("%d%d",w+n,v+n),fa[n]=now,nei[now].pb(n),now=n,qry[n].pb(i);
		else now=fa[now],qry[now].pb(i);
	}
	for(int i=1;i<=n;i++)if(fa[i]==0)fa[i]=n+1,nei[n+1].pb(i);
	qry[n+1]=qry[0];
	dfs1();
	stk.pb(knap());dfs();
	for(int i=1;i<=qu;i++)printf("%dn",ans[i]);
	return 0;
}

歪解:分块

考虑对任意时刻物品序列所在的模子(后面可能有一大截空的位置)这个静态的序列进行分块,块大小为 (B=sqrt n)。一个容易想到的思路是:任意时刻维护当前 (n) 所在块的所有位置的背包,以及之前所有块的第一个位置的背包。这样如果在块内移动那显然不需要担心;跨块的话,如果是添加,那么就将上一个块的背包全部删掉只留开头;如果是撤销,那就对撤销后所在块进行根号重构

但这样复杂度是假的,因为数据有可能在两相邻块的分界点反复横跳,时间复杂度就爆炸了。考虑针对性地补救一下这个情况:对于反复横跳,我们在第一次往右跳的时候并不删除上一块的背包们,这样除了第一次左跳,都不需要重构了。那么这样我们必定维护当前块所有和之前块首位,以及任意时刻往右跨块移动的时候并不立刻删除上一整块背包们,直到到下下块再删,也就是时刻最多只维护当前块和上一块这两块的整块。这样空间是 (3mB)​,依然能接受。

但这只是针对特殊卡法的补救,能否适应一般情况呢?尝试构造卡的方法,发现这个算法表现得很丝滑,根本卡不掉。然后发现可以胡出来一个证明:

  1. 每次清空倒数第三块时,说明此时正在往右移过相邻块分界点,此时保留了上一整块的背包。如果想要再做一次清空操作,至少要往后走 (B) 步;如果想要做一次暴力重构,那么往前退一格是没有用的,必须往前退 (B) 步到达倒数第三块才会进行暴力重构
  2. 每次暴力重构时,说明此时正在往左跨分界点,此时保留了该块一整块的背包。下一次清空,往右走一步按照算法并不会清空,只能往右走 (B) 步;下一次重构,肯定要往前退 (B) 步。

也就是说「清空」和暴力重构这两种 (mathrm O(Bm)) 的操作都是必须隔 (B) 次才会有一次,总复杂度就是 (mathrm O!left(dfrac nBBmright)=mathrm O(nm))​。

btw,这题由于空间是线根,本身就比较卡,如果用 vector<knap> 实现会开两倍空间,就会 MLE 了。于是需要手写双向链表(u1s1 链表确实是除了 BIT 和 ufset 以外最好写的 ds),稳过好吧。

code
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2e4+10;
int qu,m;
struct knap{
	int dp[N];
	knap(){memset(dp,0,sizeof(dp));}
	void add(int V,int W){
		for(int i=W;i<=m;i++)dp[i]=max(dp[i],dp[i-W]+V);
	}
};
const int B=141;
struct addedge{
	int sz,siz[N],head[N],tail[N],prv[N],nxt[N];knap val[3*B+10];
	addedge(){sz=0;}
	vector<int> stk;
	int nwnd(){
		int p;
		if(stk.size())p=stk.back(),stk.pop_back();
		else p=++sz;
		return p;
	}
	void pb(int x,knap y){
		siz[x]++;
		int p=nwnd();
		val[p]=y;
		prv[p]=tail[x],nxt[tail[x]]=p,tail[x]=p;
	}
	knap &back(int x){return val[tail[x]];}
	void ppb(int x){
		siz[x]--;
		stk.pb(tail[x]);
		int pv=prv[tail[x]];
		nxt[pv]=0,prv[tail[x]]=0;
		tail[x]=pv;
	}
}blk;
int V[N],W[N];
int main(){
	cin>>qu>>m;
	int n=0;
	while(qu--){
		char op[10];
		cin>>op;
		if(op[0]=='a'){
			int w,v;
			cin>>w>>v;
			n++;
			V[n]=v,W[n]=w;
			if((n+B-1)/B!=(n+B-2)/B){
				blk.pb((n+B-1)/B,n==1?knap():blk.back((n+B-2)/B));
				blk.back((n+B-1)/B).add(v,w);
				if((n+B-1)/B>=3)while(blk.siz[(n+B-1)/B-2]>1)blk.ppb((n+B-1)/B-2);
			}
			else{
				blk.pb((n+B-1)/B,blk.back((n+B-1)/B));
				blk.back((n+B-1)/B).add(v,w);
			}
		}
		else{
			if((n+B-1)/B!=(n+B-2)/B){
				blk.ppb((n+B-1)/B);
				if(blk.siz[(n+B-2)/B]==1){
					int b=(n+B-2)/B,l=(b-1)*B+1,r=b*B;
					for(int i=l+1;i<=r;i++)blk.pb(b,blk.back(b)),blk.back(b).add(V[i],W[i]);
				}
			}
			else blk.ppb((n+B-1)/B);
			n--;
		}
		printf("%dn",n?blk.back((n+B-1)/B).dp[m]:0);
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:P5391 – 青染之心 题解
喜欢 (0)