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

pxb0801 · 2026-03-04 19:36:35 · 题解

观察题目所给要求：每次询问集合的大小大约为总大小的一半。先考虑 |S|=2，想到将集合分为 4 部分，先询问单个部分，再询问两个部分，容斥一下即可。

拓展到 |S|\le 3 也是容易的。将集合分为 6 部分，先询问单个部分，再询问两个部分，再询问三个部分，容斥一下。

讲一下容斥细节。

对于六个部分 a,b,c,d,e,f，询问单个部分可以获得元素仅在这一个部分中的数量。询问两个部分可以获得元素在这两个部分中的数量，减去两个单个部分的答案就是交叉部分的答案。如询问 a\cup b，得到的答案是 |S\mid S\subseteq a\cup b|。减去询问 a 和 b 的答案，就得到了 |S\mid S\subseteq a\cup b,S\cap a \neq\varnothing,S\cap b\neq\varnothing|。

三个部分交叉的答案用三个部分的询问减两个部分的再减一个部分的即可。不再赘述，可以自行画图理解，详见代码。

#include<vector>
using std::vector;
int query(std::vector<int>);
using namespace std;
int solve(int n){
    vector<int> a[6];
    int ans=0,cnt1[6]={0},cnt2[36]={0};
    for(int i=0;i<n;i++){
        a[i%6].push_back(i);
    }
    for(int i=0;i<6;i++){
        ans+=cnt1[i]=query(a[i]);
    }
    for(int i=0;i<6;i++){
        for(int j=i+1;j<6;j++){
            vector<int> v;
            for(int x:a[i]) v.push_back(x);
            for(int x:a[j]) v.push_back(x);
            ans+=cnt2[i*6+j]=query(v)-cnt1[i]-cnt1[j];
        }
    }
    for(int i=0;i<6;i++){
        for(int j=i+1;j<6;j++){
            for(int k=j+1;k<6;k++){
                vector<int> v;
                for(int x:a[i]) v.push_back(x);
                for(int x:a[j]) v.push_back(x);
                for(int x:a[k]) v.push_back(x);
                ans+=query(v)-cnt2[i*6+j]-cnt2[i*6+k]-cnt2[j*6+k]-cnt1[i]-cnt1[j]-cnt1[k];
            }
        }
    }
    return ans;
}