口胡 P16454 [APIO 2026] Scallion Pancake Party 题解

Bingxiu2 · 2026-05-15 02:14:34 · 题解

好简单啊，看两眼就会了。不过由于暂无数据我只能口胡（也就是说我无法确保这是正确的做法），有了数据喊我来补代码。

首先如果 K>1，直接把传进来的参数减去 K-1，下面默认 K=1。同时，我们把传进来的 r 直接忽略掉。

这里给出一个 n \ge 6 的时候只需要看前 \frac{n^2+7n-8}{2} 张饼的做法。n \le 5 的情况去看别的题解，如果我能把这个做法优化到 n \le 5 能过我再补。

1. 房间内的客人的策略

首先如果无法确定 i 的值，那么任何信息都没用，所以考虑用前 2n-1 张饼来确定 i。

具体来说，直接把第一张自己能吃且编号在 [0,2n-2] 范围内的饼吃掉。由于自己最多只有 n 张不能吃的，所以 i \in [0,n-2] 的客人都能吃，则每个客人的 i 就是自己来之前编号为 [0,2n-2] 被吃掉的饼数。

然后我们考虑让以后的所有人都知道 P_i 的值：

如果 i=n-1，根本不饿吃什么吃，反正都能还原 P_0 \sim P_{n-2} 了，剩下的自然就是 P_{n-1}。下设 0 \le i \le n-2。

先把编号为 0 \sim i-1 的 i 个客人用于传递信息的位忽略掉（具体怎么知道他们用了哪些位传递信息下面会说）。

记 a_i 为 i 用于传递信息的第一位下标（也就是忽略掉前面 i 个客人用于传递信息的位后的第一张饼的下标）。

考虑从 a_i 开始，不停吃，直到吃了 P_i 片后的下一片或遇到 f=P_i 导致吃不了为止。

设第一片没吃的编号为 e_i，且 l_i=e_i-a_i，则 l_i \le P_i，且 l_i=P_i 或 f_{e_i}=P_i。

• 若 l_i=n-1，则传递信息在 e_i-1 处结束，也即 a_{i+1}=e_i，消耗 l_i=n-1=P_i 位传递信息；
• 否则若 l_i \ge f_{e_i}，则若 l_i<P_i 会导致 P_i>l_i \ge f_{e_i}=P_i 导出矛盾，故必有 l_i=P_i，传递信息在 e_i 处结束，也即 a_{i+1}=e_i+1，消耗 l_i+1=P_i+1 位传递信息；
• 否则 l_i<f_{e_i}：
  • 若 l_i=P_i 且 f_{e_i}>P_i，则：
  • 若 f_{e_i+1} \neq f_{e_i}，则不吃 f_{e_i+1}；
  • 否则 f_{e_i+1}=f_{e_i}>P_i，吃掉 f_{e_i+1}。
  • 否则 l_i<P_i 且 f_{e_i}=P_i，则：
  • 若 f_{e_i+1} \neq f_{e_i}，则 f_{e_i+1} \neq f_{e_i}=P_i，吃掉 f_{e_i+1}；
  • 否则 f_{e_i+1}=f_{e_i}=P_i，不吃 f_{e_i+1}。
  • 这部分的四种情况均可通过 f_{e_i+1} 与 f_{e_i}、f_{e_i+1} 是否被吃来区分开，则可以确定 l_i 与 f_{e_i} 中哪个是 P_i，传递信息在 e_i+1 处结束，也即 a_{i+1}=e_i+2，消耗 l_i+2 \le \min(n,P_i+2) 位传递信息。

总共至多消耗 2n-1+\sum\limits_{x=1}^{n-1} \min(n,x+2)=3n-1+\frac{n^2+n-6}{2}=\frac{n^2+7n-8}{2}

那么根据以上的传递信息方法，很容易得到以下从前往后依次还原 P_j 的方法：

首先从 a_j 开始，找到第一片没被吃或下标为 a_j+n-2 的饼，设其下标为 z_j，且 v_j=z_j-a_j。

• 若 v_j=n-2 且 f_{z_j} 被吃了，则 P_j=n-1 且 a_{j+1}=z_j+1；
• 否则若 v_j \ge f_{z_j}，则 P_j=v_j 且 a_{j+1}=z_j+1；
• 否则 a_{j+1}=z_j+2：
  • 若 f_{z_j} \neq f_{z_j+1}：
  • 若 f_{z_j+1} 没被吃，则 P_j=v_j；
  • 否则 P_j=f_{z_j}；
  • 否则 f_{z_j}=f_{z_j+1}：
  • 若 f_{z_j+1} 没被吃，则 P_j=f_{z_j}；
  • 否则 P_j=v_j。

2. 留在外面的客人的策略

根据 1. 中的还原方法还原 P_0 \sim P_{n-2}，然后求出 P_{n-1} 即可。