P7109 滴水不漏
t162
2021-08-01 20:50:00
这里是一个不太一样的思路。
我们考虑第 $i$ 个缸，装着不明单位的水。容易想到，若所有编号小于 $i$，且是 $2$ 的幂次方的水缸都是满的，那么我们可以求出该缸空出来的部分容量 $b_i$，从而求出该缸装的水量。
我们可以通过从高到低枚举 $i$ 的第 $j$ 位（$2^j\neq i$），并将编号为 $2^j$ 的水缸中的水倒入 $i$ 缸中，若倒满了就倒回去*（如果恰好倒满了呢？没关系，这种情况同样倒回去，那么后面的所有缸中的水一定能倒入 $i$ 缸中，并且最后 $i$ 缸会空出恰好 $1$ 单位，如果判断出 $i$ 缸没满，把 $b_i$ 加上 $1$ 即可。这样判断同样适用于 $i$ 恰好是 $2$ 的幂次方且刚好是空的情况）*，否则就将 $b_i$ 加上 $2^j$，此时 $i-b_i$ 即为最初 $i$ 缸内的水量。当然，为了方便下一个缸求解，水要还回去。这样，需要 $2\times\left\lfloor\log_2(i-1)\right\rfloor+3\quad(i\gt 1)$（$i=1$ 时，显然只要 $1$ 次）次操作。
但是，如何保证所有编号小于 $i$，且是 $2$ 的幂次方的水缸都是满的呢？
答案是，不需要保证。
我们可以找到第一个编号小于 $i$，且是 $2$ 的幂次方的缸，它不是满的。
从 $i$ 缸向这个缸倒水，并求出倒了多少水。如果倒满了就找下一个，否则求出这个缸此时的水量（这显然是可以用上面的方法求的）。每次倒出的水量之和（即每缸的水量变化量）就是答案。
如果找不到这样的缸了呢？那此时 $i$ 中剩余的水量显然可以用上面的方法求得。
估计一下，最多需要 $\left(\sum_{1\lt i\leq n}2\times\left\lfloor\log_2(i-1)\right\rfloor+3\right)+\left\lfloor\log_2(n-1)\right\rfloor+1$ 次操作，写个程序跑一下 $n=1000$ 时的情况，得到的答案是 $18963$（而且有一个数据我刚好就用了 $18963$ 次操作？？？）。
代码：
```cpp
// e3c8f1a924 2021年08月01日 星期日 19时31分25秒
#include<cstdarg>
#include<cstdio>
int _printf(char *format, ...) {
va_list args; int k;
va_start(args, format), printf("\033[34m"), k = vprintf(format, args), printf("\033[0m"), va_end(args);
return k;
}
int _puts(char *str) { int k; return printf("\033[34m"), k = puts(str), printf("\033[0m"), k; }
int _putchar(int c) { int k; return printf("\033[34m"), k = putchar(c), printf("\033[0m"), k; }
#ifdef LOCAL
#define printf _printf
#define puts _puts
#define putchar _putchar
#endif
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long ul;
typedef unsigned long long ull;
int cur[1001], ans[1001], p = 1, n, t;
int pour(int u, int v) {
printf("? %d %d\n", u, v), fflush(stdout);
int ret; return scanf("%d", &ret), ret;
}
int _get(int u) {
int i = 1, ret = 0;
while (i < u) i <<= 1; i >>= 1;
while (i) {
if (!pour(i, u)) ret |= i, cur[i] = 0;
else pour(u, i); i >>= 1;
}
if (!pour(u, u)) ret++; i = 1;
while (i < u) { if (!cur[i]) pour(u, i), cur[i] = i; i <<= 1; }
return cur[u] = u - ret;
}
int get(int u) {
int d = 0;
while (p < u) {
if (cur[p] != p) {
if (pour(u, p)) d += p - cur[p], cur[p] = p;
else return t = cur[p], d + _get(p) - t;
}
p <<= 1;
}
return d + _get(u);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) ans[i] = get(i);
putchar('!'); for (int i = 1; i <= n; i++) printf(" %d", ans[i]);
puts(""); fflush(stdout);
return 0;
}
```