P17142 [NOI 2026] 布丁

Genius_Star · 2026-08-07 08:32:03 · 题解

来一个打表做法，vp 的时候爬山写挂了，一直在调整固定一个位置的值，跑出来的仅仅获得了 29pts。

思路：

首先注意到若我们选择了一个包含 ans 的集合 S，那么将 ans 加入 S 后会新增一个 ans 的贡献，即答案是 query(S) - base(S)。

那么有一个很暴力的做法，询问一下 1 \sim m，在素数的时候只询问素数，这样可以获得二十多分。

考虑优化，对于第一次询问，我们可以将 1 \sim 3000 根据询问的值划分为若干等价类，后面类似，找到 ans 所在等价类后再次询问将这个等价类再次划分，一直递归，直到 ans 所在等价类大小 siz \le 35 - used，此时按照暴力的思路问一下即可。

因为 ans 可能取遍 1 \sim 3000，使得某些等价类大小小是不够的，要使得最大等价类的大小尽可能小；于是首先考虑搜一下第一次询问，直接随机的话这个大小大概在 200 \sim 300 左右，完全无法接受；考虑爬山，先随机一个询问序列，然后随机一个位置 x，将其值改为 [q_{x - 1}, q_{x + 1}] 之间的随机数，如果更优就保留下来。

这样爬山对 len = 6, 7, 8, 9 分别跑个 1min，本地尝试发现 len = 7 是最优的，跑出来最大等价类的大小为 124 的好划分，是询问 [180, 483, 924, 1344, 1890, 2415, 2968]。

::::info[第一次询问打表]

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 3030, M = 1e5;
int n;
int a[N], cnt[M];
inline int get(vector<int> &a){
    int s = 0;
    for (int i = 1; i < (int)a.size(); ++i)
      s += __gcd(a[i - 1], a[i]);
    return s;
}
inline int getins(vector<int> &a, int lst, int w){
    int n = a.size();
    int p = lower_bound(a.begin(), a.end(), w) - a.begin();
    if(p < n && a[p] == w)
      return lst + w;
    if(!p)
      return lst + __gcd(w, a[0]);
    if(p == n)
      return lst + __gcd(w, a[n - 1]);
    return lst - __gcd(a[p - 1], a[p]) + __gcd(w, a[p - 1]) + __gcd(w, a[p]);
}
inline int get(vector<int> &ask, vector<int> &a){
    int mx = 0, lst = get(ask);
    vector<int> V;
    for(auto i : a){
        int w = getins(ask, lst, i);
        if(!cnt[w])
          V.push_back(w);
        ++cnt[w];
        mx = max(mx, cnt[w]);
    }
    for(auto v : V)
      cnt[v] = 0;
    return mx;
}
mt19937 R(time(0));
inline void init(){
    for(int i = 1; i <= n; ++i)
      cin >> a[i];
}
int main(){
    cin >> n;
//  init();
    int T;
    int mn = 1e9;
    cin >> T;
    vector<int> now;
    for(int i = 1; i <= 3000; ++i)
      now.push_back(i);
    a[0] = 1, a[n + 1] = 4500;
    while(mn > 100){
        vector<int> ask;
        for(int i = 1; i <= n; ++i){
            a[i] = R() % 3000 + 1;
            ask.push_back(a[i]);
        }
        sort(ask.begin(), ask.end());
        sort(a + 1, a + n + 1);
        int w = get(ask, now);
        int TT = 1000;
        while(TT--){
            int x = R() % n + 1;
            int lst = a[x];
            a[x] = a[x - 1] + R() % (a[x + 1] - a[x - 1] + 1);
            ask[x - 1] = a[x];
            int ww = get(ask, now);
            if(ww > w){
                a[x] = lst;
                ask[x - 1] = a[x];
            }
            else
              w = ww;
        }
        if(w < mn){
            mn = w;
            for(auto v : ask){
                cout << v << ' ';
            }
            cout << '\n';
            cerr << w << '\n';
        }
    }
    return 0;
}
/*
180 483 924 1344 1890 2415 2968
124
*/

::::

通过这次询问，对于划分的若干等价类，显然大小 \le 35 - 7 = 28 的不需要管了，暴力询问下即可；否则对于其它的等价类，考虑经过第二次长度为 len 的询问，使得它划分的每个等价类大小 \le 28 - len。

于是，对第一次询问划分下来的每个等价类再次打表出询问，使用上面的爬山随机法，直到 \le 28 - len 了才结束；事实证明，试了 len = 8, 7, 6，发现只有 len = 6 的时候在本地 2min 以内跑出来了；于是我们可以在 Q = 3, S = 35 的限制下通过了这题。

如果你 rp 不是很好，第二次询问也没有跑出来，别慌，还有第三次，对第二次询问划分的等价类再跑随机，显然表是够的。

::::info[第二次询问打表]

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 3030, M = 1e5;
int n;
int a[N], cnt[M];
vector<int> P[M];
mt19937 R(time(0));
inline int get(vector<int> &a){
    int s = 0;
    for (int i = 1; i < (int)a.size(); ++i)
      s += __gcd(a[i - 1], a[i]);
    return s;
}
inline int getins(vector<int> &a, int lst, int w){
    int n = a.size();
    int p = lower_bound(a.begin(), a.end(), w) - a.begin();
    if(p < n && a[p] == w)
      return lst + w;
    if(!p)
      return lst + __gcd(w, a[0]);
    if(p == n)
      return lst + __gcd(w, a[n - 1]);
    return lst - __gcd(a[p - 1], a[p]) + __gcd(w, a[p - 1]) + __gcd(w, a[p]);
}
inline int get(vector<int> &ask, vector<int> &a){
    int mx = 0, lst = get(ask);
    vector<int> V;
    for(auto i : a){
        int w = getins(ask, lst, i);
        if(!cnt[w])
          V.push_back(w);
        ++cnt[w];
        mx = max(mx, cnt[w]);
    }
    for(auto v : V)
      cnt[v] = 0;
    return mx;
}
inline vector<int> create(int n, vector<int> &now, int lim){
    a[0] = 1, a[n + 1] = 4500;
    int mn = 1e9;
    vector<int> rask;
    while(mn > lim){
        vector<int> ask;
        for(int i = 1; i <= n; ++i){
            a[i] = R() % 3000 + 1;
            ask.push_back(a[i]);
        }
        sort(ask.begin(), ask.end());
        sort(a + 1, a + n + 1);
        int w = get(ask, now);
        int TT = 100;
        while(TT--){
            int x = R() % n + 1;
            int lst = a[x];
            a[x] = a[x - 1] + R() % (a[x + 1] - a[x - 1] + 1);
            ask[x - 1] = a[x];
            int ww = get(ask, now);
            if(ww > w){
                a[x] = lst;
                ask[x - 1] = a[x];
            }
            else
              w = ww;
        }
        if(w < mn){
            mn = w;
            rask = ask;
//          for(auto v : ask){
//              cout << v << ' ';
//          }
//          cout << '\n';
//          cerr << w << '\n';
        }
    }
    return rask;
}
inline void getsave(vector<int> &ask, vector<int> &a){
    int lst = get(ask);
    vector<int> V;
    for(auto i : a){
        int w = getins(ask, lst, i);
        if(!cnt[w])
          V.push_back(w);
        ++cnt[w];
        P[w].push_back(i);
    }
    for(auto v : V){
        cnt[v] = 0;
        if((int)P[v].size() <= 28)
          continue;
//      cout << P[v].size() << ':';
//      for(auto i : P[v])
//        cout << i << ' ';
//      cout << '\n'; 
        auto getask = create(6, P[v], 22);
        cout << "Q[" << v << ']' << " = {";
        for(int i = 0; i < (int)getask.size(); ++i)
          cout << getask[i] << (i == (int)getask.size() - 1 ? "};" : ", ");
        cout << '\n'; 
    }
    return ;
}
inline void init(){
    for(int i = 1; i <= n; ++i)
      cin >> a[i];
    vector<int> ask;
    for(int i = 1; i <= n; ++i)
      ask.push_back(a[i]);
    sort(ask.begin(), ask.end());
    vector<int> now;
    for(int i = 1; i <= 3000; ++i)
      now.push_back(i); 
    getsave(ask, now);
}
int main(){
    cin >> n;
    init();
//  int T;
//  int mn = 1e9;
//  cin >> T;
//  vector<int> now;
//  for(int i = 1; i <= 3000; ++i)
//    now.push_back(i);

    return 0;
}
/*
7
180 483 924 1344 1890 2415 2968
124
*/

::::

代码实现的时候把表在 init 时预处理好，询问的时候直接问即可。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#include "pudding.h"
const int N = 3030, M = 1e5;
int n;
int a[N], cnt[M], id[N], ccnt[M];
vector<int> P[M], Q[M], PP[M];
mt19937 R(time(0));
inline int get(vector<int> &a){
    int s = 0;
    for (int i = 1; i < (int)a.size(); ++i)
      s += __gcd(a[i - 1], a[i]);
    return s;
}
inline int getins(vector<int> &a, int lst, int w){
    int n = a.size();
    int p = lower_bound(a.begin(), a.end(), w) - a.begin();
    if(p < n && a[p] == w)
      return lst + w;
    if(!p)
      return lst + __gcd(w, a[0]);
    if(p == n)
      return lst + __gcd(w, a[n - 1]);
    return lst - __gcd(a[p - 1], a[p]) + __gcd(w, a[p - 1]) + __gcd(w, a[p]);
}
inline int get(vector<int> &ask, vector<int> &a){
    int mx = 0, lst = get(ask);
    vector<int> V;
    for(auto i : a){
        int w = getins(ask, lst, i);
        if(!cnt[w])
          V.push_back(w);
        ++cnt[w];
        mx = max(mx, cnt[w]);
    }
    for(auto v : V)
      cnt[v] = 0;
    return mx;
}
inline void getsave(vector<int> &ask, vector<int> &a){
    int lst = get(ask);
    vector<int> V;
    for(auto i : a){
        int w = getins(ask, lst, i);
        if(!cnt[w])
          V.push_back(w);
        ++cnt[w];
        P[w].push_back(i);
    }
    for(auto v : V)
      cnt[v] = 0;
    return ;
}
void init(int c, int t){
    vector<int> now;
    for(int i = 1; i <= 3000; ++i)
      now.push_back(i);
    vector<int> base = {180, 483, 924, 1344, 1890, 2415, 2968};
    getsave(base, now);
    Q[263] = {98, 160, 900, 1435, 2764, 3344};
    Q[264] = {92, 343, 1229, 1352, 2727, 3549};
    Q[265] = {149, 360, 530, 2395, 3344, 3572};
    Q[266] = {160, 2370, 3296, 3501, 3855, 4472};
    Q[268] = {255, 476, 1348, 1712, 2189, 4445};
    Q[271] = {264, 446, 895, 1170, 3043, 3139};
    Q[261] = {55, 285, 369, 1782, 2125, 3428};
    Q[262] = {324, 561, 1687, 1853, 2152, 4350};
    Q[243] = {60, 572, 650, 753, 855, 3132};
    Q[250] = {632, 654, 1143, 2343, 3921, 4384};
    Q[246] = {655, 1080, 3151, 3574, 3640, 4005};
    Q[247] = {256, 326, 626, 684, 2989, 3052};
    Q[256] = {387, 632, 737, 2544, 2978, 3923};
    Q[244] = {675, 795, 1926, 2170, 2672, 3335};
    Q[180] = {70, 1025, 1118, 1230, 1581, 2982};
    Q[182] = {672, 1064, 1133, 1298, 3847, 4100};
    Q[184] = {166, 733, 927, 1073, 1255, 2985};
    Q[190] = {975, 1107, 1336, 2449, 3074, 3295};
    Q[202] = {616, 1152, 3589, 3635, 3907, 3981};
    Q[234] = {340, 1605, 2148, 2188, 2688, 4377};
    Q[226] = {67, 608, 1011, 1492, 1716, 3757};
    Q[238] = {696, 1659, 2650, 3317, 3695, 3898};
    Q[224] = {361, 1331, 1356, 1551, 1757, 3408};
    Q[222] = {1218, 1463, 1587, 1692, 1798, 4433};
    Q[232] = {592, 1474, 1570, 1941, 2008, 4344};
    Q[159] = {1872, 1988, 2046, 2142, 2232, 2328};
    Q[160] = {240, 327, 528, 2100, 2255, 3772};
    Q[163] = {5, 363, 429, 2138, 2261, 2436};
    Q[166] = {235, 1078, 2268, 2960, 3934, 4120};
    Q[172] = {935, 1078, 1125, 2055, 2161, 3356};
    Q[178] = {205, 637, 787, 952, 2299, 2505};
    Q[257] = {2292, 2502, 2618, 2717, 2856, 4472};
    Q[260] = {143, 702, 2548, 2584, 2819, 4359};
    Q[259] = {232, 821, 922, 1124, 1278, 2718};
    Q[258] = {519, 790, 888, 1411, 2584, 2795};
}
int find_tastiness(int c, int m){
    if(m <= 35){
        vector<int> ask;
        for(int i = 1; i <= m; ++i)
          ask.push_back(i);
        return query_tastiness(ask) - get(ask);
    }
    vector<int> ask = {180, 483, 924, 1344, 1890, 2415, 2968};
    int w = query_tastiness(ask);
    if(Q[w].empty()){
        assert((int)P[w].size() <= 28); 
        ask.clear();
        for(auto i : P[w])
          ask.push_back(i);
        return query_tastiness(ask) - get(ask);
    }
    ask = Q[w];
    int lst = get(ask);
    vector<int> V;
    for(auto i : P[w]){
        int t = getins(ask, lst, i);
        if(!ccnt[t])
          V.push_back(t);
        ++ccnt[t];
        PP[t].push_back(i);
    }
    w = query_tastiness(ask);
    ask = PP[w];
    for(auto v : V)
      PP[v].clear(), ccnt[v] = 0;   
    return query_tastiness(ask) - get(ask);
}