AtCoder_abc278_g

题目大意

给定 $n$，$l$，$r$ 三个数，你需要和交互器博弈。

有一个长度为 $n$ 的区间，你和交互器轮流操作。

每次操作，操作的一方选择一个没有被染黑并且长度在 $l$ 和 $r$ 之间的区间，把它染黑。

无法操作的一方寄了，另一方获胜。

每次你操作要输出两个数 $a$ 和 $b$，表示你选择了区间 $[a,a+b-1]$。

每次交互器操作会给你两个数 $a$ 和 $b$，表示交互器选择了 $[a,a+b-1]$，若 $a=b=0$ 则表示你获胜，如果 $a=b=-1$ 则表示你寄了。

解题思路

情况1

先考虑能否模仿对方，发现唯一的问题就是如果他把区间放在，中间你模仿不了。

所以你考虑先手，先把中间的占了，让左右的长度相同。

此时只要满足 $l\neq r$ 或者 $l \equiv n \pmod 2$ 即可。

情况2

$l = r$，这个时候你只能涂黑固定长度的区间。

考虑计算 $\text{SG}$ 函数，不知道什么是 $\text{SG}$ 函数的可以看这里。

令 $SG_i$ 表示长度为 $i$ 的 $\text{SG}$ 函数值。

那么当 $i<l$ 时，$SG_i=0$。

那么我们要计算对于 $i\ge l$ 的 $SG_i$，就要枚举你这个区间放在哪里。

所以 $SG_i=\operatorname{mex}_{j=1}^{i-l+1}\{SG_{j-1} \operatorname{xor} SG_{i-j-l+1}\}$。

如果 $SG_n = 0$ 那么先手必败，你要选择后手，否则选择先手。

你可以用 set 维护现在还剩哪些连续的空白段。

每次轮到你操作的时候就枚举你选择哪个区间，使得删去这个区间时剩下的局面先手必败，也就是剩下的 $\text{SG}$ 函数值异或为 $0$。

代码示例

场上没过，后来才调出来。

/*
* @Author: ftt2333
* @Email: ftt2333@126.com
* @LastEditTime: 2022-11-19 23:41:43
*/

#include <bits/stdc++.h>
using namespace std;
#define off ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
#define fio(s) fin(s".in"), fout(s".out")
using ll = long long; using ull = uint64_t;
using db = double; using ldb = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vl = vector<ll>;
template <class T> using uid = uniform_int_distribution<T>;
template <class T> using urd = uniform_real_distribution<T>;
#define rep(i, a, b) for(auto i = (a); i <= (b); ++i)
#define per(i, a, b) for(auto i = (a); i >= (b); --i)
#define go(i, h, e, x) for(int i = h[x]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define szof(a) int((a).size())
#define mem(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define int ll

mt19937 rnd(random_device{}());
const int mod = 998244353, N = 2114;

int n, l, r;
int f[N], tax[N];

void solve1() {
  cout << "First\n";
  int e = l + (l % 2 != n % 2);
  int pos = (n - e) / 2 + 1;
  cout << pos << ' ' << e << '\n';
  cout.flush();
  int x, y;
  for (; ; ) {
    cin >> x >> y;
    if (!x && !y) break;
    y = x + y - 1;
    swap(x, y);
    x = n + 1 - x, y = n + 1 - y;
    cout << x << ' ' << y - x + 1 << '\n';
    cout.flush();
  }
}

int mex(vi v) {
  for (int x : v) tax[x]++;
  int res = 0;
  rep(i, 0, N - 1) if (!tax[i]) {
    res = i;
    break;
  }
  for (int x : v) tax[x]--;
  return res;
}

set<pii> rng;

void split(int l, int r) {
  auto it = prev(rng.upper_bound({l, n}));
  auto e = *it;
  rng.erase(it);
  if (e.fi < l) rng.insert({e.fi, l - 1});
  if (e.se > r) rng.insert({r + 1, e.se});
}

int base = 0;
bool check(int l, int r) {
  auto it = rng.upper_bound({l, n});
  if (it == rng.begin()) return 0;
  it--; auto e = *it;
  if (e.fi > l || e.se < r) return 0;
  if (base ^ f[e.se - e.fi + 1] ^ f[l - e.fi] ^ f[e.se - r]) return 0;
  return 1;
}

void getnext() {
  base = 0;
  for (auto e : rng) base ^= f[e.se - e.fi + 1];
  rep(i, 1, n - l + 1) if (check(i, i + l - 1)) {
    cout << i << ' ' << l << '\n';
    cout.flush();
    split(i, i + l - 1);
    break;
  }
}

void solve2() {
  rep(i, l, n) {
    vi v;
    rep(j, 1, i - l + 1) {
      v.pb(f[j - 1] ^ f[i - j - l + 1]);
    }
    f[i] = mex(v);
  }
  rng.insert({1, n});
  if (f[n]) {
    cout << "First\n";
    getnext();
  }
  else cout << "Second\n";
  int x, y;
  for (; ; ) {
    cin >> x >> y;
    if (!x && !y) return;
    y = x + y - 1;
    split(x, y);
    getnext();
  }
}

signed main() {
  cin >> n >> l >> r;
  if (l != r) solve1();
  else solve2();
}