题解：P16434 [APIO 2026 中国赛区] 蛋糕
AeeE5x
·
·
题解
前言
场外人士题解。
因为 NOIP 分数太低了所以没报 APIO。
什么叫我这个分能去 APIO？？？
算了不管去没去了，反正我花了两天时间终于是独立做出来了这道题。
Description
交互题。
交互库会隐藏一个 [1,W] 内的正整数 d，初始你需要构造一个长度不超过 N，且值域在 [1,W+200] 的序列 a'。
交互库会将 d 插入这个序列，并升序排序。设你构造的序列 a' 长为 m-1，则交互库手中的序列 a 长度为 m。
你可以对交互库进行询问。每次询问需要给出两个非空下标集合 S_1, S_2，满足 S_1, S_2 \subseteq \{0, 1, 2, \dots, m\} 且 S_1 \cap S_2 = \varnothing。交互库会回答 \sum_{i \in S_1} a_i 与 \sum_{i \in S_2} a_i 的大小关系（大于、小于或等于）。
你需要通过至多 K 次询问，回答 d 的值。
Solution
本题可以看作有四问，本题解将依次解决每一问。
Part 1
保证 N=3000，W=100，K=100，7 分。
这部分有无数种做法，考验你有没有读懂题目。
考虑构造序列 $a'=\{1,2,3,\ldots,100\}$，交互库手里的 $a$ 则是其中的某个数重复了一次得到的。
每次询问检查相邻的两个数是否相等即可。
$100$ 次刚好足够，没必要继续优化了。
:::success[参考代码]
```cpp
for(int i=1;i<=W;i++) a.push_back(i);
```
```cpp
for(int i=0;i<m;i++){
int comp=compare_tastiness({i},{i+1});
if(comp==0) return i+1;
}
```
:::
### Part 2
保证 $N=3$，$W=3$，$K=1$，$8$ 分。
这部分也有无数种做法，考验你分类讨论能力。
---
#### Sol 1
考虑构造序列 $a'=\{1,2,3\}$，则 $a$ 是 $\{1,1,2,3\}$、$\{1,2,2,3\}$、$\{1,2,3,3\}$ 中的一个。
考虑 $a$ 的第一项和最后一项，我们知道 $a_0$ 一定为 $1$，且 $a_3$ 一定为 $3$。
考虑询问 $a_0+a_3$ 和 $a_1+a_2$ 的大小关系。
我们发现上述三种情况刚好对应大于、小于、等于三种可能的答案。
:::success[参考代码]
```cpp
for(int i=1;i<=3;i++) a.push_back(i);
```
```cpp
int comp=compare_tastiness({0,3},{1,2});
if(comp==1) return 1;
else if(comp==0) return 2;
else return 3;
```
:::
#### Sol 2
来自 @[hetao1733837](/user/1410369)。
考虑构造序列 $a'=\{1,1\}$，则不管 $d$ 是多少，都有 $a_0=a_1=1$。
同 Sol 1，询问 $a_0+a_1$ 和 $a_2$ 的大小关系即可。
### Part 3
保证 $N=40$，$W=10^9$，$K=30$，$30$ 分。
从这里开始问题变得棘手。
---
看到 $10^9$ 和 $30$，考虑构造等比序列。
考虑构造 $a'=\{1,2,4,8,\ldots,2^{29}\}$。
但是发现这样还缺点意思，于是我们往里面添一个 $1$，$a'=\{1,1,2,4,8,16,\ldots,2^{29}\}$。
---
这样有什么用呢？
考虑 $i>0$，则根据 $2$ 的幂次的性质，有 $\sum\limits_{j=0}^{i-1}a'_j=a'_i$。
放到 $a$ 序列上，如果对于一个 $i$ 来说，上述式子是**成立的**，则 $d$ 一定**位于 $i$ 右边**，因为如果不成立，则 $i$ 的左侧一定存在一个其他数捣乱。
---
看上去我们可以通过二分找到 $d$ 位于 $2$ 的多少次幂中间。
但是这样算上后续二分 $d$ 的具体值的操作次数，总共是 $\log \log W+\log W$ 次，有点不够了。
我们考虑尝试每次操作都将 $d$ 的范围缩小一半。
---
考虑从右到左的扫描，对于一个 $i$，若 $\sum\limits_{j=0}^{i-1}a_j=a_i$ 不成立，则说明 $d$ 在 $i$ 左侧，**也就是 $d\le a_i$**。
而因为 $a$ 成指数增长，所以一次判断恰好能将 $d$ 的上界减半。
而当扫描到第一个 $\sum\limits_{j=0}^{i-1}a_j=a_i$ 成立的位置时，就说明 $d\ge a_i$ 了，且 $d$ 就应该在 $i+1$ 这位置。
这样一次操作能将 $d$ 的下界抬高一半。
---
剩下就可以利用前面的 $2$ 的次幂二分了。
由于每次询问都能将 $d$ 的范围减半，所以总操作次数是 $\log V$ 的，足够通过。
:::success[参考代码]
```cpp
a.push_back(1);
for(int i=1;i<=W;i<<=1) a.push_back(i);
```
```cpp
int L=1,R=W,pos=-1;
for(int i=m-1;i>=1;i--){
if(i==1){
L=a[i];
pos=i+1;
break;
}
vector<int> vhaoierqa;
for(int j=0;j<i;j++) vhaoierqa.push_back(j);
int comp=compare_tastiness(vhaoierqa,{i});
if(comp==0){
L=a[i];
pos=i+1;
break;
}else R=a[i];
}
while(L<R){
int mid=(L+R)>>1;
vector<int> vuqa;
for(int i=0;i<31;i++) if((mid>>i)&1) vuqa.push_back(i+1);
int comp=compare_tastiness(vuqa,{pos});
if(comp==0) return mid;
else if(comp==-1) L=mid+1;
else R=mid-1;
}
return L;
```
:::
### Part 4
保证 $N=3000$，$W=2000$，$K=7$，$55$ 分。
集大成者。
---
你发现从信息的角度来说，你能获得的信息量只有 $3^7=2187$，但 $W$ 恰好卡在了这个上界。
所以你必须思考一些三进制或者三分的神秘东西。
---
沿用 Part 1 的思路，我们构造 $a'=\{1,2,3,\ldots,2000\}$。
现在想象我们拥有两个指针，一个从前往后跳，一个从后往前跳。
左指针每移动一步，其上的数会增加 $1$；右指针每移动一步，其上的数会减少 $1$。无论何时，两个指针上数的和都是固定的。
这是两个指针都不碰到 $d$ 的情况。
---
如果左指针碰到了 $d$——那么这次的 $+1$ 操作会出现问题，导致两指针上数的和减少了 $1$，且这个影响会一直持续。
如果右指针碰到了 $d$，同理，两指针上数的和会永久增加 $1$。
---
我们考虑对上述过程中的两指针和分类讨论，创造出一个三分的环境。
不考虑寻找 $d$，我们转而去寻找那个使指针 $+1$ 或 $-1$ 失败的位置，即对数两两之间的间隔三分。
---
我们把间隔标记在左侧的数上，初始的三分区间为 $[0,m-1]$。
假设当前异常间隔所在的区间为 $[L,R]$，则我们取一个步长 $\mathrm{div}$，考虑左端点从 $L$ 移动到 $L+\mathrm{div}$、右端点从 $R+1$ 移动到 $R+1-\mathrm{div}$ 是否出现问题。
构造 $S_1=\{L,R+1\}$，$S_2=\{L+\mathrm{div},R+1-\mathrm{div}\}$。
- 若 $S_1$ 求和大于 $S_2$ 求和：
- 说明在左侧指针的移动过程中，在某个位置出现了 $+1$ 异常。
- 即答案在 $[L,R-\mathrm{div}-1]$ 处。
- 若 $S_1$ 求和等于 $S_2$ 求和：
- 指针移动过程中，没有出现异常。
- 答案在 $[L+\mathrm{div},R-\mathrm{div}]$ 中。
- 若 $S_1$ 求和小于 $S_2$ 求和：
- 右侧指针移动过程中，出现了 $-1$ 异常。
- 即答案在 $[R-\mathrm{div}+1,R]$ 中。
三分即可，操作次数 $\log_3 W$，精细实现不会超过 $7$。
:::success[参考代码]
```cpp
for(int i=1;i<=W;i++) a.push_back(i);
```
```cpp
int L=0,R=m-1;
while(L<R){
int len=R-L+1;
if(len==2){
int comp=compare_tastiness({L},{L+1});
if(comp==0) return a[L];
else return a[L+1];
}else{
int div=(len+1)/3;
vector<int> s1={L,R+1},s2={L+div,R+1-div};
int comp=compare_tastiness(s1,s2);
if(comp==1) R=L+div-1;
else if(comp==0) L=L+div,R=R-div;
else L=R-div+1;
}
}
return a[L];
```
:::
## Code
没有合并，所以看起来有些乱。
细节巨多，一定要想清楚边界之类的再动手写。
:::success[完整代码]
```cpp
#include<bits/stdc++.h>
#include "cake.h"
// cake.h ---------------
// #include <vector>
// #ifndef CAKE_H
// #define CAKE_H
// std::vector<int> bake_cakes(int N, int W, int K);
// int find_tastiness(int m, int W, int K);
// int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
// #endif // CAKE_H
// ----------------------
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
vector<int> a;
vector<int> bake_cakes(int N,int W,int K){
a.clear();
if(N==3000&&W==100&&K==100) for(int i=1;i<=W;i++) a.push_back(i);
else if(N==3&&W==3&&K==1) for(int i=1;i<=3;i++) a.push_back(i);
else if(N==40&&W==1'000'000'000&&K==30){
a.push_back(1);
for(int i=1;i<=W;i<<=1) a.push_back(i);
}else if(N==3000&&W==2000&&K==7) for(int i=1;i<=W;i++) a.push_back(i);
return a;
}
int find_tastiness(int m,int W,int K){
if(W==100&&K==100){
for(int i=0;i<m;i++){
int comp=compare_tastiness({i},{i+1});
if(comp==0) return i+1;
}
return 0;
}else if(W==3&&K==1){
int comp=compare_tastiness({0,3},{1,2});
if(comp==1) return 1;
else if(comp==0) return 2;
else return 3;
}else if(W==1'000'000'000&&K==30){
int L=1,R=W,pos=-1;
for(int i=m-1;i>=1;i--){
if(i==1){
L=a[i];
pos=i+1;
break;
}
vector<int> vhaoierqa;
for(int j=0;j<i;j++) vhaoierqa.push_back(j);
int comp=compare_tastiness(vhaoierqa,{i});
if(comp==0){
L=a[i];
pos=i+1;
break;
}else R=a[i];
}
while(L<R){
int mid=(L+R)>>1;
vector<int> vuqa;
for(int i=0;i<31;i++) if((mid>>i)&1) vuqa.push_back(i+1);
int comp=compare_tastiness(vuqa,{pos});
if(comp==0) return mid;
else if(comp==-1) L=mid+1;
else R=mid-1;
}
return L;
}else if(W==2000&&K==7){
int L=0,R=m-1;
while(L<R){
int len=R-L+1;
if(len==2){
int comp=compare_tastiness({L},{L+1});
if(comp==0) return a[L];
else return a[L+1];
}else{
int div=(len+1)/3;
vector<int> s1={L,R+1},s2={L+div,R+1-div};
int comp=compare_tastiness(s1,s2);
if(comp==1) R=L+div-1;
else if(comp==0) L=L+div,R=R-div;
else L=R-div+1;
}
}
return a[L];
}
return 0;
}
```
:::