相当抽象的一道题,看了好几遍题解才看明白的
题目大意:
给定字符串 \(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