[NOI2026] 布丁 题解

dapingguo8 · 2026-07-24 10:11:23 · 题解

大家好，我又干了（笑）。

0. 前言

这个题是 APIO 2026 T2 蛋糕的精神续作，它们在各个方面都有很多相似之处（除了做法）。

希望大家在解决这个题目的时候能够玩得开心（笑）~

1. 解法一：确定答案

对于测试点 1，w 只有 35 个可能的取值，考虑用较简单的方式确定答案。

只需要询问一次 [1,2,3,\dots,35]，将 w 混入排序后相当于对原本的结果产生了 w 的贡献，因此将询问结果减去 34 即为 w 的值。

对测试点 2,3 也应用这个做法：测试点 2 仅询问 [1,3000] 内所有质数，测试点 3 询问 [1,3000] 中的所有数。得分为 10 + \lfloor 3.66 \rfloor + \lfloor 3.9 \rfloor = 16。

std::vector<int> primes;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int calc(std::vector<int>a) {
    std::sort(a.begin(),a.end());
    int res = 0;
    for(int i = 1; i < a.size(); i++) {
        res += gcd(a[i], a[i - 1]);
    }
    return res;
}
bool p[3005];
void init(int c,int t){
    p[1] = 1;
    for(int i = 2; i <= 3000; i++) {
        if(!p[i]) {
            primes.push_back(i);
            for(int j = i * 2; j <= 3000; j += i) {
                p[j] = true;
            }
        }
    }
}
int find_tastiness(int c,int m) {
    std::vector<int> p;
    for(int i = 1; i <= m; i++) {
        if(c == 2 && p[i])continue;
        p.push_back(i);
    }
    return query_tastiness(p) - calc(p);
}

2. 询问次数的分配

从第 5 次询问开始每次询问要丢掉 30\% 的分数，惩罚很重，而解法一可以在一次询问内直接确定答案，因此考虑在第 4 次询问使用解法一，直接确定答案。

所以，需要在前 3 次询问内尽可能减少 w 的候选取值个数。

3. 解法二：因数排除

一些记号：

• 以下将一次包含 k 个数的询问称为代价 k 的询问。

• 若 p^d 整除 w 而 p^{d+1} 不整除 w，则称 w 含有 d 个 p。

一个比较自然的想法是利用询问给出的 \gcd 的信息确定因数组成。

可以用一次代价 1 的询问确定 w 是否为某个质数 p 的倍数，

进一步地，如果 k 个质数 p_1,p_2,\dots,p_k 的乘积不大于询问参数上界 4500，那么可以用一次代价 1 的询问确定 w 含有其中哪些质因子。

更深入地，还可以通过提高次数来确定 w 包含的某个质因子的数量。

单从削减取值个数的角度考虑，最坏情况下，确定 w 不是 p_i 的倍数可以将取值个数削减至原本的 \dfrac{p_i-1}{p_i}。

若在前三次询问时分别选择

则得分可达到 10 + \lfloor3.66\rfloor + \lfloor 12.5\rfloor = 25。

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
std::vector<int> primes;

bool pr[3005];
void init(int c,int t){
    pr[1] = 1;
    for(int i = 2; i <= 3000; i++) {
        if(!pr[i]) {
            primes.push_back(i);
            for(int j = i * 2; j <= 3000; j += i) {
                pr[j] = true;
            }
        }
    }
}
int calc(std::vector<int>a) {
    std::sort(a.begin(),a.end());
    int res = 0;
    for(int i = 1; i < a.size(); i++) {
        res += gcd(a[i], a[i - 1]);
    }
    return res;
}
int fp[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

int find_tastiness(int c,int m) {
    std::vector<int> p;
    int a1 = 2 * 3 * 5 * 7 * 11;
    int a2 = 13 * 17 * 19;
    int a3 = 23 * 29;
    int cp[10] = {0};
    int res1 = query_tastiness(std::vector<int>(a1));
    for(int i = 0; i < 5; i++) {
        if(res1 % fp[i] == 0){
            cp[i] = 1;
        }
    }
    int res2 = query_tastiness(std::vector<int>(a2));
    for(int i = 5; i < 8; i++) {
        if(res2 % fp[i] == 0){
            cp[i] = 1;
        }
    }
    int res3 = query_tastiness(std::vector<int>(a3));
    for(int i = 8; i < 10; i++) {
        if(res3 % fp[i] == 0){
            cp[i] = 1;
        }
    }
    for(int i = 1; i <= m; i++) {
        if(c == 2 && pr[i])continue;
        for(int j = 0; j < 10; j++) {
            if((i % fp[j] != 0) ^ cp[j]) {
                p.push_back(i);
            }
        }
    }
    return query_tastiness(p) - calc(p);
}

但是，注意到这个做法在测试点 2 上的表现很差，因此要考虑另外的做法。

4. 解法三：上下界压缩

考虑询问给出的除 \gcd 以外的信息，注意到询问的流程中有这样一步：将 w 插入并按升序排序，这会给出 w 的位置信息，从而可以将 w 的取值上下界压缩。

具体地，可以通过设计询问序列，使得能够根据将 w 插入后对 \gcd 的扰动确定 w 被插入的位置。

4.1 解法三A：

首先确定 w 包含 2 的个数 d，然后尝试将取值范围折半。考虑询问 [2^k,4096] \ (k > d)：

• 若 w\le 2^k，则最终结果增加 2^d；

• 若 w>2^k，则最终结果增加 2^{d+1}-2^k。

• 注意到后者是 2^{d+1} 的倍数而前者不是，因此可以方便地推断 w 的落点。

然而候选区间的中点并不总是 2 的次幂，因此这个时候可以乘上一个质数 p 以贴近候选区间的中点。

第 1 次询问可以通过类似的方式在确定因数构成的同时将候选区间折半。

• 若第 1 次直接询问 4096 而不做优化，第 2,3 次询问操作如上，则得分为 10 + \lfloor 10.2\rfloor + \lfloor 13\rfloor = 33。

• 若第 1 次询问 [3360]（3360 = 2^5\times 3\times 5\times 7），确定 2,3,5,7 的因数信息，则得分提升至 10+ \lfloor 10.2\rfloor + \lfloor 30.8\rfloor = 50。

• 若第 1 次询问 [1680, 3360]，其他同上，折半取值范围，则得分可进一步提升至 10+ \lfloor 11.2\rfloor + \lfloor 39.2\rfloor = 60。

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

using namespace std;

int l, r, pw, pw3, pw5, pw7, best_l, best_r;

vector<int> primes;

bool p[3005];

const vector<int> reserved_weight = {1, 2, 4, 8, 24, 12, 6, 9, 18};

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

vector<int> count_candidates() {
    vector<int> res;

    for (int i = l; i <= r; i++) {
        int c2 = 0, c3 = 0, c5 = 0, c7 = 0;
        int t = i;
        while (t % 2 == 0 and c2 <= 9) {
            c2 ++;
            t /= 2;
        }
        if (t % 3 == 0) {
            c3 ++;
            t /= 3;
        }
        if (t % 5 == 0) {
            c5 ++;
            t /= 5;
        }
        if (t % 7 == 0) {
            c7 ++;
            t /= 7;
        }
        if(c2 == pw and (c3 == pw3) and c5 == pw5 and c7 == pw7) {
            res.push_back(i);
        }
    }
    if(res.size() < 20){
        return res;
    }
    return {};
}

void init(int t, int id) {
    for(int i = 2; i <= 3000; i++) {
        if(!p[i]) {
            primes.push_back(i);
            for(int j = i * 2; j <= 3000; j += i) {
                p[j] = true;
            }
        }
    }
    cerr<<primes.size()<<endl;
}

int log2(int x) {
    int res = 0;
    while(x > 1) {
        x /= 2;
        res++;
    }
    return res;
}

void first_step() {
    int res = query_tastiness({16 * 105, 32 * 105}) - 16 * 105;
    bool extra = 0;
    if(res > 0) {
        r = 16 * 105;
        if(res % 16 == 0){
            extra = 1;
        }
    }
    else {
        res += 16 * 105;
        if(res % 16) {
            res /= 2;
        }
        else {
            extra = 1;
        }
        l = 16 * 105 + 1;
    }
    while(res % 2 == 0) {
            pw++;
            res /= 2;
    }
    if(res % 3 == 0) {
        pw3++;
    }
    if(res % 5 == 0) {
            pw5++;
    }
    if(res % 7 == 0) {
            pw7++;
    }
    if(extra) {
        int res = query_tastiness({3 * 1024});
        pw = pw3 = 0;
        while(res % 2 == 0 and pw <= 9) {
            pw++;
            res /= 2;
        }
        if(res % 3 == 0) {
            pw3++;
        }
    }
}

void second_step() {
    for(int i = 0; i <= 1; i++) {
        vector<int> candidates = count_candidates();
        if (!candidates.empty()) {
            int origin_res = 0;
            for (int j = 1; j < candidates.size(); j++) {
                origin_res += gcd(candidates[j - 1], candidates[j]);
            }
            int res = query_tastiness(candidates);
            l = res - origin_res;
            r = l;
            return;
        }
        int best = 1, mid = l + r >> 1;
        for(int j = pw + 1; j <= 8; j++) {
            for(auto it: primes) {
                if(abs(mid - best) > abs(mid - (1 << j) * it)) {
                    best = (1 << j) * it;
                }
            }
        }
        vector<int> p = {best, 1 << 12};
        int res = query_tastiness(p) - gcd(best, 1 << 12);
        if(res % (1 << pw + 1)) {
            r = best;
        }
        else l = best + 1;
    }
}
void final_step() {
    vector<int> res;
    // l = best_l, r = best_r;
    for (int i = l; i <= r; i++) {
        int c2 = 0, c3 = 0, c5 = 0, c7 = 0;
        int t = i;
        while (t % 2 == 0 and c2 <= 10) {
            c2 ++;
            t /= 2;
        }
        if (t % 3 == 0) {
            c3 ++;
            t /= 3;
        }
        if (t % 5 == 0) {
            c5 ++;
            t /= 5;
        }
        if (t % 7 == 0) {
            c7 ++;
            t /= 7;
        }
        if(c2 == pw and (c3 == pw3) and c5 == pw5 and c7 == pw7) {
            res.push_back(i);
        }
    }
    vector<int> candidates = res;
    int origin_res = 0;
    for (int j = 1; j < candidates.size(); j++) {
        origin_res += gcd(candidates[j - 1], candidates[j]);
    }
    int res_final = query_tastiness(candidates);
    l = res_final - origin_res;
    r = l;
    return;
}
int find_tastiness(int a,int b) {
    l = 1, r = b, pw = 0, pw3 = 0, pw5 = 0, pw7 = 0;
    best_l = l, best_r = r;
    first_step();
    if(l == r) return l;
    second_step();
    if(l == r) return l;
    final_step();

    return l; 
}

4.2 解法三B：

当然，如果想更进一步的话，每次仅折半取值范围是不够的，需要更加精细的划分。

延续解法三 A 的思路，如果想要将取值区间分为尽可能均匀的多个小段的话，需要将询问序列中的每个数尽可能贴近取值区间的等分点。

考虑序列 [1,2,4,\dots, 2^k]，分别乘上不同的质数后对齐至等分点，这样可以根据扰动的结果确定 w 的落点。

这一部分视实现情况可以获得不同的分数：

• 第 1 次询问不做优化可以获得 55\sim 80 分；

• 第 1 次询问优化为 [3360] 可以获得 65\sim 95 分；

• 第 1 次询问进一步优化为 [1680,3360] 可以获得 75\sim 100 分。

在每个得分区间内的分数取决于你构造的询问序列的精细程度。每次划分越细越均匀则表现通常越好。

当然，由于第三次询问时取值范围较小，因此采用乘质数的方法不一定能够找到合适的方案，此时可以手动构造一个序列，例如构造五个数使得相邻两数之间的 \gcd 分别为 [9,3,6,2]，然后对齐至等分点。

标准做法在对齐时直接贪心，可以做到 S = 28。

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

using namespace std;

int l, r, pw, pw3, pw5, pw7, best_l, best_r;

vector<int> primes;

bool p[3005];

const vector<int> reserved_weight = {1, 2, 4, 8, 24, 12, 6, 9, 18};

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int calc(vector<int> a) {
    sort(a.begin(), a.end());
    int res = 0;
    for (int i = 1; i < a.size(); i++) {
        res += gcd(a[i - 1], a[i]);
    }
    return res;
}

vector<int> count_candidates() {
    vector<int> res;

    for (int i = l; i <= r; i++) {
        int c2 = 0, c3 = 0, c5 = 0, c7 = 0;
        int t = i;
        while (t % 2 == 0 and c2 <= 5) {
            c2 ++;
            t /= 2;
        }
        if (t % 3 == 0) {
            c3 ++;
            t /= 3;
        }
        if (t % 5 == 0) {
            c5 ++;
            t /= 5;
        }
        if (t % 7 == 0) {
            c7 ++;
            t /= 7;
        }
        if(c2 == pw and (pw3 == -1 or c3 == pw3) and c5 == pw5 and c7 == pw7) {
            res.push_back(i);
        }
    }
    return res;
}

vector<int> find_interval(int k, vector<int> candidates) {
    vector<int> res;
    if(pw == 0 and pw3 == 0) {
        for(int i = 0; i <= (k - 1) / 2; i++) {
            res.push_back(1 << i);
        }
        for(int i = (k) / 2; i >= 0; i--) {
            res.push_back((1 << i) * 3);
        }
    }
    else {
        res.push_back(1);
        for(int i = 0; i <= k - 1; i++) {
            if(i == pw) continue;
            res.push_back((1 << i));
        }
        res.push_back(1 << k - (pw == 0));
    }

    int m = (int)res.size();
    if (m == 0) return {};

    vector<long long> points(m);
    int n = (int)candidates.size();
    if (m == 1) {
        points[0] = candidates[n / 2];
    } else {
        for (int i = 0; i < m; i++) {
            int idx = (int)((1LL * i * (n - 1) + (m - 1) / 2) / (m - 1));
            points[i] = candidates[idx];
        }
    }

    long long segment = (1LL << 62);
    if (m > 1) {
        for (int i = 1; i < m; i++) {
            segment = min(segment, points[i] - points[i - 1]);
        }
        if (segment == (1LL << 62)) segment = 1;
    } else {
        segment = 1;
    }
    long long limit = max(1LL, (segment + 1) / 2 );

    vector<char> used(primes.size(), 0);
    vector<int> picked;
    picked.reserve(m);
    set<int> possible_sim;
    picked.push_back(res[0]);
    for (int i = 1; i < m; i++) {
        int best_idx = -1;
        long long best_diff = (1LL << 62);

        for (int j = 0; j < (int)primes.size(); j++) {
            if (used[j]) continue;
            long long product = 1LL * res[i] * primes[j];
            if (product > 4000) break;
            long long diff = llabs(product - points[i]);
            if (i == m - 1 and product < points[i]) {
                continue;
            }
            if (i == 0 and product > points[i]) {
                break;
            }
            if (diff < best_diff || (diff == best_diff && (best_idx == -1 || primes[j] < primes[best_idx]))) {
                best_idx = j;
                best_diff = diff;
            }
        }
        if (best_idx == -1 || best_diff > limit) {
            return {};
        }
        picked.push_back(primes[best_idx] * res[i]);
        used[best_idx] = 1;
    }

    return picked;
}

void init(int t, int id) {
    for(int i = 2; i <= 3000; i++) {
        if(!p[i]) {
            primes.push_back(i);
            for(int j = i * 2; j <= 3000; j += i) {
                p[j] = true;
            }
        }
    }
    cerr<<primes.size()<<endl;
}

int log2(int x) {
    int res = 0;
    while(x > 1) {
        x /= 2;
        res++;
    }
    return res;
}

void first_step() {
    int res = query_tastiness({16 * 105, 32 * 105}) - 16 * 105;
    bool extra = 0;
    if(res > 0) {
        r = 16 * 105;
        if(res % 16 == 0){
            extra = 1;
        }
    }
    else {
        res += 16 * 105;
        if(res % 16) {
            res /= 2;
        }
        else {
            extra = 1;
        }
        l = 16 * 105 + 1;
    }
    while(res % 2 == 0) {
            pw++;
            res /= 2;
    }
    if(res % 3 == 0) {
        pw3++;
    }
    if(res % 5 == 0) {
            pw5++;
    }
    if(res % 7 == 0) {
            pw7++;
    }
    if(extra) {
        int res = query_tastiness({3 * 1024});
        pw = pw3 = 0;
        while(res % 2 == 0 and pw <= 5) {
            pw++;
            res /= 2;
        }
        if(res % 3 == 0) {
            pw3++;
        }
    }
}

int second_step() {
    vector<int> candidates = count_candidates();
    for(int i = 0; i <= 1; i++) {

        if (candidates.size() <= 10) {
            int origin_res = 0;
            for (int j = 1; j < candidates.size(); j++) {
                origin_res += gcd(candidates[j - 1], candidates[j]);
            }
            int res = query_tastiness(candidates);
            return res - origin_res;
        }
        for(int k = 8; k >= 3; k--) {
            vector<int> p = find_interval(k, candidates);
            if(p.empty()) continue;
            vector<int> sent_p;

            for(int j = 1; j < p.size(); j++) {
                sent_p.push_back(p[j]);
            }

            int res = query_tastiness(sent_p);

            int valid_count = 0;
            vector<int> next_candidates;
            for(auto it:candidates) {
                vector<int> temp = sent_p;
                temp.push_back(it);
                if(calc(temp) == res) {
                    next_candidates.push_back(it);
                }
            }
            candidates = next_candidates;
            break;

        }
        if(candidates.size() > 15) {
            int n = candidates.size();
            vector<int> sent_p;
            int o = candidates[n / 5] / 9 * 9;
            int x = candidates[n / 5 * 2] / 9 * 9;
            int y = candidates[n / 5 * 3] / 9 * 9 + 3;
            int z = candidates[n / 5 * 4] / 3 * 3;
            int w = candidates[n - 1] / 2 * 2;
            sent_p.push_back(o + 9);
            sent_p.push_back(x + (1 - x % 2) * 9);
            sent_p.push_back(y + y % 2 * 3);
            sent_p.push_back(z + z % 2 * 3);
            if(w % 3 == 0) w += 2;
            sent_p.push_back(w);
            int res = query_tastiness(sent_p);
            vector<int> next_candidates;
            for(auto it:candidates) {
                vector<int> temp = sent_p;
                temp.push_back(it);
                if(calc(temp) == res) {
                    next_candidates.push_back(it);
                }
            }
            candidates = next_candidates;
            break;
        }
    }

    return query_tastiness(candidates) - calc(candidates);
}
int find_tastiness(int a,int b) {
    l = 1, r = 3000, pw = 0, pw3 = 0, pw5 = 0, pw7 = 0;
    best_l = l, best_r = r;
    first_step();
    if(l == r) return l;
    return second_step(); 
}

4.3 解法三C：

随机搜索类做法，例如爬山或者模拟退火，具体就不在这里展开了。

5. 签名

https://pan.baidu.com/s/1syiku8tHWH9ZFtX0MmK_UA?pwd=lavi 提取码: lavi