raywu的博客

博客

QOJ5095 九王唱 做题记录

2024-10-09 16:17:24 By raywu

Task

$n$ 个人 $n + 1$ 件物品,每个人 $i$ 对一件物品 $j$ 有一个喜欢程度 $a_{i, j}$。

一轮游戏从 $i$ 开始,按 $i, i + 1, \cdots, n, 1, 2, \cdots, i - 1$ 的顺序每人选走一个物品,每个人都希望他对最后剩下的物品的喜欢程度最大,答案为最后剩下的物品是哪个。对于每个 $i \in [1, n]$ 都求出答案。

对于每个 $i$,$a_{i, 1} \sim a_{i, n + 1}$ 为 $1 \sim n + 1$ 的排列。

$n \le 5000$。


Solution

发现正着想没什么思路,倒过来思考。

为了方便,记 $f_{i, j}$ 表示第 $i$ 个人喜欢程度为 $j$ 的物品编号,即 $f_{i, a_{i, j}} = j$。

假设从第 $i$ 个人开始选物品。

首先考虑最后一个人 $i - 1$。由于轮到他的时候只剩两个物品可选,那么他一定会毙掉他更讨厌的那个物品 $x_{i - 1}$。

再考虑倒数第二个人 $i - 2$。考虑分类讨论如下:

  • 如果剩下的三个物品中 $i - 2$ 号人最讨厌的不为 $x_{i - 1}$,那么他会毙掉他最讨厌的物品 $x_{i - 2}$。

  • 否则,他和最后一个人最讨厌的物品是同一个物品,那么他会选择不毙掉 $x_{i - 1}$,留给最后一个人去将它选走,自己选择倒数第二讨厌的物品。这样的话他就可以保证最后剩下的物品(在还剩下的 $3$ 个物品中)是他最喜欢的。

想到这里,我们可以发现,最后一个人 $i - 1$ 选走的物品一定是他初始最讨厌的物品 $f_{i - 1, 1}$,因为前面的人即使最讨厌的物品也是它也会把该物品留给 $i - 1$ 来选。同理,若 $f_{i - 2, 1} \neq f_{i - 1, 1}$,$i - 2$ 选走的是 $f_{i - 2, 1}$,否则为 $f_{i - 2, 2}$。

于是我们便得出了暴力思路:倒着决策,当前人选走还未被选过的他最讨厌的物品。

暴力是 $O(n^3)$ 的,理论上无法通过,但跑得飞快过了暴力 Code

接下来考虑优化。

我们以第 $n$ 个人为例:考虑第一轮从 $1$ 开始操作,第二轮从 $2$ 开始操作,由于我们是倒着决策,那么 $n$ 的决策优先权不断降低。也就是说,假设第一轮 $n$ 最终选了 $f_{n, k_1}$ 这件物品,那么第二轮时 $n$ 选走的物品 $f_{n, k_2}$ 一定满足 $k_1 \le k_2$。

所以我们考虑开一个 $lst_i$ 记录第 $i$ 个人上一轮选择的物品为 $f_{i, lst_i}$,那么当前轮时枚举 $i$ 的决策直接从 $lst_i$ 开始枚举即可。当然,如果 $i$ 是当前轮第一个决策的人,那么强制让他从 $f_{i, 1}$ 开始选。

这样的话每个 $f_{i, j}$ 最多只会被遍历一次,复杂度被降到了 $O(n^2)$,可以通过。正解 Code

Comments

zty02281128
%%%%%%
  • 2024-10-09 16:19:23
  • Reply
raywu
zty02281128 %%%
  • 2024-10-09 16:20:53
  • Reply
union_of_britain
niubi!!
  • 2024-11-01 20:28:23
  • Reply

Post a comment

You can use @mike to mention the user mike.

If you wish to input the '@' character, please use @@