专栏文章

题解：P11179 [ROIR 2018] 管道监控 (Day1)

MMeta_Morph
P11179题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2c4mt
此快照首次捕获于
2025/12/01 19:25
3 个月前
此快照最后确认于
2025/12/01 19:25
3 个月前
查看原文

[ROIR 2018] 管道监控 (Day1) 题解

[ROIR 2018] 管道监控 (Day1) 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

Trie，Hash，树形 DP。

分析

其实很容易就可以想到全部解法，考虑 DP。
由于字符串长度较长，肯定有一维需要用来记延后处理的字符串，然后我们发现状态就没别的了，于是设 fu,if_{u,i} 表示 uu 节点处选取字符串往上延伸了 ii 长度的最小花费。
初始状态为 fu,0=0,fu,i=inf⁡(i>0)f_{u,0}=0,f_{u,i}=\inf(i>0)。
这个 DP 分两步走：
  1. 合并子树，假设现在合并子节点 vv，那么转移方程就为：
    fu,max⁡(i,j)′←fu,i+fv,j+1f'_{u,\max(i,j)} \gets f_{u,i} + f_{v,j+1} \\
    这一步可以 O(n2)O(n^2) 做，也可以优化到 O(n)O(n)。
  2. 给自己加字符串。
    注：一个字符串只需要在最底下的点加一遍即可，一个点最多也只会作为一个加入的字符串的底部。这两个点比较浅显，但还是解释一下。
    如果找到可以加入的字符串，长度为 lenlen，权值为 ww，那么我们的转移方程就为：
    fu,len′←fu,i(i<len)f'_{u,len} \gets f_{u,i} (i<len) \\
    这一步可以 O(n2)O(n^2) 做，也可以 O(n)O(n) 做。
那么考虑如何找符合条件的字符串，可以在 DP 时用栈记录前缀 Hash，复杂度是 O(nm)O(nm)，可以通过；也可以考虑把所有串倒过来插入 Trie，查询时也倒着往上查，复杂度 O(n2+∣∑len(stk)∣)O(n^2+|\sum \mathrm{len}(st_k)|)。
最后的方案可以开个数组记一下，然后将 DP 过程整个倒过来做一遍回溯即可。
复杂度可以做到 O(n2+∣∑len(stk)∣)O(n^2+|\sum \mathrm{len}(st_k)|)。

代码

这里实现的是最劣的 O(n3+nm)O(n^3+nm)，且由于对 ROIR 的阴影使用了双 Hash，代码冗长，常数巨大（但是也不用卡常），不建议观看。
CPP
constexpr int N(500+10),M(1e5+10),S(1e6+10);

namespace Hashs {
	constexpr int P1(1e9+7),P2(1e9+9);
	struct Hash {
		int a,b;
		Hash(int a=0,int b=0):a(a),b(b) {}

		friend Hash operator +(Hash A,Hash B) {
			return Hash(A.a+B.a>=P1?A.a+B.a-P1:A.a+B.a,A.b+B.b>=P2?A.b+B.b-P2:A.b+B.b);
		}
		friend Hash operator -(Hash A,Hash B) {
			return Hash(A.a-B.a<0?A.a-B.a+P1:A.a-B.a,A.b-B.b<0?A.b-B.b+P2:A.b-B.b);
		}
		friend Hash operator *(Hash A,Hash B) {
			return Hash((ll)A.a*B.a%P1,(ll)A.b*B.b%P2);
		}
		friend bool operator ==(Hash A,Hash B) { return A.a==B.a&&A.b==B.b; }
	} pw[N];
	const Hash B(131,13331);

	void Init(const int n=N-5) {
		pw[0]=Hash(1,1);
		FOR(i,1,n)pw[i]=pw[i-1]*B;
	}

	Hash constr(int len,char *s) {
		Hash res(0,0);
		FOR(i,1,len)res=res*B+Hash(s[i]-'a'+1,s[i]-'a'+1);
		return res;
	}
} using namespace Hashs;

int n,m,TYPE;

char pa[N];
int fa[N];
vector<int> g[N];

int w[M],len[M];
Hash h[M];

int self[N][N],Self[N][N];
int Fa_v_u[N][N],Fa_v_v[N][N];
ll f[N][N];

int top;
Hash st[N];

Hash query(int l,int r) { return st[r]-st[l-1]*pw[r-l+1]; }

void DP(int u) {
	f[u][0]=0,self[u][0]=0,Self[u][0]=0;
	FOR(i,1,n)f[u][i]=LINF,self[u][i]=0,Self[u][i]=i;
	if(u!=1)++top,st[top]=st[top-1]*B+Hash(pa[u]-'a'+1,pa[u]-'a'+1);
	for(int v:g[u]) {
		DP(v);
		static ll tmp[N];
		FOR(i,0,n)tmp[i]=LINF;
		FOR(i,0,n)if(f[u][i]<LINF)FOR(j,0,n)if(f[v][j+1]<LINF) {
			const int k(max(i,j));
			if(tmp[k]>f[u][i]+f[v][j+1])
				tmp[k]=f[u][i]+f[v][j+1],Fa_v_u[v][k]=i,Fa_v_v[v][k]=j+1;
		}
		FOR(i,0,n)f[u][i]=tmp[i];
	}
	static int mark[N];
	FOR(i,1,top)mark[i]=-1;
	FOR(i,1,m)if(len[i]<=top&&query(top-len[i]+1,top)==h[i]) {
		if(!~mark[len[i]]||w[i]<w[mark[len[i]]])mark[len[i]]=i;
	}
	FOR(i,1,top)if(~mark[i])FOR(j,0,i)if(f[u][i]>f[u][j]+w[mark[i]])
		f[u][i]=f[u][j]+w[mark[i]],self[u][i]=mark[i],Self[u][i]=j;
	if(u!=1)--top;
}

int St[N];
vector<tuple<int,int,int>> Ans;

void DFS(int u,int i) {
	St[++top]=u;
	if(self[u][i]) {
		int t(self[u][i]);
		Ans.push_back({St[top-len[t]],u,t}),i=Self[u][i];
	}
	int siz(g[u].size());
	DOR(p,siz-1,0) {
		int v(g[u][p]);
		DFS(v,Fa_v_v[v][i]),i=Fa_v_u[v][i];
	}
	--top;
}

signed main() {
	/*DE("Input");*/
	scanf("%d%d%d",&n,&m,&TYPE),Init();
	// check
	if(n==1) {
		puts("0");
		if(TYPE)puts("0");
		return 0;
	}
	// build
	FOR(i,2,n) {
		static char opt[3];
		scanf("%d%s",&fa[i],opt),g[fa[i]].push_back(i),pa[i]=*opt;
	}
	// hash
	FOR(i,1,m) {
		static char opt[S];
		scanf("%d%s",&w[i],opt+1),len[i]=strlen(opt+1);
		if(len[i]>n-1)continue;
		h[i]=constr(len[i],opt);
	}
	/*DE("DP");*/
	DP(1);
	if(f[1][0]>=LINF)return puts("-1"),0;
	printf("%lld\n",f[1][0]);
	if(TYPE) {
		DFS(1,0),printf("%d\n",(int)Ans.size());
		for(const auto &p:Ans)printf("%d %d %d\n",get<0>(p),get<1>(p),get<2>(p));
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...