题解 P3341 【[ZJOI2014]消棋子】

mulberror · 2020-02-29 17:11:19 · 题解

题目概括

给定R\times C的棋盘，n种颜色的棋子，每种棋子只有两颗并且都在棋盘上。
棋盘的每个格子最多有一颗棋子。
每次操作确定(x,y)和两个方向（保证(x,y)为空格子），向两个方向遇到的第一个颜色如果相同就删去。
请你解决以下两个问题：

• 给定你k个操作，让你求出能够删去颜色的个数。
• 最多能删去多少颜色，并给出方案。

给定数据保证操作合法，选手请保证给出方案亦合法

思路要点

大致思路为用set维护行和列
第一问直接模拟即可
第二问，我们考虑一个贪心，因为删去颜色后只能使以后的答案更优，所以贪心策略就是能删就删
用队列维护当前删去颜色，考虑从删去扩展到其他颜色。
通过观察样例会发现，在两个格子所在的2行和2列所遇到的第一个颜色我们能够更新，所以check后合法的弹入队列。
至于输出方案，洛谷中不需要输出方案，就在更新的时候一并记录即可。
对于每一个点删除后更新的次数为8次，所以总的复杂度为\mathcal O(nlog_2n+klog_2n)

代码

// 洛谷中不需要输出方案的标程
// 方案记录在ans中
#include <bits/stdc++.h>

using namespace std;

template <class T>
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T>
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}

template <class T>
void writeln(T x) {
  write(x), puts("");
}

const int N = 1e5 + 5;
const char dir[] = "UDLR";

set< pair<int, int> > A[N], B[N];
int R, C, n;
int a[N], b[N], c[N], d[N];
bool vis[N];
set< pair<int, int> >::iterator it;
vector< pair< pair<int, int>, pair<char, char> > > ans;

bool move(int x, int y, char d) {
  if (d == 'D') {
    it = B[y].lower_bound(make_pair(x + 1, 0));
    return it != B[y].end(); 
  } else if (d == 'U') {
    it = B[y].lower_bound(make_pair(x, 0));
    if (it == B[y].begin()) return 0;
    else return it--, 1;
  } else if (d == 'L') {
    it = A[x].lower_bound(make_pair(y, 0));
    if (it == A[x].begin()) return 0;
    else return it--, 1;
  } else {
    it = A[x].lower_bound(make_pair(y + 1, 0));
    return it != A[x].end();
  }
  return 0;
}

bool check(int x, int y) {
  set< pair<int, int> >::iterator it = A[x].lower_bound(make_pair(y, 0));
  return (*it).first == y;
}

void del(int j) {
  A[a[j]].erase(make_pair(b[j], j)), B[b[j]].erase(make_pair(a[j], j));
  A[c[j]].erase(make_pair(d[j], j)), B[d[j]].erase(make_pair(c[j], j));
}

void solve1() {
  int m; read(m);
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    int x, y; read(x), read(y);
    if (check(x, y)) continue;
    char dir1[5], dir2[5]; scanf("%s %s", dir1, dir2);
    if (!move(x, y, dir1[0])) continue; 
    set< pair<int, int> >::iterator it1 = it; 
    if (!move(x, y, dir2[0])) continue;
    set< pair<int, int> >::iterator it2 = it;
    if ((*it1).second == (*it2).second) {
      ans++;
      vis[(*it1).second] = 1;
      del((*it1).second);
    }
  }
  write(ans), putchar(' ');
  for (int i = 1; i <= n; i++) 
    if (vis[i]) {
      A[a[i]].insert(make_pair(b[i], i)), A[c[i]].insert(make_pair(d[i], i));
      B[b[i]].insert(make_pair(a[i], i)), B[d[i]].insert(make_pair(c[i], i));
      vis[i] = 0;
    }
}

bool update(int i) { // i is color
  int X1 = a[i], Y1 = b[i], X2 = c[i], Y2 = d[i], cnt = 0;
  if (X1 == X2) {
    if (Y1 > Y2) swap(Y1, Y2);
    if (Y1 + 1 == Y2) return 0;
    move(4, 1, 'R');
    if (move(X1, Y1, 'R')) {
      if ((*it).second == i) {
        del(i);
        ans.push_back(make_pair(make_pair(X1, Y1 + 1), make_pair('L', 'R')));
        return 1;
      }
    }
    return 0;
  }
  if (Y1 == Y2) {
    if (X1 > X2) swap(X1, X2);
    if (X1 + 1 == X2) return 0;
    if (move(X1, Y1, 'D')) 
      if ((*it).second == i) {
        del(i);
        ans.push_back(make_pair(make_pair(X1 + 1, Y1), make_pair('U', 'D')));
        return 1;
      }
    return 0;
  }
  char opt[6];
  if (!check(X2, Y1)) {
    for (int j = 0; j < 4; j++) 
      if (move(X2, Y1, dir[j])) 
        if ((*it).second == i) opt[++cnt] = dir[j];
    if (cnt >= 2) {
      ans.push_back(make_pair(make_pair(X2, Y1), make_pair(opt[1], opt[2])));
      del(i);
      return 1;
    }
  }
  cnt = 0; 
  if (!check(X1, Y2)) {
    for (int j = 0; j < 4; j++) 
      if (move(X1, Y2, dir[j])) 
        if ((*it).second == i) opt[++cnt] = dir[j];
    if (cnt >= 2) {
      ans.push_back(make_pair(make_pair(X1, Y2), make_pair(opt[1], opt[2])));
      del(i);
      return 1;
    }
  }
  return 0;
}

void solve2() {
  ans.clear();
  queue<int> q; 
  for (int i = 1; i <= n; i++) 
    if (update(i)) q.push(i), vis[i] = 1;
  while (!q.empty()) {
    int k = q.front();
    q.pop();
    int color[10];
    int t = 0;
    for (int i = 0; i < 4; i++) {
      if (move(a[k], b[k], dir[i])) 
        color[++t] = (*it).second;
      if (move(c[k], d[k], dir[i])) 
        color[++t] = (*it).second;
    }
    for (int i = 1; i <= t; i++) {
      if (!vis[color[i]] && update(color[i])) {
        q.push(color[i]);
        vis[color[i]] = 1;
        del(color[i]);
      }
    }
  }
  writeln(ans.size());
}

int main() {
#ifdef chhokmah
  freopen("eliminate1.in", "r", stdin);
#endif
  read(R), read(C), read(n);
  for (int i = 1; i <= n; i++) {
    read(a[i]), read(b[i]), read(c[i]), read(d[i]);
    A[a[i]].insert(make_pair(b[i], i)), A[c[i]].insert(make_pair(d[i], i));
    B[b[i]].insert(make_pair(a[i], i)), B[d[i]].insert(make_pair(c[i], i));
    vis[i] = 0;
  }
  solve1();
  solve2();
  return 0; 
}