题解：P15586 [KTSC 2026] 五万酱汁 / 50,000 Sauces

Redshift_Shine · 2026-03-04 19:28:21 · 题解

这题大概是来搞笑的。

在选择性忽略题目条件的情况下，不难通过暴力的子集容斥做到 O(3^N)，不过这不符合题目要求且显然没有任何用处。

在上述做法的基础上，不难发现只需要枚举大小不大于 3 的子集。查询量级 O(n^3)，符合单次查询集合大小限制，但一次只处理一种显然太浪费了，而且仍然无法通过本题。

注意到两个反常的限制，n\ge 6 且询问大小 |Y|\le \lceil\frac{N}{2}\rceil+1。猜测解法与 6 有关。

不难发现，根据查询结果的意义，可以任意对元素进行合并，且不会影响对答案的求解。

尝试将所有元素尽可能平均地分为 6 份。在最坏情况下，N\equiv 3\pmod 6，三组的最大和为 \frac{N-3}{2}+3，而 |Y|\le \lceil\frac{N}{2}\rceil+1=\frac{N-1}{2}+2=\frac{N-3}{2}+3，刚好达到单词查询限制上界。

同样的，在此条件下，暴力查询分组的总次数为 \binom{6}{1}+\binom{6}{2}+\binom{6}{3}=6+15+20=41，刚好达到询问次数上界。

直接实现该方法即可。时间复杂度 O(n)。

#include "sauce.h"
#include <vector>

using std::vector;

const int T = 6;

int sht1[T], sht2[T][T], lq[T], res;
vector<int> vec[T], tmp;

int solve(int N)
{
    for (int i = 0; i < T; i++)
        lq[i] = N / T;
    for (int i = 0; i < N % T; i++)
        lq[T - i - 1]++;
    for (int i = 0, t = 0; i < T; i++)
        for (int j = 0; j < lq[i]; j++)
            vec[i].emplace_back(t), t++;

    // Phase 1
    for (int i = 0; i < T; i++)
        sht1[i] += query(vec[i]), res += sht1[i];

    // Phase 2
    for (int i = 0; i < T; i++)
    {
        for (int j = i + 1; j < T; j++)
        {
            tmp = vec[i];
            tmp.insert(tmp.end(), vec[j].begin(), vec[j].end());
            sht2[i][j] = query(tmp) - sht1[i] - sht1[j];
            res += sht2[i][j];
        }
    }
    for (int i = 0; i < T; i++)
    {
        for (int j = i + 1; j < T; j++)
        {
            for (int l = j + 1; l < T; l++)
            {
                tmp = vec[i];
                tmp.insert(tmp.end(), vec[j].begin(), vec[j].end());
                tmp.insert(tmp.end(), vec[l].begin(), vec[l].end());
                res += query(tmp) - sht1[i] - sht1[j] - sht1[l] - sht2[i][j] - sht2[i][l] - sht2[j][l];
            }
        }
    }
    return res;
}