布丁 NOI 2026

[NOI 2026] 布丁

建议删除此题，我毫无逻辑的搞都过了，明显不是题，纯看谁运气好。

题目链接： [NOI 2026] 布丁 。

题目描述：

有多次询问，每次询问交互库会生成一个数 ww ，你需要实现函数 int find_tastiness(int c,int m) 猜测并返回这个 ww 。

你可以调用函数 int query_tastiness(vector<int>S) ，该函数会将 ww 加入 SS 后排序并输出相邻两项的 gcd⁡\gcd 之和。

对于单组测试，你最多调用不超过 44 次该函数，传入的 SS 最多不超过 3535 。如果你超过了限制，你会获得相应的部分分。

w∈[1,m],m=3000w\in[1,m],m=3000 。

时间限制 12s12s 。

交互库不是自适应的。

很明显 gcd⁡\gcd 的和不具备任何实际意义。你只能通过 query_tastiness 的结果和原来的 SS 的相邻两项 gcd⁡\gcd 做差才能得到有效信息。不妨设 query(S) 的结果为这个信息。

容易发现如果我传入序列 S={1,2,3,⋯ ,m}S=\{1,2,3,\cdots,m\} ，那么 query(S) 的结果就是 ww 。这样做可以获得 1616 分。

考虑调用 44 次 query ，前三次缩小 SS 的范围，最后一次直接传入 SS 。

一个简单的想法是随机 KK 个长度为 nn 的序列，手动计算对于每一个 w=iw=i ， query 的值。找到这 KK 个序列中最能区分的序列，然后询问。复杂度 O(Knm)\mathcal{O}(Knm) 。由于常数原因，取 n=9,K=10n=9,K=10 后获得 5050 分。

考虑优化。很明显如果 KK 能更大，分数肯定更高。所以我们考虑优化常数。容易发现对于相同的 SS ，我们其实重复计算了几乎 mm 遍，所以考虑记忆化序列。我这里采用自然溢出哈希和 unordered_map 存储。在 n=9,K=2000n=9,K=2000 时获得了 8686 分。

然后就是一些调参工作了。目前这样最高有 9797 分，参数 n=6,K=4100n=6,K=4100 。

然后就是一些神人优化了。参考 NOI 2024 百万富翁，这题本质上是提交答案题，于是考虑打表。

具体来说，虽然我直接设置 K=105K=10^5 会超时，但是我可以本地多跑几趟 K=4700K=4700 ，然后根据表找到更优秀的初始序列就行。这种方法最终使得调用 query 的 SS 的和为 3535 ， 通过了 100100 分。

其实这种方法的上限远不止于此：

  1. 可以本地多跑几趟，获得更优秀的初始序列。
  2. 可以换成更优秀的随即方式。

吐槽第一篇题解：

写过后想尝试一下 2 的优化方法。于是我去看第一篇题解。然后我发现第一篇题解中的方法：

A. 如果不打表只能靠运气，纯废物。

B. 没试。

C. 用完更劣质了。

D. 用完更劣质了。

E. 不知所云，不用试也知道会更劣质。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
//#include "pudding.h"
#define WZH
#ifdef WZH
#ifndef PUDDING_H
void init(int c, int t);
int find_tastiness(int c, int m);
int query_tastiness(std::vector<int> a);
#endif
#endif
int G[3001][3001];
void init(int c,int t){
    for(int i=1;i<=3000;i++)for(int j=1;j<=3000;j++)
        G[i][j]=__gcd(i,j);
}
using V=vector<int>;
int query(V x){return query_tastiness(x);}
mt19937 rnd((unsigned)time(NULL)^114514);
int get_value(V &a,V &book){
    int n=a.size(),mx=0;
    V tmp(6001,0);
    int t=0;
    for(int i=1;i<=3000;i++){
        if(book[i])continue;
        int ans=0;
        while(t<n&&a[t]<=i)t++;
        if(t)ans+=G[a[t-1]][i];
        if(t<n)ans+=G[a[t]][i];
        if(t&&t<n)ans-=G[a[t]][a[t-1]];
        tmp[ans+3000]++;
        mx=max(mx,tmp[ans+3000]);
    }
    return mx;
}
void upd(V &a,V &book){
    int n=a.size(),k=query(a),t=0;
    for(int i=0;i<n-1;i++)k-=G[a[i]][a[i+1]];
    for(int i=1;i<=3000;i++){
        if(book[i])continue;
        int ans=0;
        while(t<n&&a[t]<=i)t++;
        if(t)ans+=G[a[t-1]][i];
        if(t<n)ans+=G[a[t]][i];
        if(t&&t<n)ans-=G[a[t]][a[t-1]];
        if(ans!=k)book[i]=1;
    }
}
V Max(V &a,V &b,V &book){
    int t1=get_value(a,book);
    int t2=get_value(b,book);
    return t1<t2?a:b;
}
using ull=unsigned long long;
const int P=133;
unordered_map<ull,vector<int>>mp;
ull HASH(V a){
    int n=a.size();
    ull h=0;
    for(int i=0;i<n;i++)h=h*P+a[i];
    return h;
}
const ull bh=HASH(V(3001,0));
int find_tastiness(int c,int m){
    if(c==1){
        V t;
        for(int i=1;i<=m;i++)t.push_back(i);
        return query(t)-34;
    }
    V book(3001,0);
    for(int i=0;i<3;i++){
        int n=6;
        V ans(n,0);
        ull T=HASH(book);
        if(!mp.count(T)){
            if(T==bh)ans={138,570,1380,1475,1645,2310};
            else ans={3,1908,2526,2636,2704,2794};
            for(int j=1;j<=4400;j++){
                V t(n,0);
                for(int k=0;k<n;k++)t[k]=rnd()%3000+1;
                sort(t.begin(),t.end());
                ans=Max(ans,t,book);
            }
            mp[T]=ans;
        }
        else ans=mp[T];
        // cout<<get_value(mp[T],book)<<"\n";
        // for(int j=0;j<n;j++)cout<<mp[T][j]<<",";cout<<"\n";
        upd(ans,book);
    }
    V t;
    for(int i=1;i<=3000;i++)if(!book[i])t.push_back(i);
    int T=0,M=t.size();
    for(int i=0;i<M-1;i++)T+=G[t[i]][t[i+1]];
    return query(t)-T;
}