P16434 [APIO 2026 中国赛区] 蛋糕 题解

· · 题解

这题出的还是挺好的，思维链引导比较完整，和 perm 有异曲同工之妙。

对于 sub1，直接构造 1 \sim 100 的 100 个蛋糕，然后比较每个相邻的蛋糕，如果相等，就找到 d 了。

对于 sub2，目的是找到一种构造，使得一次询问的三个结果对应三种可能值，总共就没几种情况，手玩一下就找到了 \{1,3\} 是可行的，一次询问就是 \{0,1\}\{2\}，如果返回 -1 说明 d=1；返回 0 说明 d=2；否则 d=3。

前两个 sub 没什么好说的，大概就花费了 10 分钟左右。

对于 sub3，这个就需要思考一下了，因为 \log W 大致是 K，所以可以想到二分或者二进制分解之类的东西，又因为 N=40 比较小，显然只能构造 W 的二进制拆分，类似若干个 2^p。

然后考虑怎么询问能把 d 找出来，发现可以令 S_1 = \{0,1,\cdots,i\}, S_2 = \{i+1\}，这样从后向前扫可以得到 d 的位置，也就是 d 的最高二进制位，为了方便判断在序列前面塞个 1，所以构造的蛋糕就是 \{2^0,2^0,2^1,\cdots,2^{29}\}。

知道了 d 的位置之后就可以接着往前扫，和 d 比较，判断出 d 的剩余二进制位。

有一些边界需要注意，除了边界情况，这样询问次数是严格 30 次。

::::info[一个很可能陷入的误区] 这里需要说一下，我做的时候把找 d 的位置和判断 d 的剩余二进制位当成两个部分看了，思考完找 d 的位置的方法后，发现这样找的最劣会询问 29 次，于是就想到了用二分优化，但是写完发现判断 d 的剩余二进制位这一部分最劣可能是 30 次，加上二分的询问次数就 35 次了，于是就在疯狂优化第二部分，甚至分讨了两种情况，但很显然都存在卡掉的数据，在这上面浪费了很多时间。

这和 perm 可能遇到的问题很像，如果做 perm 的时候陷入二分的解法很可能就无法想到正解。 ::::

对于 sub4，其实 sub3 的做法稍微优化一下就能拿到这部分的 11\text{pts}，总分 56\text{pts}。

可以发现 3^7=2187，也就是说 7 次询问，每次询问的三种返回值我们都要用到，很容易往三分的方面想。

另外 N=3000 也挺大的，可以构造蛋糕 \{1,2,\cdots,3^7+1\}，总共 2188 个。

对于给定的 l,k，若我们能确定 d 在 [l,l+3k] 的范围内，那么可以三分出 l,l+k,l+2k,l+3k 这四个端点。

令 S_1 = \{l,l+3k\},S_2 = \{l+k,l+2k\}，正常情况下应该是相等的，分讨一下：

具体原因就不写了，比较显然。初始时令 l=0,k=3^6 即可，最终答案就是 l+1。

#include<bits/stdc++.h>
#include"cake.h"
using namespace std;
#define ll long long

int p[10];

vector<int> bake_cakes(int N, int W, int K) {
    vector<int> v; v.clear();
    if(N == 3000 && W == 100) for(int i = 1; i <= W; i ++) v.push_back(i);
    if(N == 3) v.push_back(1), v.push_back(3);
    if(N == 40) {
        v.push_back(1);
        for(int i = 0; i <= 29; i ++) if((1 << i) <= W) v.push_back(1 << i);
    }
    if(N == 3000 && W == 2000) {
        p[0] = 1;
        for(int i = 1; i <= 7; i ++) p[i] = p[i - 1] * 3;
        for(int i = 1; i <= 2188; i ++) v.push_back(i); 
    }
    return v;
}

ll check(ll x) {
    vector<int> s1, s2; s1.clear(), s2.clear();
    s2.push_back(x + 1);
    for(int i = 0; i <= x; i ++) s1.push_back(i);
    return compare_tastiness(s1, s2);
}

int find_tastiness(int m, int W, int K) {
    if(K == 100) for(int i = 1; i <= W; i ++) {
        vector<int> s1, s2; s1.clear(), s2.clear();
        s1.push_back(i - 1), s2.push_back(i);
        if(compare_tastiness(s1, s2) == 0) return i;
    }
    if(K == 1) {
        vector<int> s1, s2; s1.clear(), s2.clear();
        s1.push_back(0), s1.push_back(1), s2.push_back(2);
        ll x = compare_tastiness(s1, s2);
        if(x == -1) return 1;
        if(x == 0) return 2;
        if(x == 1) return 3;
    }
    if(K == 30) {
        ll res = 0;
        vector<int> s1, s2; s1.clear(), s2.clear();
        for(int i = 0; i < m - 1; i ++) s1.push_back(i);
        s2.push_back(m - 1);
        for(int i = m - 2; i >= 0; i --) {
            ll x = compare_tastiness(s1, s2);
            if(x == 0) {
                s1.clear(), s1.push_back(i + 1);
                s2.clear(), s2.push_back(i + 2);
                for(int j = i; j >= 1; j --) {
                    s1.push_back(j), x = compare_tastiness(s1, s2);
                    if(x == 1) s1.pop_back();
                    else if(x == 0) break;
                }
                for(auto it : s1) res += (it > 0 ? (1 << it - 1) : 1);
                break;
            }
            s1.pop_back(), s2.pop_back(), s2.push_back(i);
        }
        return res;
    }
    if(K == 7) {
        int l = 0;
        for(int i = 6; i >= 0; i --) {
            ll x = compare_tastiness({l, l + 3 * p[i]}, {l + p[i], l + 2 * p[i]});
            if(x == -1) l += 2 * p[i];
            else if(x == 0) l += p[i];
        }
        return l + 1;
    }
}

/*
40 1000000000 30 7
1000000000 1 2 3 999999999 536870913 805306367
*/