2024牛客多校7&8

7

通读题解之后决定把能看懂的题目补了（毕竟能看懂的也不多，某些算法听都没听过 QwQ）

A Maximum Subarray Sum (A)

（出题人解法没看明白）

解法2的切入点类似之前某场div2的D题（题解传送门），将操作过程视为选出 \(\lfloor n/k\rfloor\) 个长度为 \(k\) 的子序列，答案序列中大于 \(k\) 的部分暂时与舍弃部分等价，即最后舍弃的数字下标满足 \(i' = i\space mod\space k\). 设 \(dp[i][x][y][p]\) 表示到 \(i\) 位置，换走 \(x\) 个数、换入 \(y\) 个数，当前选择状态为 \(z\)（选或不选）时的最大和，每个计入答案的数可能存在按序选入/中途换入两种选择方式，同理未计入答案的数也存在直接抛弃/换出两种可能。当前数被选中时，由于子序列长度至少为 \(k\)，为避免出现间断点，\(dp[i][x][y][1]\) 只能由 \(dp[i - k + 1][x][y][1]\)（长度为 \(k\) 的子序列）或 \(dp[i - 1][x][y][1]\)（答案序列中大于 \(k\) 的部分）转移而来，前者需要从 \(0\) 到 \(m\) 枚举换出数字的数量，其他所有情况则可以 \(O(1)\) 转移。利用前缀和与set之类的容器处理换出后的序列最大值，整体复杂度可优化至 \(nm^3\) 左右。特别地，当 \(i\space mod\space k = k - 1\) 时，由于舍弃的数不可能超过 \(k - 1\) 个，该位置上的数字不能被直接抛弃，只进入 \(0\) 至 \(m\) 的循环、讨论可能存在的换出情况。代码还是借鉴其他队答案才写明白的，所以没放这里了 TAT

I Fight Against the Monster (I)

题解思路是二分答案，不过不用二分也行。\(h\leq m\) 时显然答案为 \(h\)，对于 \(h > m\) 的情况，若生产出的 \(k\) 台新机器仍不足以将怪物杀死，可以选择直接补充与剩余血量相等的机器数目（\(h'\leq m - k\) 时），或补充 \(m - k\) 台机器至恰好足以生产新机器，依此思路可 \(O(1)\) 计算答案，代码如下：

    if(h <= m) printf("%lld\n", h);
    else if(m <= k) printf("%lld\n", m);
    else {
        ll sum = h - m;
        if(sum <= k) printf("%lld\n", m);
        else {
            ll cnt = sum / m, x = sum % m;
            if(x >= k) printf("%lld\n", m + cnt * (m - k) + (x - k));
            else printf("%lld\n", m + cnt * (m - k));
        }
    }

8

上周四不在家所以没打，后来自己写的时候各种卡题，难过）

A Haitang and Game (A)

事实上A题并不是一道博弈题，最终序列中加入的所有 \(d\) 是固定的，不存在任何可能改变胜负的博弈策略。具体而言，若序列中 \(d\)（本身不存在于序列中）的倍数有 \(a_i,a_j,...\)，且 \(gcd(a_i,a_j,...) = d\)，则 \(d\) 必然会被加入。数据范围 \(a_i\leq 10^5\)，遍历 \(1\) 至 \(a_{max}\)，枚举倍数判断其是否为合法的 \(d\)，由调和级数得整体复杂度 \(nloga_{max}\).