题解：CF2135D1 From the Unknown (Easy Version)
AC_Lover
·
·
题解
CF2135D1
首先可以尝试一个一个往上加，即询问 \displaystyle\underbrace{1\dots 1}_{10^5}，那么此时一定有结果，得数就是 \displaystyle{\left\lceil\frac{10^5}{W}\right\rceil}。
这有什么用？注意到这可以得到 W 一个较紧的取值范围，设 x=\displaystyle{\left\lceil\frac{10^5}{W}\right\rceil}，于是 \dfrac{10^5}{W}\in (x-1,x]，解得
如何在这个区间里**一次**区分出 $W$？先考虑两个数 $W^{\prime},W^{\prime}+1$ 分别作为 $W$ 如何区分，可以放一个 $W^{\prime}$，再放一个 $1$，如果 $W=W^{\prime}$ 就会换行，行数变成 $2$ ；如果 $W=W^{\prime}+1$ 就不会换行，行数是 $1$。于是考虑这样一种构造：
$$
[\underline{l,1},\underline{l,2},\dots,\underline{l,r-l+1}]
$$
这样一定会找到一个分界点，前面的一组都放到一行，后面的都会放到两行，也即对于划线的一组 $(l,i)$，如果 $l+i\le W\Rightarrow i\in [1,W-l]$ 那么会对行数贡献 $1$，否则 $i\in (W-l,r-l+1]$ 会贡献 $2$，因此这次询问的得数 $y$ 可以表示为 $(W-l)+2(r-W+1)$ ，那么可以直接解出 $W$。
不过有没有可能出现这样询问的时候爆 $W$ 的上界？即 $r-l+1>W$ 是否可能成立。仔细分析一下我们发现这是不可能的，根据 $l,r$ 定义有性质 $2l>r$ $^\dagger$，所以 $r-l+1\le l\le W$，一定不会爆上界，这个做法是正确的。
:::info[$\dagger$ 证明]
记 $N=10^5,p=\left\lceil\frac{N}{x}\right\rceil,q=\left\lceil\frac{N}{x-1}\right\rceil$，则 $2l-r=2p-q+1$，因此我们需要证明 $2p\ge q$。
考虑反证，假设对于 $x\ge 2$ 存在 $2p<q$。可以用两个上取整分别解得 $N\in((p-1)x,px],\quad N\in ((q-1)(x-1),q(x-1)]$，变形一下 $2p<q\Rightarrow p\ge 2p+1$，所以
$$
N>(q-1)(x-1)>(2p+1-1)(x-1)=2p(x-1) \\
N\le px
$$
中间的 $N$ 被架空，得到 $2p(x-1)<px$，即 $x<2$，与 $x\ge 2$ 矛盾，因此 $2p\ge q$，得证。
:::
:::info[代码]
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define psb push_back
#define SZ(vec) ((int)vec.size())
using namespace std;
vector<int> buc;
int out()
{
cout << "? " << SZ(buc) << " ";
for (int x : buc) cout << x << " ";
cout << "\n";
buc.clear();
int buf; cin >> buf;
return buf;
}
int ceil(int a,int b) { return (a+b-1)/b; }
void solve()
{
int A=100000;
for (int i=1;i<=A;i++) buc.psb(1);
int x=out();
if (x==1)
{
cout << "! " << A << "\n";
return;
}
int l=ceil(A,x),r=ceil(A,x-1)-1;
int len=r-l+1;
for (int i=1;i<=len;i++) { buc.psb(l),buc.psb(i); }
x=out();
cout << "! " << 2*(r+1)-l-x << "\n";
}
int main()
{
int T; cin >> T;
while (T--) solve();
return 0;
}
```
:::