题解：P16541 [EGOI 2026] 饼干 / Biscuits

lailai0916 · 2026-08-31 01:08:40 · 题解

题意简述

两人从栈顶分饼干。每回合 Aurora 先禁止一个拿取数量，Bianca 再选择另一个合法数量；Aurora 吃掉所选数量的饼干，若仍有剩余，Bianca 再吃掉下一块。求最优博弈下 Bianca 的总重量，并支持单点修改饼干重量。

解题思路

所有饼干最终都会被其中一人吃掉，总重量固定。Aurora 最大化自己的幸福度，等价于最小化 Bianca 的幸福度。

设当前剩余后缀为 [i,n-1]，Bianca 在最优博弈下能得到 b_i。若 Bianca 选择 Y=y<n-i，Aurora 先吃掉前 y 块，Bianca 随后吃到第 i+y 块，并进入后缀 [i+y+1,n-1]。这个选择对应的收益为：

若 y=n-i，Aurora 吃完全部剩余饼干，Bianca 的收益为 0。

Aurora 可以禁止任意一个合法的 y。禁止范围外的数不会排除任何选择，必然不会更优。Bianca 会在剩余收益中取最大值，所以 Aurora 会删去收益多重集中的一个最大值。即使最大值出现多次，也只能删去其中一次。因此，b_i 就是全部候选收益按重数计算的次大值。

从栈底向栈顶逐块加入饼干。设当前候选收益多重集的最大值和次大值分别为 p,q，其中 p\ge q。在前面加入一块重量为 x 的饼干时，新增的候选收益是：

原有候选收益仍然存在。因为 x>0，有 q+x>q，所以新的最大值与次大值就是 p 和 q+x 按大小排序后的结果。

只维护两者之差：

加入重量 x 后，新的差为：

初始令 p=q=0，相当于候选多重集中有两个零。对第一个非空后缀，新增正收益后，次大值仍为零，正好符合游戏结果。多出的零在之后也不会进入前两名之外产生影响。

每次加入重量 x，p+q 都增加 x。处理完整个栈后：

Bianca 的答案是较小值 q，因此：

每块重量 x 对应一个差值转移函数：

初始 d=0，且所有 x\le50。若转移前 0\le d\le50，转移后仍有 0\le|d-x|\le50。因此，可以用长度为 51 的数组完整保存任意一段饼干对差值的复合函数。

线段树按原数组顺序建立。对区间 [l,r]，游戏中的处理顺序是从栈底向栈顶，也就是先处理右半段，再处理左半段。若左右儿子的复合函数分别为 L,R，父结点函数为：

代码使用迭代线段树的叶子布局。超过 n 的补齐叶子保存恒等函数，不会影响根的复合结果。单点修改后，只需从对应叶子向上重算。函数值始终不超过 50，可以使用 unsigned char 存储。

建树时间复杂度为 O(nV)，每次修改为 O(V\log n)，空间复杂度为 O(nV)，其中 V=50。

正确性证明

对任意后缀，Bianca 的每个合法选择都唯一对应一个候选收益。Aurora 只能禁止一个选择，并希望 Bianca 在其余选择中的最大收益尽量小，所以结果恰为候选多重集的次大值。该结论同时覆盖最大值并列的情况。

从栈底向上加入重量 x 时，旧候选全部保留，唯一新增候选为旧次大值 q 加 x。它严格大于旧 q，所以新前两大值恰为 p 与 q+x。由此得到的差值转移 d\gets|d-x| 与真实最大、次大值更新完全等价。又因为两者之和每次增加当前重量，最终公式能够从总重量和差值唯一恢复 Bianca 的收益。

每个线段树叶子准确表示单块转移。父结点先应用右半段，再应用左半段，与从栈底到栈顶的实际处理顺序一致。根据区间长度归纳，根结点表示完整饼干栈的差值复合函数。修改后重算根链仍保持这一性质，所以每次输出都等于对应局面的最优 Bianca 幸福度。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
const int M=262145;
const int V=50;
int n,q,s,sum,a[N];
unsigned char f[M][V+1];
void set_leaf(int u,int x)
{
    for(int i=0;i<=V;i++)f[u][i]=abs(i-x);
}
void push_up(int u)
{
    for(int i=0;i<=V;i++)f[u][i]=f[u<<1][f[u<<1|1][i]];
}
void update(int p)
{
    int u=s+p;
    set_leaf(u,a[p]);
    while(u>1)
    {
        u>>=1;
        push_up(u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    s=1;
    while(s<n)s<<=1;
    for(int i=0;i<s;i++)
    {
        if(i<n)
        {
            cin>>a[i];
            sum+=a[i];
            set_leaf(s+i,a[i]);
        }
        else
        {
            for(int j=0;j<=V;j++)f[s+i][j]=j;
        }
    }
    for(int i=s-1;i;i--)push_up(i);
    cout<<(sum-f[1][0])/2<<'\n';
    while(q--)
    {
        int p,z;
        cin>>p>>z;
        sum+=z-a[p];
        a[p]=z;
        update(p);
        cout<<(sum-f[1][0])/2<<'\n';
    }
    return 0;
}