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

· · 题解

sub1

放入 \{101, 102, 103, \cdots, 201\}，逐个比较 101+d 是否等于后面某个数字。

sub2

放入 \{100,102\}，检查 d+100 和 102 的关系。

sub3

发现 10^9 \approx 2^{30}，考虑放入 2 的整次幂然后二分。但是我们不知道 d 在哪个位置，考虑先确定 d 的位置，发现 1+1+2+4+\cdots+2^k = 2^{k+1}，而中间只要插入一个 d，必然被破坏。所以用这个东西就可以检查 d 是否在 2^{k+1} 之后。

从高位到低位依次检查，最后倍增，前后两个加起来正好跑满 30 次。

sub4

发现 2000 \approx 3^7，考虑三进制。

需要按照 <, =, > 分成三段。查询两个点 \frac{1}{3} W 和 \frac{2}{3} W：

于是就做完了，想要凑出 W-1 是容易的，后面几层类似处理即可。

#include<bits/stdc++.h>
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);

using namespace std;
const int pw3[8]={1,3,9,27,81,243,729,2187};
int vis[105];
int test;
vector<int> bake_cakes(int N, int W, int K) {
    if(N==3000) {
        if(W==100) {
            test=1;
            vector<int> p;
            for(int i=101; i<=201; i++) p.push_back(i);
            return p;
        } else {
            test=4;
            vector<int> p;
            for(int i=1; i<=100; i++) p.push_back(1);
            p.push_back(1);
            for(int i=1; i<=pw3[7]+1; i++) p.push_back(i);
            return p;
        }
    } else if(N==3) {
        test=2;
        return {100,102};
    } else {
        test=3;
        vector<int> p;
        p.push_back(1);
        for(int i=0; i<30; i++) p.push_back(1<<i);
        return p;
    }
}
int find_tastiness(int m, int W, int K) {
    if(test==1) {
        for(int i=1; i<=100; i++) {
            if(compare_tastiness({0,1},{i+1})==0) return i;
        }
    } else if(test==2) {
        return 2+compare_tastiness({0,1},{2});
    } else if(test==3) {
        for(int i=30; i>=1; i--) {
            vector<int> p;
            for(int j=0; j<i; j++) p.push_back(j);
            if(compare_tastiness(p,{i})==0) {
                int x=(1<<i-1);
                vector<int> tmp;
                tmp.push_back(i);
                for(int j=i-1; j>=1; j--) {
                    vector<int> tmp2;
                    tmp2=tmp, tmp2.push_back(j);
                    if(compare_tastiness(tmp2,{i+1})!=1) x|=1<<j-1, tmp=tmp2;
                }
                return x;
            }
        }
    } else {
        memset(vis,0,sizeof vis);
        int x=0;
        for(int i=6; i>=0; i--) {
            vector<int> tmp; // 2*x+pw3[i+1]-1
            if(x) {
                tmp.push_back(100+x);
                if(x>1) tmp.push_back(100+x-1);
                if(pw3[i+1]==x) tmp.push_back(100+pw3[i+1]-2), tmp.push_back(0), tmp.push_back(1);
                else tmp.push_back(100+pw3[i+1]);
            } else {
                tmp.push_back(100+pw3[i+1]);
            }
            int res=compare_tastiness({100+x+pw3[i], 100+x+2*pw3[i]}, tmp);
            if(res==0) x+=pw3[i];
            else if(res==1) x+=2*pw3[i]; 
        }
        return x;
    }
}

什么你问我赛时多少分？我没资格去，我已急哭。