Codeforces

Round #532 (Div. 2)

D. Dasha and Chess

题目大意：交互题。一个 \(999\times 999\) 的棋盘上，有一个白色棋子和 \(666\) 个黑色棋子。先手执白，每次可以八连通走一步，后手每次可以选择一个棋子随便放到一个空位置。如果白棋和某个黑棋同行/同列，那么先手胜。

题解：把白棋移动到中心。然后往有最少黑棋的象限相反方向移动。在这个方向上可以移动 \(499\) 步，这个方向以及相邻两个象限至少有 \(666\times \frac{3}{4} > 499\) 个黑棋，由鸽巢原理白棋一定获胜。

E. Andrew and Taxi

题目大意：给你一个有向图，让你选择一些边反向，使得图没有有向环。最小化最大的边权，边的数量没有要求。

题解：二分最小的最大边权 \(m\)，使得删掉权小于等于 \(m\) 的边之后是个 DAG。删掉的边中如果有从拓扑序大的指向拓扑序小的边，将它反向。

Q：最小化边权和怎么做呢?