[Blog] [Docs] [Code] [Slides] [About]

SWERC 2019 D - Gnalcats

hashing

2020-03-14 22:23 CST

Problem

题目链接(CodeForces)

很有难度的一道哈希表。要求判定两个栈操作语言是否等价。

不仅实现上难度大,时间上也往死里卡(0.3s)。

关键思想:

  • pair可以当作<left, right>来映射,实现$O(1)$判定pair是否相等;
  • stack可以当作<top, rest>来映射,实现$O(1)$判定栈是否相等。

Solution

#include <bits/stdc++.h>
using namespace std;
 
string a, b;
int pcnt = 100000000, scnt = 200000000;
map<pair<int, int>, int> pmap;
map<int, pair<int, int>> pmaprev;
map<pair<int, int>, int> smap;
map<int, pair<int, int>> smaprev;
 
int findOrCreatePair(int l, int r) {
  auto p = make_pair(l, r);
  if (pmap[p] == 0) {
    ++pcnt;
    pmap[p] = pcnt;
    pmaprev[pcnt] = p;
    return pcnt;
  } else {
    return pmap[p];
  }
}
 
int findOrCreateStack(int h, int r) {
  auto p = make_pair(h, r);
  if (smap[p] == 0) {
    ++scnt;
    smap[p] = scnt;
    smaprev[scnt] = p;
    return scnt;
  } else {
    return smap[p];
  }
}
 
int initial = 0;
void init() {
  pmap.clear(), smap.clear();
  pmaprev.clear(), smaprev.clear();
  int rest = -1;
  for (int i = 100005; i > 0; --i) {
    rest = findOrCreateStack(i, rest);
  }
  initial = scnt;
}
 
int solve(string &s) {
  int n = s.size();
  int cur = initial;
  int head = 1, rest = initial - 1;
  for (int i = 0; i < n; ++i) {
    pair<int, int> p = pair<int, int>();
    switch (s[i]) {
      case 'C':
        rest = cur;
        break;
      case 'D':
        p = smaprev[rest];
        head = p.first, rest = p.second;
        break;
      case 'L':
        if (pmaprev.find(head) == pmaprev.end()) {
          return -1;
        } else {
          head = pmaprev[head].first;
        }
        break;
      case 'R':
        if (pmaprev.find(head) == pmaprev.end()) {
          return -1;
        } else {
          head = pmaprev[head].second;
        }
        break;
      case 'P':
        p = smaprev[rest];
        head = findOrCreatePair(head, p.first);
        rest = p.second;
        break;
      case 'U':
        if (pmaprev.find(head) == pmaprev.end()) {
          return -1;
        } else {
          p = pmaprev[head];
          head = p.first;
          rest = findOrCreateStack(p.second, rest);
        }
        break;
      case 'S':
        p = smaprev[rest];
        rest = findOrCreateStack(head, p.second);
        head = p.first;
        break;
    }
    cur = findOrCreateStack(head, rest);
  }
  //cout << cur << endl;
  return cur;
}
 
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin >> a >> b;
  init();
  cout << (solve(a) == solve(b) ? "True" : "False");
  return 0;
}
<EOF>