[CodeChef BWGAME]Black-white Board Game

danihao123 posted @ 2018年4月20日 15:23 in 题解 with tags codechef 行列式 高斯消元 可并堆 , 870 阅读
转载请注明出处:http://danihao123.is-programmer.com/

ao劲啊这题,,,

看到那个逆序对奇偶性就想到了行列式(考虑行列式的定义)……其实最后要判定的就是该矩阵行列式的正负性(或者是0)。

这个东西肯定可以高消搞成上三角,然后行列式就很好求了。但高消事\(O(n^3)\)的,会T掉。

考虑怎么去优化这个高消。首先在消元顺序合理的情况下,一定可以让矩阵在整个过程中一直是01矩阵。具体的实现方式,就是考虑从小到大对每个变量进行消元的时候,包含该变量的方程很多,并且他们两两之间一定是满足一个的全1段事另一个的前缀。那么用最短的那一段进行消元即可。

考虑到其他方程被消之后最靠左的1的位置会全部变成另一个位置,所以可以考虑使用可并堆维护各个方程。同时,为了求每个方程当前最靠左的1的位置,我搞了个并查集(逃

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using R = double;
// using GG = __gnu_pbds::priority_queue<int>;
const int maxn = 100005;
const R eps = 1e-8;
inline int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0.00) {
      return -1;
    } else {
      return 1;
    }
  }
}
 
int seg[maxn][2];
namespace BF {
  R A[105][105];
  inline int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      int r = i;
      for(int j = i + 1; j <= n; j ++) {
        if(fabs(A[j][i]) > fabs(A[i][i])) {
          r = j;
        }
      }
      if(r != i) {
        flag *= -1;
        for(int j = i; j <= n; j ++) {
          std::swap(A[i][j], A[r][j]);
        }
      } else {
        if(sign(A[i][i]) == 0) {
          return 0;
        }
      }
      for(int j = i + 1; j <= n; j ++) {
        if(sign(A[j][i]) == 0) continue;
        double f = A[j][i] / A[i][i];
        for(int k = i; k <= n; k ++) {
          A[j][k] -= A[i][k] * f;
        }
      }
    }
    int ret = flag;
    for(int i = 1; i <= n; i ++) {
      ret *= sign(A[i][i]);
    }
    return ret;
  }
  inline void solve(int n) {
    for(int i = 1; i <= n; i ++) {
      int L = seg[i][0], R = seg[i][1];
      for(int j = 1; j <= n; j ++) {
        if(L <= j && j <= R) {
          A[i][j] = 1;
        } else {
          A[i][j] = 0;
        }
      }
    }
    int v = (det(n));
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
namespace CT {
  /*
  struct Node {
    int l, r, id;
    bool operator <(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id < res.id;
        } else {
          return r < res.r;
        }
      } else {
        return l < res.l;
      }
    }
    bool operator >(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id > res.id;
        } else {
          return r > res.r;
        }
      } else {
        return l > res.l;
      }
    }
    bool operator ==(const Node &res) const {
      return (l == res.l) && (r == res.r) && (id == res.id);
    }
  };
  */
  struct N2 {
    int r, id;
    N2() {
      r = 0; id = 0;
    }
    N2(int x, int y) {
      r = x; id = y;
    }
    bool operator <(const N2 &res) const {
      if(r == res.r) {
        return id < res.id;
      } else {
        return r < res.r;
      }
    }
    bool operator >(const N2 &res) const {
      if(r == res.r) {
        return id > res.id;
      } else {
        return r > res.r;
      }
    }
    bool operator ==(const N2 &res) const {
      return (r == res.r) && (id == res.id);
    }
  };
  
  /* struct Node {
    Node *fa, *ch[2];
    N2 v; int l;
    int setv;
    int d() {
      return ((this == fa -> ch[1]) ? 1 : 0);
    }
    void sc(Node *c, int dir) {
      ch[dir] = c;
      c -> fa = this;
    }
    int cmp(const N2 &v2) const {
      if(v == v2) {
        return -1;
      } else {
        if(v2 < v) {
          return 0;
        } else {
          return 1;
        }
      }
    }
    void paint(int x) {
      if(l == -1) return;
      l = x; setv = x;
    }
    void pushdown(int x) {
      if(setv != -1) {
        ch[0] -> paint(setv);
        ch[1] -> paint(setv);
        setv = -1;
      }
    }
  };
  Node pool[maxn]; std::queue<int> FQ;
  Node *nil, *cur;
  void init_pool() {
    nil = cur = pool;
    nil -> l = nil -> setv = -1;
    nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
  }
  Node *alloc_node(N2 x, int L) {
    Node *ret;
    if(FQ.empty()) {
      ret = ++ cur;
    } else {
      ret = FQ.front(); FQ.pop();
    }
    ret -> v = x;
    ret -> l = L; ret -> setv = -1;
    ret -> fa = ret -> ch[0] = ret -> ch[1] = nil;
    return ret;
  }
  
  inline bool is_root(Node *o) {
    return (o -> fa == nil)
  }
  inline void zig(Node *x) {
    int d = x -> d(); Node *y = x -> fa;
    if(is_root(y)) {
      x -> fa = y -> fa;
    } else {
      y -> fa -> sc(x, y -> d());
    }
    y -> sc(x -> ch[d ^ 1], d);
    x -> sc(y, d ^ 1);
  }
  void pdw_path(Node *x) {
    if(!is_root(x)) pdw_path(x -> fa);
    x -> pushdown();
  }
  inline void splay(Node *x) {
    pdw_path(x);
    while(!is_root(x)) {
      Node *y = x -> fa;
      if(!is_root(y)) {
        if((x -> d()) ^ (y -> d())) {
          zig(x);
        } else {
          zig(y);
        }
      }
      zig(x);
    }
  }
  Node *insert(Node *o, Node *x) {
    if(o == nil) return x;
    Node *last = o;
    int d;
    while(o != nil) {
      o -> pushdown(); last = o;
      d = o -> cmp(x -> v);
      o = o -> ch[d];
    }
    x -> ch[0] = x -> ch[1] = nil;
    last -> sc(x, d);
    splay(x); return x;
  }
  Node *top(Node *x) {
    Node *ret = x;
    while(x -> ch[0] == 0) {
      x -> paint
    }
  } */
  
  int par[maxn * 2];
  int get_fa(int x) {
    if(par[x] == x) return x;
    else return (par[x] = get_fa(par[x]));
  }
  void merge(int dir, int src) {
    dir = get_fa(dir); src = get_fa(src);
    if(dir == src) return;
    par[src] = dir;
  }
  bool is_same(int x, int y) {
    return (get_fa(x) == get_fa(y));
  }
  
  using heap = __gnu_pbds::priority_queue<N2, std::greater<N2> >;
  heap Q[maxn];
  int id[maxn], mp[maxn];
  int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      Q[i].clear();
    }
    for(int i = 1; i <= 2 * n; i ++) {
      par[i] = i;
    }
    for(int i = 1; i <= n; i ++) {
      id[i] = mp[i] = i;
      int L = seg[i][0], R = seg[i][1];
      Q[L].push(N2(R, i));
      merge(L, n + i);
    }
    for(int i = 1; i <= n; i ++) {
      if(Q[i].empty()) {
        return 0;
      }
      int p = id[i];
      if(!(get_fa(p + n) <= i && seg[p][1] == (Q[i].top()).r)) {
        flag *= -1;
        int np = (Q[i].top()).id;
#ifdef LOCAL
        printf("Swaping %d and %d.\n", p, np);
#endif
        int nv = mp[np];
        std::swap(id[i], id[nv]);
        std::swap(mp[np], mp[p]);
      }
      p = id[i];
      Q[i].pop();
      int r = seg[p][1];
      if(Q[i].size() > 0 && (Q[i].top()).r == r) {
        return 0;
      }
      if(r < n) {
        Q[r + 1].join(Q[i]);
        merge(r + 1, i);
      }
    }
    return flag;
  }
  void solve(int n) {
    int v = det(n);
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
 
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      scanf("%d%d", &seg[i][0], &seg[i][1]);
    }
    if(n <= 100) {
      BF::solve(n);
    } else {
      CT::solve(n);
    }
  }
  return 0;
}
How to Cancel Netfli 说:
Aug 09, 2022 07:54:33 PM

Netflix has become one of the world’s largest streaming services. It is an absolute beast when it comes to providing some of the best streaming TV series and movies online. The reason it has become such a huge trend and hype is due to growth in the modern gadgets and better Internet all across the world. How to Cancel Netflix But at the same time people have made a change in their mindset so as to seek comfort and entertainment from their homes, phones or laptop without the hassle of going to movies which has become a boon for some people.

NCERT Term 1 Questio 说:
Sep 21, 2022 01:41:35 AM

Every student who wants to get a high score in their Term-1 Examinations can download and practice NCERT Term-1 Sample Paper 2023 Class 2 and the question paper may include mostly short answer questions and objectives to bring out students’ abilities. NCERT Term 1 Question Paper Class 2 Class teachers and subject experts have suggested revision questions mock test questions along with IMP questions which have been repeatedly asked in previous question Papers.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter