蛋糕 APIO 2026 中国赛区

[APIO 2026 中国赛区] 蛋糕

简单题，但是考场看错题了 be like 。

题目链接： [APIO 2026 中国赛区] 蛋糕 。

题目描述：

你可以选择一个长度不超过 NN ，值域在 [1,W+200][1,W+200] 的序列 aa 。并实现函数 vector<int> bake_cakes(int N,int W,int K) 返回你选择的序列。

有多次独立的询问，每次询问交互库会往你的序列 aa 中加入一个值域 [1,W][1,W] 的数字 ww ，并将你的序列排序。

设排序后的数组为 bb ，长度为 m+1m+1 。则你需要实现函数 int find_tastiness(int m,int W,int K) 返回交互库往你的数组中加入的数字 ww 。

你可以在你的函数中调用函数 int compare_tastiness(vector<int>S1,vector<int>S2) 。该函数调用时需要满足 S1∩S2=∅S_1\cap S_2=\varnothing 。该函数的返回值为： 1,0,−11,0,-1 ，分别表示 ∑i∈S1bi\sum\limits_{i\in S_1} b_i 比 ∑i∈S2bi\sum\limits_{i\in S_2} b_i 大，一样大或小。

对于每一次询问，你只能调用该函数不超过 KK 次。

子任务：

子任务编号 NN WW KK
11 100100 100100 100100
22 33 33 11
33 4040 10910^9 3030
44 20002000 20002000 77

交互库不是自适应的。

警示后人：

没有要求 S1∪S2=US_1\cup S_2=U 。

Subtask 1

传 100100 个 11 比较就行。

Subtask 2

传 {1,3}\{1,3\} 然后比较时传 {1,2}{3}\{1,2\}\{3\} 。

Subtask 3

肯定与二进制有关。

考虑传 {1,1,2,4,8,⋯ }\{1,1,2,4,8,\cdots\} 。

假设我们知道了 ww 的二进制下最高位，那么只需要从最高位开始，一次往下比较就能确定 ww 二进制下每一位。共有 ⌊log⁡n⌋\lfloor\log n\rfloor 次询问。

接下来我们需要确定二进制下最高位。这里可以倒着枚举，一共要 30−⌊log⁡n⌋30-\lfloor\log n\rfloor 次询问。

总共刚好 3030 次。

Subtask 4

注意到 2178=372178=3^7 。

根据信息论，可以发现我们必须用到 1,0,−11,0,-1 三种信息。

由于 N=3000N=3000 ，于是我们传 {1,2,3,⋯ ,2178}\{1,2,3,\cdots,2178\} 。

从 x=6x=6 开始，假设 ww 的已经确定的位置的和为 AA ，那么我们每次考虑 {3x+A,2×3x+a}{3×3x,x}\{3^x+A,2\times3^x+a\}\{3\times3^x,x\} ，容易根据 {1,0,−1}\{1,0,-1\} 区分 ww 三进制下第 xx 位。

代码：

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
#include <bits/stdc++.h>
#include "cake.h"
using namespace std;
using V=vector<int>;
int cpt(V s1,V s2){return compare_tastiness(s1,s2);}
int pw[114514];
vector<int>bake_cakes(int n,int W,int K){
    if(K==1)return V{1,3};
    if(K==100)return V(100,1);
    if(K==30){
        V S1;
        S1.push_back(1);
        for(int i=0;i<=29;i++)S1.push_back(1<<i);
        return S1;
    }
    if(K==7){
        pw[0]=1;
        for(int i=1;i<=7;i++)pw[i]=pw[i-1]*3;
        V S1;
        for(int i=1;i<=pw[7];i++)S1.push_back(i);
        return S1;
    }
    return V{1};
}
int find_tastiness(int m,int W,int K){
    if(K==1){
        int t=cpt(V{0,1},V{2});
        if(t==-1)return 1;
        else if(t==0)return 2;
        return 3;
    }
    if(K==100){
        V S1,S2;
        for(int i=0;i<=99;i++)S1.push_back(i);
        S2.push_back(100);
        for(int i=100;i>=1;i--){
            if(cpt(S1,S2)==0)return i;
            S1.pop_back();
        }
        return 0;
    }
    if(K==30){
        int l=30;
        while(l>=2){
            V S1,S2;
            for(int i=0;i<l;i++)S1.push_back(i);
            S2.push_back(l);
            if(cpt(S1,S2))l--;
            else break;
        }
        l++;
        V S1,S2;
        S1.push_back(l-1);
        S2.push_back(l);
        int ans=1<<l-2;
        for(int j=l-2;j>=1;j--){
            S1.push_back(j);
            int t=cpt(S1,S2);
            if(t==1)S1.pop_back();
            else if(t==-1)ans+=(1<<j-1);
            else return ans+(1<<j-1);
        }
        return ans;
    }
    if(K==7){
        int ans=0;
        for(int i=6;i>=0;i--){
            int x=ans+pw[i]-1,y=ans+2*pw[i]-1,z=3*pw[i]+ans-1;
            if(ans)ans+=pw[i]*(1+cpt(V{x,y},V{ans-1,z}));
            else ans+=pw[i]*(1+cpt(V{x,y},V{z}));
        }
        return ans;
    }
    return 0;
}