🌓
Ftt2333's Nest

ABC278G

创建于 2022-11-21

Tags: OI

Categories: OI

题目大意

给定 nnllrr 三个数,你需要和交互器博弈。

有一个长度为 nn 的区间,你和交互器轮流操作。

每次操作,操作的一方选择一个没有被染黑并且长度在 llrr 之间的区间,把它染黑。

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

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

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

解题思路

情况1

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

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

此时只要满足 lrl\neq r 或者 ln(mod2)l \equiv n \pmod 2 即可。

情况2

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

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

SGiSG_i 表示长度为 iiSG\text{SG} 函数值。

那么当 i<li<l 时,SGi=0SG_i=0

那么我们要计算对于 ili\ge lSGiSG_i,就要枚举你这个区间放在哪里。

所以 SGi=mexj=1il+1{SGj1xorSGijl+1}SG_i=\operatorname{mex}_{j=1}^{i-l+1}\{SG_{j-1} \operatorname{xor} SG_{i-j-l+1}\}

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

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

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

代码示例

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

/*
* @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();
}

Powered by Hexo, theme by Facter