ABC261Ex Game on Graph

给定一张带权有向图, 两个人玩游戏: 有一棋子, 初始在给定点上, A先手, 轮流一沿当前点的出边将棋子移至另一点, 无法移动则游戏结束. A 想让经过边的边权最小, B 想让其最大. 双方以最优策略游玩, 要求出最终得分, 或者报告游戏不会结束.

$n,m\le2\times10^5$

记 $F(0,u),F(1,u)$ 为当前 A/B 要操作, 棋子在点 $u$ 的得分. 若 $u$ 无出边, 则 $F(u,0)=F(u,1)=0$. 否则:

$$F(0,u)=\min_{u\stackrel{w}{\rarr} v} F(1,v)+w\\ F(1,u)=\max_{u\stackrel{w}{\rarr} v} F(0,v)+w\\ $$

考虑在反图上应用 dijkstra 算法: $dis(t,u)=F(t,u)$, 对于 $F(0,u)$, 正常转移; 对于 $F(1,u)$, 每次转移到其的时候, 只更新 $dis$, 不加入队列, 仅当其的所有出边处理完了才加入优先队列 (注意到若 $v\rarr u$, 必然有 $F(1,u)>F(0,v)$, 故 dijkstra 的 $dis$ 转移后要更大的限制可以满足).

时间复杂度 $O(m\log m)$

CF568C New Language

使用前 $m$ 种字母, 每种字母有一个类型 (总共 $2$ 种类型, 要求构造一个长为 $n$ 的字符串 $A$, 其字典序必大于等于另一给定字符串 $S$, 且满足若干条限制: $(i,x,j,y)$: 若 $A_i$ 有类型 $x$, 则 $A_j$ 要有类型 $y$ .

$n\le 200, m\le 26$

对于限制, 考虑使用 2-SAT: $n$ 个变量 $V_i$, 为了方便, 记 $V_{it}$ 表示 $A_i$ 有类型 $t$, 对于 $(i,x,j,y)$, 连边 $V_{ix}\rarr V_{jy}$ (同时有 $V_{j,\lnot y}\rarr V_{i,\lnot x}$ ).

考虑从小到大枚举每一位: 枚举填什么字母 (相同类型的字母只用考虑满足字典序要求时最小的, 除了下文所说的特殊情况), 判断是否产生矛盾 (若为类型 $t$, 那么 $V_{i,\lnot t}\rarr V_{i,t}$), $O(n)$ 暴力判断即可.

注意特殊情况: 可能前面填了之后后面不存在让字典序不大于 $S$ 的填法, 考虑回退, 设前面 $i$ 位 $S(1..i)=A(1..n)$, 考虑让 $S(i)$ 增大, 那么后面就不用再受字典序要更大的限制. 注意到每个 $i$ 最多回退一次, 故最多回退 $O(n)$ 次.

时间复杂度 $O(n^3)$