要有光

标签：破题 leftarrow 光隐 void sky long 要有光

相当抽象的一道题，看了好几遍题解才看明白的

link

题目大意：

给定字符串 \(S_0\)（即绫的法术源），要求进行一下操作：

• 光归：对于\(T\)（\(T\) 为 \(S\) 的最大回文后缀），使 \(S \leftarrow T\)，消耗 \(A\) 时间

• 光辉： 对于\(T\)（\(T\) 为 \(S\) 的最大回文后缀且\(T\) 为 \(S\) 的子串），使 \(S \leftarrow T\)，消耗 \(B\) 时间

• 光隐： 对于\(T\)（\(T\) 为把 \(S\) 删去其长度相等且长度不大于 \(k\) 的前缀与后缀），\(S \leftarrow T\)，消耗 \(C\) 时间

• 光腾：对于\(T\)（\(T\)为在 \(S\) 两边分别加入 \(P\) 和 \(Q\) ），\(S \leftarrow T\)，消耗 \(D\) 时间

• 光戈：对于\(T（T = a + S ）\)，\(S \leftarrow T\)，在使用此变换之后，无法再使用其它类型的法术变换 ，消耗 \(E\) 时间

求阿绫最少需要多少次才能使 \(S=T\)

万物有灵，法术亦是如此。

思路：

什么破题什么破题什么破题什么破题什么破题什么破题

这题要当图论打

• 光归：直接连 \((i,fail_i,A)\)

void sky_regression(){//光归
	for(long long i=2;i<=cnt;i++){
		add(i,t[i].fail,A);
	}
}

• 光辉：连 \((i,fail_iB)\)

void sky_shine(){//光辉
	for(long long i=2;i<=cnt;i++){
		add(t[i].fail,i,B);
	}
}

• 光隐：处理一下\(i\)，连 \(k\) 条\((i,fa_i,C)\)

void sky_stealth(){//光隐
	for(long long i=2;i<=cnt;i++){
		long long x=t[i].fa;
		for(long long j=1;x && j<=k;x=t[x].fa,j++){
			add(i,x,C);
		}
	}
}

• 光腾：把 \(i\) 向 \(i\) 的子树中任一节点转移，代价为 \(D\)

  然后看了题解发现复杂度大到飞起，只好建立虚树（但是我没学）

  于是我就看了2个小时的OI-wiki差不多懂了但好像没那么懂

  每个点建立虚点，能且只能以\(0\)的代价向子的节点转移

  连\((i^‘,i,0)\)和\((i,i^`,D)\)即可

void sky_feiteng(){//光腾
	for(long long i=2;i<=cnt;i++){
		add(i+cnt,i,0);
	}
	for(long long i=2;i<=cnt;i++){
		add(i,i+cnt,D);
	}
	for(long long i=2;i<=cnt;i++){
		if(t[i].fa>1){
			add(t[i].fa+cnt,i+cnt,0);
		}
	}
}

• 光戈：由于使用后不能使用其他操作，所以单独分开

接下来建回文自动机，因为我不会所以去抄了一个，这题就当练图论了

然后跑一遍堆优化dij结合DP转移就行

标签：破题,leftarrow,光隐,void,sky,long,要有光
From： https://www.cnblogs.com/LuoTianYi66ccff/p/17773243.html