题解：P17142 [NOI 2026] 布丁（暂无数据）

· · 题解

以下为 Q\le 3 的做法。

首先注意到可以直接询问 [1,n] 中的每一个数来确定 x 到底是多少，然后发现假如已知 x\in S，那么直接询问 S 中的每一个数即可以 |S| 的代价确定 x。

发现这样子太浪费询问次数的限制了，注意到我们可以用前几次询问缩小 S，然后再用一次询问确定 x。

考虑随机出若干个询问，取最优的一个，然后目前的 S 就会被划分为若干等价类，定义一个询问的区分度为划分出的等价类的最大大小，我们取区分度最小的那个询问，然后再问下去。

考虑现在本地随出一组较优的构造，对于第一次询问，找到一个区分度较小的询问，可以在本地先跑出来，然后对于该询问划分出的每一个等价类，都搜出一个询问使得总代价 \le 35，对于每一个等价类采用不同的随机策略，即可在较快的时间内跑出解。

我们的随机策略有若干种，一种是直接随机，一种是随机出一些质数的倍数，一种是随机出一个等差数列再随机扰动，这几种随机方法可以覆盖大部分情况。

然后实测每次询问的序列长度为 6 时最优，一方面有足够的区分度，一方面不会导致前几次询问代价太大而搜不出来解。

以下为搜第一次询问的代码。

#include<bits/stdc++.h>

using namespace std;

int Gcd[4505][4505];
vector<int>E[100005];
void init() {
    for(int i=0;i<=4500;i++) {
        Gcd[i][0]=Gcd[0][i]=i;
        for(int j=1;j<=i;j++) Gcd[i][j]=Gcd[j][i]=Gcd[j][i-j];
    }
}
void calc(vector<int>A) {
    vector<int>T;
    srand(time(0));
    int minn=1e9,Y=6;
    while(1) {
        T.clear();
        for(int j=1;j<=Y;j++) T.push_back(1*(rand()%(4500/1)+1));
        int maxn=0;
        for(auto j:A) {
            vector<int>now=T;
            now.push_back(j),sort(now.begin(),now.end());
            int sum=0;
            for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
            E[sum].push_back(j),maxn=max(maxn,(int)E[sum].size());
        }
        if(maxn<minn) {
            minn=maxn;
            cout<<maxn<<"\n";
            for(auto i:T) cout<<i<<",";
            cout<<"\n----------------------------\n";
        }
        for(auto j:A) {
            vector<int>now=T;
            now.push_back(j),sort(now.begin(),now.end());
            int sum=0;
            for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
            E[sum].clear();
        }
    }
}
int main() {
    init();
    vector<int>A;
    for(int i=1;i<=3000;i++) A.push_back(i);
    calc(A);
    return 0;
}

可以搜到一组较优的构造

145
1015,2550,1450,1995,3225,630

以下为根据第一次询问得到的若干等价类所搜到的构造的代码。

#include<bits/stdc++.h>

using namespace std;

int Gcd[4505][4505];
vector<int>E[100005],F[100005];
void init() {
    for(int i=0;i<=4500;i++) {
        Gcd[i][0]=Gcd[0][i]=i;
        for(int j=1;j<=i;j++) Gcd[i][j]=Gcd[j][i]=Gcd[j][i-j];
    }
}
bool check(int x) {
    for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
    return 1;
}
void calc(vector<int>A) {
    vector<int>T;
    srand(time(0));
    int minn=1e9,Y=6;
    while(1) {
        T.clear();
        for(int j=1;j<=Y;j++) {
            if(rand()&1) T.push_back(j*100-rand()%20);
            else T.push_back(j*100+rand()%20);
        }
        int maxn=0;
        for(auto j:A) {
            vector<int>now=T;
            now.push_back(j),sort(now.begin(),now.end());
            int sum=0;
            for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
            E[sum].push_back(j),maxn=max(maxn,(int)E[sum].size());
        }
        for(auto j:A) {
            vector<int>now=T;
            now.push_back(j),sort(now.begin(),now.end());
            int sum=0;
            for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
            E[sum].clear();
        }
        if(maxn<minn) {
            minn=maxn;
            cout<<A.size()<<" "<<minn<<"\n";
        }
        if(maxn<=35-Y-6) {
            for(auto i:T) cout<<i<<",";
            cout<<"\n";
            break;
        }
    }
}
void Calc(vector<int>A) {
    vector<int>T;
    T={1015,2550,1450,1995,3225,630};
    for(auto j:A) {
        vector<int>now=T;
        now.push_back(j),sort(now.begin(),now.end());
        int sum=0;
        for(int k=0;k<=5;k++) sum+=Gcd[now[k]][now[k+1]];
        F[sum].push_back(j);
    }
    int cnt=0;
    for(int i=1;i<=100000;i++) if(F[i].size()>29) {
        cnt++;
        if(cnt>19) calc(F[i]);
        cout<<"OK "<<cnt<<"\n";
        cout<<"----------------------------\n";
    }
}
int main() {
    init();
    vector<int>A;
    for(int i=1;i<=3000;i++) A.push_back(i);
    Calc(A);
    return 0;
}

以上代码的随机数生成方式可能要随着不同的等价类变化，当你看到跑不动的时候就换一种随机方法。

最后是 AC 代码。

#include<bits/stdc++.h>
#include"pudding.h"

using namespace std;

int query_tastiness(vector<int>a);
int Gcd[4505][4505];
vector<int>E[100005];
void init(int c,int t) {
    for(int i=0;i<=4500;i++) {
        Gcd[i][0]=Gcd[0][i]=i;
        for(int j=1;j<=i;j++) Gcd[i][j]=Gcd[j][i]=Gcd[j][i-j];
    }
}
vector<int>calc(int C,vector<int>A) {
    vector<int>T[105];
    int id=0,minn=1e9,X,Y;
    if(C==1) X=0,Y=6,T[0]={1015,2550,1450,1995,3225,630};
    if(C==2) {
        X=27,Y=6;
        T[1]={1309,1122,1224,1326,2686,765};
        T[2]={2669,1734,2159,2669,1853,1224};
        T[3]={3757,901,493,2703,1292,1564};
        T[4]={2838,2728,385,3982,2640,2937};
        T[5]={2772,3619,3135,4169,319,1760};
        T[6]={2387,2849,2607,2882,4026,2739};
        T[7]={2827,1155,1760,4455,1320,3707};
        T[8]={748,924,2068,858,1793,1760};
        T[9]={792,1782,176,880,308,3333};
        T[10]={550,2420,1617,946,3157,2068};
        T[11]={2827,1155,1760,4455,1320,3707};
        T[12]={2205,2457,2107,2268,2561,2370};
        T[13]={2427,2564,2208,2595,2256,2000};
        T[14]={2063,2516,2330,2196,2585,2018};
        T[15]={2256,2145,2081,2482,2214,1935};
        T[16]={1764,1696,1550,1590,976,1881};
        T[17]={1129,1820,969,1087,1640,1176};
        T[18]={1133,1832,1844,930,1404,975};
        T[19]={1656,1948,1627,995,1619,1934};
        T[20]={91,196,294,406,510,615};
        T[21]={112,216,312,392,490,588};
        T[22]={96,214,292,412,485,609};
        T[23]={91,189,319,384,488,610};
        T[24]={114,202,310,390,518,595};
        T[25]={89,195,288,393,483,619};
        T[26]={100,208,308,409,505,584};
        T[27]={109,195,289,386,510,594};
    }
    for(int i=1;i<=X;i++) {
        int maxn=0;
        for(auto j:A) {
            vector<int>now=T[i];
            now.push_back(j),sort(now.begin(),now.end());
            int sum=0;
            for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
            E[sum].push_back(j),maxn=max(maxn,(int)E[sum].size());
        }
        if(maxn<minn) minn=maxn,id=i;
        for(auto j:A) {
            vector<int>now=T[i];
            now.push_back(j),sort(now.begin(),now.end());
            int sum=0;
            for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
            E[sum].clear();
        }
    }
    for(auto j:A) {
        vector<int>now=T[id];
        now.push_back(j),sort(now.begin(),now.end());
        int sum=0;
        for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
        E[sum].push_back(j);
    }
    int Sum=query_tastiness(T[id]);
    vector<int>ans=E[Sum];
    for(auto j:A) {
        vector<int>now=T[id];
        now.push_back(j),sort(now.begin(),now.end());
        int sum=0;
        for(int k=0;k<=Y-1;k++) sum+=Gcd[now[k]][now[k+1]];
        E[sum].clear();
    }
    return ans;
}
int find_tastiness(int c,int m) {
    vector<int>A;
    for(int i=1;i<=m;i++) A.push_back(i);
    auto ans=calc(1,A);
    if(ans.size()<=29) {
        int S=ans.size(),t=query_tastiness(ans);
        for(int i=0;i<S-1;i++) t-=Gcd[ans[i]][ans[i+1]];
        return t;
    }
    ans=calc(2,ans);
    int S=ans.size(),t=query_tastiness(ans);
    for(int i=0;i<S-1;i++) t-=Gcd[ans[i]][ans[i+1]];
    return t;
}

以上代码中为了避免分类一个数在哪个等价类内，于是将所有等价类的解取最优的，减少代码难度。