CF1903E Geo Game 题解

· · 题解

设博弈过程中依次经过的点的下标为 p_1,p_2,\ldots,p_n，表示第 i 个走到的点为 (x_{p_i},y_{p_i})（不包括起点）；因为我们只关心最终答案的奇偶性，所以可以将其转化一下（这里将 (sx,sy) 视为 (x_{p_0},y_{p_0})）：

\begin{aligned} L&=\left[\sum\limits_{i=1}^n (x_{p_i}-x_{p_{i-1}})^2+(y_{p_i}-y_{p_{i-1}})^2\right]\bmod 2\\ &=\sum\limits_{i=1}^n \left[(x_{p_i}-x_{p_{i-1}})^2+(y_{p_i}-y_{p_{i-1}})^2\right]\bmod 2\\ &=\sum\limits_{i=1}^n \left[x_{p_i}-x_{p_{i-1}}+y_{p_i}-y_{p_{i-1}}\right]\bmod 2\\ &=(x_{p_n}+y_{p_n}-x_{p_0}-y_{p_0})\bmod 2 \end{aligned}

可见我们只关心起点和终点的 x,y 坐标之和的奇偶性是否相同，如果相同那么先手胜，反之亦然。

所以我们把 n 个点的坐标压成 n 个 0/1，表示该点的横纵坐标之和的奇偶性（即模 2 意义下的值）。

不妨设起点的奇偶性为 0；令 c_i(i\in\{0,1\}) 为 n 个 0/1 中 i 的出现次数：

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,sx,sy; cin>>n>>sx>>sy;
    int a=sx+sy&1;
    set<int> s[2];
    for(int i=0;i<n;i++){
      int x,y; cin>>x>>y;
      s[x+y&1].emplace(i+1);
    } // 存点
    auto f=[&](int x){
      if(s[x].empty())x=!x;
      cout<<*s[x].begin()<<endl;
      s[x].erase(s[x].begin());
    }; // 向交互库输出一个点
    auto g=[&](){
      int x; cin>>x;
      if(s[0].find(x)!=s[0].end())s[0].erase(x);
      else s[1].erase(x);
    }; // 从交互库读取一个点
    if(s[a].size()>=s[!a].size()){ // 先手必胜
      cout<<"First"<<endl;
      if(n&1){ // 最后是自己出
        for(int i=0;i<n-1;i++)
          if(i&1)g();
          else f(!a);
        f(a);
      }
      else{ // 最后是对方出
        for(int i=0;i<n;i++)
          if(i&1)g();
          else f(!a);
      }
    }
    else{ // 后手必胜
      cout<<"Second"<<endl;
      for(int i=0;i<n;i++)
        if(i&1)f(a);
        else g();
    }
  }
  return 0;
}