P7109 滴水不漏

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$ 次操作???)。

代码:

// 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;
}