做题记录 25.9.1
szt100309
·
·
个人记录
\blue\odot AT_abc209_e [ABC209E] Shiritori
取前缀和后缀分别建立两点，一个字符串为一条边
令 f_u 表示 u 为先手时的情况，为 -1 表示先手败，0 表示平，1 表示胜，本题转移为若后继都是必败态则当前状态必胜，反之必败，特别地无出边的 f_u=1，若为 \text{DAG} 则直接在反图上转移即可，若存在环，且环存在至少一条出边指向 f_v=1，则该点为 -1，由此推出剩余点，若不存在出边或出边都是 -1，则环上点都是 0
在反向图上拓扑排序时，设目前要扩展 u，设 u\to v 且 f_v=0（初始令 f_\ast=0），若 f_u=1，则 f_v=-1 并将 v 加入队列，若 f_u=-1 且是 v 最后一条入边，则 f_v=1 并将 v 加入队列
时间复杂度 O(n+\sum |s_i|)
代码
参考
\blue\odot P3530 [POI 2012] FES-Festival
先按差分约束建边，求出 \text{SCC}，显然 \text{SCC} 之间独立，每个 \text{SCC} 内用 \text{Floyd} 求出最短路，若存在 ds_{i,i}<0 则无解，否则这一 \text{SCC} 的贡献为 \text{SCC} 内最短路的最大值加一
时间复杂度 O(n^3)
代码
参考