MX-S5 题解

A. 王国边缘

题目链接

见到循环结构，先把下标转成从 \(0\) 开始，以方便用同余描述位置。

倍增。用二元组来表示位置：\((u, v)\) 表示第 \(u\) 个循环节的第 \(v\) 个位置。设 \(f(i, j)\) 表示从位置 \((0, i)\) 开始跳 \(2^j\) 次以后的位置。假设已经可以初始化 \(f(i, 0)\)，考虑转移：

下面考虑怎么计算 \(f(i, 0)\)。正难则反，设 \(pre_i\) 表示 \(i\) 之前的最近的 \(1\) 的位置（在循环意义下，并且可以是 \(i\) 本身）。这是容易 \(O(n)\) 计算的。然后我写了一个巨复杂的分讨，呃呃。反正能算。

计算答案时直接倍增。最终答案为 \(un + v + 1\)。注意二元组的第一维可以取模（且必须取模）。

int solve(i64 s, i64 t)
{
    s--;
    i64 u = s / n; int v = (int)(s % n);
    for(int i = 0; (1 << i) <= t; i++)
    {
        if(t & (1ll << i))
        {
            u = (u + f[v][i].u) % MOD;
            v = f[v][i].v;
        }
    }
    return (int)((u * n + v + 1) % MOD);
}

B. 买东西题

题目链接

学到新东西了：反悔贪心。

先把物品按原价升序排列，把优惠券按 \(w\) 升序排列。设 \(g_i\) 表示第 \(i\) 个物品使用的优惠券的编号（如果不用优惠券，那么 \(g_i = 0\)，或者别的任意的东西）。考虑从前往后确定每个物品的 \(g\)。

贪心的主要问题在于局部最优解可能不是全局最优解。也就是说，如果给前 \(x\) 个物品都确定了优惠券，并且知道此时前 \(x\) 个物品的花费最小，在全局的最优解中，前 \(x\) 个物品的 \(g\) 也可能要改变。而反悔贪心解决了这个问题：即使先前确定的 \(g\) 在全局的视角中不是最优的，我们也可以“撤销”它。这样我们只要一直保持局部的最优性即可。到最后局部扩展到整体时，局部最优解就是全局最优解。

下面具体分析这个问题。

假设已经考虑到第 \(i\) 个物品。有 \(3\) 种方案来购买它：

1. 以折扣价购买。
2. 使用某个未被使用过的优惠券。
3. 使用某个已经被用过的优惠券。

（显然我们不会以原价购买。）

分析第 3 种情况。首先，如果两个物品用两张优惠券，如果可以交换优惠券，总花费不会改变。所以不用考虑 \(i\) 从前面拿一张优惠券，又塞一张优惠券给前面的情况。

假设用的优惠券是 \(g_j\)。那么 \(j\) 没有优惠券了，花费从 \(a_j - v_{g_j}\) 变为 \(b_j\)，而 \(i\) 的花费是 \(a_i - v_{g_j}\)。这样对总花费的影响是 \(\Delta = (a_i - v_{g_j}) + b_j - (a_j - v_{g_j}) = a_i - (a_j - b_j)\)。效果就相当于 \(i\) 用了一张减价 \(a_j - b_j\) 的优惠券。

用一个大顶堆来维护当前可用的优惠券。如果 \(i\) 用了优惠券，那么就往堆里加入一个价格为 \(a_i - b_i\) 的优惠券，以实现反悔操作。

每次确定当前物品 \(i\) 用哪张优惠券时，如果没有可用的优惠券，或者减价最多的优惠券也不如直接按折扣价买，那就按折扣价买；否则使用折扣力度最大的优惠券，并加入一张价格为 \(a_i - b_i\) 的优惠券。

sort(a.begin(), a.end()), sort(b.begin(), b.end()); // a 表示物品，b 表示优惠券
priority_queue<int> heap;
int p = 0; i64 ans = 0;
for(auto pr: a)
{
    while(p < m && pr.fi >= b[p].fi)
        heap.push(b[p++].se);
    int add;
    if(heap.empty() || pr.fi - pr.se > heap.top())
        add = pr.se;
    else
    {
        add = pr.fi - heap.top();
        heap.pop();
        heap.push(pr.fi - pr.se);
    }
    ans += add;
}

C. IMAWANOKIWA (Construction ver.)

题目链接

牛逼分讨题。拿个特殊性质的 12 分跑路就差不多得了。正赛应该不会有这种玩意吧……

D. 魔法少女们

不会计数。