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

# SWERC 2019 D - Gnalcats

hashing

2020-03-14 22:23 CST

## Problem

• 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>