题解：P16434 [APIO 2026 中国赛区] 蛋糕
qianyuzhe
·
·
题解
本赛季发挥得像奶龙一样，场外选手提供 subtask 4 一种不太一样的做法及其代码实现。
注意到 3^K\sim W，考虑三分。由于 N>W，考虑把美味度为 1\sim N 的蛋糕都做出来，再加入一个 1 把下标对齐。然后我们希望构造一种三分区间的方法。
考虑求出区间 [L,R] 的三等分点 M_1,M_2，设 \sum\limits_{i=L}^{M_1}=a,\sum\limits_{i=M_1+1}^{M_2-1}=b,\sum\limits_{i=M_2}^{R}=c，如果没有蛋糕 d，那么 a,b,c 应该就等于对应位置下标之和。
设 x 为每个小区间长度，y 为小于 x 的非负整数，加入 d 后，分类讨论：
-
若 d\in[L,M_1)，则 a 会增加 y，b,c 各会增加 x。
-
若 d\in[M_1,M_2)，则 a 不会增加，b 会增加 y，c 会增加 x。
-
若 d\in[M_2,R]，则 a,b 不会增加，c 会增加 y。
以上 \dfrac{R-L}{3} 只是大概估计，实际需略微调整。
发现，设 z=\sum\limits_{i=L}^{M_1-1}i+\sum\limits_{i=M_2}^{R}i-\dfrac{R-L}{3}，则 d 属于三个小区间分别对应 a+c<z,=z,>z 的情况。
所以只需要想办法构造出常数 z 即可。
注意到，在 S_1 和 S_2 中分别加上 a_1,a_2(a_1>a_2)，实际上等价于只在 S_1 中加入 a_1-a_2。再利用允许加入至多为 W+200 的数，我们可以由此来方便地构造常数。
注意到在三分过程中用到的最大的常数就是第一次的两个子区间和，不多于 1800000，所以我们先做出 900 个 2000。下面来构造余数。我们考虑二进制分解：分别构造出 2001,2002,\dots,2512,3024 美味度的蛋糕。
但是因为 2256,2512,3024 都超过了 2200，所以我们可以再加入 10 个 2200 美味度的蛋糕，结合 2056,2112,2024 美味度的蛋糕来凑出这几个数。构造时直接二进制分解。
这样我们最多需要用到 8 次操作。考虑尽可能地均分区间，在 M_1+1<M_2 时将 M_1 增加 1 即可压到 7 次操作。
::::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
int id;
int compare_tastiness(vector<int>s1,vector<int>s2);
vector<int>bake_cakes(int n,int w,int k){
int i;
vector<int>a={};
if(n==3000&&w==100&&k==100){
id=1;
for(i=1;i<=w;i++)a.push_back(i);
return a;
}
if(n==3&&w==3&&k==1){
id=2;
return {1,1};
}
if(n==40&&w==1e9&&k==30){
id=3;
a.push_back(1);
for(i=1;i<=w;i*=2)a.push_back(i);
return a;
}
if(n==3000&&w==2000&&k==7){
id=4;
a.push_back(1);
for(i=1;i<=w;i++)a.push_back(i);
for(i=920;i--;)a.push_back(2000);
for(i=1024;i;i>>=1)a.push_back(2000+i%200);
for(i=20;i--;)a.push_back(2200);
return a;
}
}
int find_tastiness(int m,int w,int k){
int r,d,i,j;
vector<int>v={};
if(id==1){
for(i=1;i<=m;i++){
r=compare_tastiness({i-1},{i});
if(!r)return i;
}
}
if(id==2)return 2-compare_tastiness({0,1},{2});
if(id==3){
for(i=m;i--;){
v={};
for(j=0;j<i;j++)v.push_back(j);
if(!compare_tastiness(v,{i}))break;
}
d=1<<i-1;
v={i};
for(j=i-1;j;j--){
v.push_back(j);
if(compare_tastiness(v,{i+1})==1)v.pop_back();
else d|=1<<j-1;
}
return d;
}
if(id==4){
long long s,L=1,R=w,M1,M2;
vector<int>u;
while(L<R){
M1=L+(R-L)/3;
M2=R-(R-L)/3;
if(M1+1<M2)M1++;
s=-(R-L)/3-1;
v=u={};
for(i=L;i<=M1;i++){
s+=i;
v.push_back(i);
}
for(i=M2;i<=R;i++){
s+=i;
v.push_back(i);
}
for(i=2001;i<2001+s/2000;i++)u.push_back(i);
s%=2000;
if(s&1024){
s^=1024;
v.push_back(2901);
v.push_back(2902);
v.push_back(2903);
v.push_back(2904);
v.push_back(2905);
v.push_back(2906);
u.push_back(2941);
u.push_back(2942);
u.push_back(2943);
u.push_back(2944);
u.push_back(2945);
u.push_back(2927);
}
if(s&512){
s^=512;
v.push_back(2907);
v.push_back(2908);
v.push_back(2909);
u.push_back(2946);
u.push_back(2947);
u.push_back(2931);
}
if(s&256){
s^=256;
v.push_back(2910);
v.push_back(2911);
u.push_back(2948);
u.push_back(2929);
}
if(s&128){
s^=128;
v.push_back(2912);
u.push_back(2932);
}
if(s&64){
s^=64;
v.push_back(2913);
u.push_back(2930);
}
if(s&32){
s^=32;
v.push_back(2914);
u.push_back(2928);
}
if(s&16){
s^=16;
v.push_back(2915);
u.push_back(2926);
}
if(s&8){
s^=8;
v.push_back(2916);
u.push_back(2925);
}
if(s&4){
s^=4;
v.push_back(2917);
u.push_back(2924);
}
if(s&2){
s^=2;
v.push_back(2918);
u.push_back(2923);
}
if(s){
v.push_back(2919);
u.push_back(2922);
}
r=compare_tastiness(v,u);
if(r==-1)R=M1-1;
else if(r==1)L=M2;
else{
L=M1;
R=M2-1;
}
}
return L;
}
}
```
::::