Codeforces Round #693 (Div. 3)_codeforces round 693

作者：小小林熬夜学编程 | 2024-02-09 17:48:58

踩

codeforces round 693

D：
题意：两个人取数，A取偶数能加分，B取奇数能加分，问最优情况下分数情况？
显然取走别人的虽然不能让自己加分，但是可以让对方减分，因此相对分数是加的，从大到小按顺序取即可。
E：
题意：给n个有序对，问每个有序对是否存在另一个有序对 $a_i<a_j$ && $b_i<b_j$ or $a_i<b_j$ && $b_i<a_j$ ?
首先将每个有序对转化为 $b\leq a$ 的形式，按 $a$ 排序，取前缀最小 $b$ ，判断前缀最小 $b$ 是否符合要求即可。
F：
题意： $2 * n$ 的的网格图，可以放 $1 * 2$ 或 $2 * 1$ 的矩形，但是有的位置不能放，问是否能塞满网格图？
可以按存在不能放的位置分段来看，分情况讨论即可。
G：
题意：给一个有向图，从一个点出发可以往那些比1距离远的点走，但是只能往距离1更近的节点的走一步，问从每个点出发能够距离1最近的距离。
考虑树dp，每个节点的状态取决于距离1更远且与该节点相连的点，因此可以将每个节点按到1的距离从大到小排序后转移状态，每个节点的dp值取决于其子节点的距离或dp值。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/72467