文章目录

交互题：毒水 做题笔记

发布于

题意

有 $n$ 瓶水，其中一瓶有毒。
有 $maxk$ 只小白鼠，其中有一只变异了。现在要决定每只小白鼠喝哪些水。最后给出每只小白鼠的死亡情况，你需要输出毒水的编号。
普通小白鼠喝毒水会死，变异小白鼠不喝毒水会死。

Subtask分值$n$$maxk$
$1$$1$$n = 1$$0$
$2$$9$$n \leq 1000$$3000$
$3$$20$$n \leq 1000$$30$
$4$$30$$8 \leq n \leq 16$$7$
$5$$40$$n \leq 1000$$15$

题解

查看题解

Subtask 1

直接输出 $1$。

// Please submit with C++14!
#pragma region HEAD   // Spectre
#include <algorithm>  // By rbtree (https://rbtr.ee)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD

////////////////////////////////////////////////////////////////////////////////

signed main() {
  puts("2");
  fflush(stdout);
  puts("1");
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

Subtask 2

每瓶水用 $3$ 只小白鼠试，如果死了 $2$ 只或 $3$ 只的就是毒水。
小白鼠用量 $3n$。

// Please submit with C++14!
#pragma region HEAD   // Spectre
#include <algorithm>  // By rbtree (https://rbtr.ee)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD

////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp n = ra, maxk = ra, tar = -1;
  array<bool, 3003> a;
  for (auto _ : {1, 2, 3}) {
    for (tp i = 1; i <= n; ++i) {
      printf("1 1 %lld\n", i);
    }
  }
  puts("2");
  fflush(stdout);
  for (tp i = 1; i <= 3 * n; ++i) {
    a[i] = ra;
  }
  for (tp i = 1; i <= n; ++i) {
    if (a[i] + a[i + n] + a[i + n + n] <= 1) {
      printf("%lld\n", i);
    }
  }
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

Subtask 3

对于第 $i$ 只小白鼠，让它去试所有编号二进制第 $i$ 位为 $1$ 的水。当然，因为有变异小白鼠的存在，要用 $3$ 只试。
小白鼠用量 $3 \log n$。

// Please submit with C++14!
#pragma region HEAD   // Spectre
#include <algorithm>  // By rbtree (https://rbtr.ee)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD

////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp n = ra, maxk = ra, tar = 0, lg = 0;
  array<bool, 33> a;
  for (tp i = 1; i <= n; i <<= 1) {
    ++lg;
  }
  for (auto _ : {1, 2, 3}) {
    for (tp i = 0; i < lg; ++i) {
      vector<tp> t;
      t.clear();
      for (tp j = 1; j <= n; ++j) {
        if (j & (1ll << i)) {
          t.push_back(j);
        }
      }
      printf("1 %zu", t.size());
      for (auto&& i : t) {
        printf(" %lld", i);
      }
      puts("");
    }
  }
  puts("2");
  fflush(stdout);
  for (tp i = 0; i < 3 * lg; ++i) {
    a[i] = ra;
  }
  for (tp i = 0; i < lg; ++i) {
    if (a[i] + a[i + lg] + a[i + lg + lg] <= 1) {
      tar += 1ll << i;
    }
  }
  printf("%lld\n", tar);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

Subtask 4 & 5

注意到变异鼠就是普通老鼠取反，因此我们要考虑确定变异鼠的位置。
和 Subtask 3 一样，我们用第 $j$ 只小白鼠来检测所有编号二进制第 $j$ 位为 $1$ 的小白鼠。
检验方法就是和这些小白鼠喝的水集合的异或，然后再把死亡情况异或起来，若为 $1$，则表示有矛盾。

因为每瓶水都被喝了偶数次，因此异或起来一定是 $0$，由于有一只变异，所以出现差错的话异或起来一定是 $1$。
然后注意到我们无法判断变异鼠是在检测鼠当中还是实验鼠当中，不过注意到我们还剩一只没有用，拿它来检测即可。
小白鼠用量 $\log n + \log \log n + 1$。

// Please submit with C++14!
#pragma region HEAD   // Spectre
#include <algorithm>  // By rbtree (https://rbtree.archi)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD

////////////////////////////////////////////////////////////////////////////////

signed main() {
  bool f = 1;
  tp n = ra, maxk = ra, lg = ceil(log2(n)), lglg = ceil(log2(lg)), poison = 0;
  array<bitset<1003>, 19> a;
  for (tp i = 0; i < lg; ++i) {
    tp cnt = 0;
    for (tp j = 0; j < n; ++j) {
      if (j >> i & 1) {
        ++cnt;
        a[i][j] = 1;
      }
    }
    printf("1 %lld", cnt);
    for (tp j = 0; j < n; ++j) {
      if (j >> i & 1) {
        printf(" %lld", j + 1);
      }
    }
    puts("");
  }
  for (tp i = 0; i < lglg; ++i) {
    for (tp j = 0; j < lg; ++j) {
      if (j >> i & 1) {
        a[i + lg] ^= a[j];
      }
    }
    printf("1 %zu", a[i + lg].count());
    for (tp j = 0; j < n; ++j) {
      if (a[i + lg][j]) {
        printf(" %lld", j + 1);
      }
    }
    a[lg + lglg] ^= a[i + lg];
    puts("");
  }
  printf("1 %zu", a[lg + lglg].count());
  for (tp j = 0; j < n; ++j) {
    if (a[lg + lglg][j]) {
      printf(" %lld", j + 1);
    }
  }
  puts("\n2");
  fflush(stdout);
  for (tp i = 0; i <= lg + lglg; ++i) {
    a.back()[i] = ra ^ 1;
  }
  for (tp i = lg; i <= lg + lglg; ++i) {
    f ^= a.back()[i];
  }
  if (f) {
    tp mutations = 0;
    for (tp i = 0; i < lglg; ++i) {
      bool g = a.back()[i + lg];
      for (tp j = 0; j < lg; ++j) {
        if (j >> i & 1) {
          g ^= a.back()[j];
        }
      }
      if (g) {
        mutations += 1ll << i;
      }
    }
    a.back()[mutations] = !a.back()[mutations];
  }
  for (tp i = 0; i <= n; ++i) {
    a[17][i] = 1;
  }
  for (tp i = 0; i < lg; ++i) {
    if (a.back()[i]) {
      a[17] &= a[i];
    }
  }
  printf("%zu\n", a[17]._Find_first() + 1);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

查看代码

// Please submit with C++14!
#pragma region HEAD   // Spectre
#include <algorithm>  // By rbtree (https://rbtr.ee)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD

////////////////////////////////////////////////////////////////////////////////

signed main() {
  bool f = 1;
  tp n = ra, maxk = ra, lg = ceil(log2(n)), lglg = ceil(log2(lg)), poison = 0;
  array<bitset<1003>, 19> a;
  if (n == 1) {
    puts("2\n1");
    return 0;
  }
  for (tp i = 0; i < lg; ++i) {
    tp cnt = 0;
    for (tp j = 0; j < n; ++j) {
      if (j >> i & 1) {
        ++cnt;
        a[i][j] = 1;
      }
    }
    printf("1 %lld", cnt);
    for (tp j = 0; j < n; ++j) {
      if (j >> i & 1) {
        printf(" %lld", j + 1);
      }
    }
    puts("");
  }
  for (tp i = 0; i < lglg; ++i) {
    for (tp j = 0; j < lg; ++j) {
      if (j >> i & 1) {
        a[i + lg] ^= a[j];
      }
    }
    printf("1 %zu", a[i + lg].count());
    for (tp j = 0; j < n; ++j) {
      if (a[i + lg][j]) {
        printf(" %lld", j + 1);
      }
    }
    a[lg + lglg] ^= a[i + lg];
    puts("");
  }
  printf("1 %zu", a[lg + lglg].count());
  for (tp j = 0; j < n; ++j) {
    if (a[lg + lglg][j]) {
      printf(" %lld", j + 1);
    }
  }
  puts("\n2");
  fflush(stdout);
  for (tp i = 0; i <= lg + lglg; ++i) {
    a.back()[i] = ra ^ 1;
  }
  for (tp i = lg; i <= lg + lglg; ++i) {
    f ^= a.back()[i];
  }
  if (f) {
    tp mutations = 0;
    for (tp i = 0; i < lglg; ++i) {
      bool g = a.back()[i + lg];
      for (tp j = 0; j < lg; ++j) {
        if (j >> i & 1) {
          g ^= a.back()[j];
        }
      }
      if (g) {
        mutations += 1ll << i;
      }
    }
    a.back()[mutations] = !a.back()[mutations];
  }
  for (tp i = 0; i <= n; ++i) {
    a[17][i] = 1;
  }
  for (tp i = 0; i < lg; ++i) {
    if (a.back()[i]) {
      a[17] &= a[i];
    }
  }
  printf("%zu\n", a[17]._Find_first() + 1);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////

仅有一条评论

  1. hzt · 2022-10-18 15:58

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

发表评论