Gym - 102501D Gnalcats
题意
给两种栈操作判断是否相等,如果两个操作都fail，也认为相等
Solution
模拟，每个氨基酸一个hash值。通过判断最后栈元素是否对应hash相等，判断操作是否相等
#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
//#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <cassert>
#include <unordered_map>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define PI acos(-1.0)
#define random(x) rand() % x
#define debug(x) cout << #x << " " << x << "\n"
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
#ifdef DEBUG
const int MAX = 2e3 + 50;
#else
const int MAX = 1e6 + 50;
#endif
const int mod = 1e9 + 7;
void file_read() {
#ifdef DEBUG
freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
}
#define ULL unsigned long long
struct DNA
{
struct Node
{
int l, r;
unsigned LL val;
Node(){}
Node(int l, int r, unsigned LL val) : l(l), r(r), val(val) {}
bool complex() const {
return l and r;
}
}tr[MAX];
stack<int> stk;
int tot;
int num;
DNA() : tot(1), num(1) {
for(int i = 1; i <= (int)1e5; i++) {
tr[tot] = Node(0, 0, num++);
stk.push(tot);
tot++;
}
}
ULL hash(int u, int v) {
ULL base = 131;
return tr[u].val * base + tr[v].val;
}
bool op_C() {
auto u = stk.top();
tr[tot] = tr[u];
stk.push(tot);
tot++;
return true;
}
bool op_D() {
stk.pop();
return true;
}
bool op_L() {
auto u = stk.top(); stk.pop();
if(!tr[u].complex())
return false;
// tr[tot] = tr[tr[u].l];
// stk.push(tot);
stk.push(tr[u].l);
return true;
}
bool op_P() {
auto u = stk.top(); stk.pop();
auto v = stk.top(); stk.pop();
tr[tot] = Node(u, v, hash(u, v));
stk.push(tot);
tot++;
return true;
}
bool op_R() {
auto u = stk.top(); stk.pop();
if(!tr[u].complex())
return false;
// tr[tot] = tr[tr[u].r];
// stk.push(tot++);
stk.push(tr[u].r);
return true;
}
bool op_S() {
auto u = stk.top(); stk.pop();
auto v = stk.top(); stk.pop();
stk.push(u);
stk.push(v);
return true;
}
bool op_U() {
auto u = stk.top(); stk.pop();
if(!tr[u].complex())
return false;
stk.push(tr[u].r);
stk.push(tr[u].l);
return true;
}
bool op(const string &s) {
bool res = true;
for(auto c : s) {
switch (c)
{
case 'C':res &= op_C(); break;
case 'D':res &= op_D(); break;
case 'L':res &= op_L(); break;
case 'P':res &= op_P(); break;
case 'R':res &= op_R(); break;
case 'S':res &= op_S(); break;
case 'U':res &= op_U(); break;
default:
break;
}
}
return res ;
}
};
DNA A, B;
int main() {
file_read();
string s, t;
cin >> s >> t;
A = DNA();
B = DNA();
bool a = A.op(s);
bool b = B.op(t);
if(a ^ b) {
puts("False");
return 0;
}
if(!a and !b) {
puts("True");
return 0;
}
while(!A.stk.empty() and !B.stk.empty()) {
auto u = A.stk.top(); A.stk.pop();
auto v = B.stk.top(); B.stk.pop();
if(A.tr[u].val != B.tr[v].val) {
puts("False");
return 0;
}
}
if(!A.stk.empty() || !B.stk.empty()) {
puts("False");
return 0;
}
puts("True");
return 0;
}
Gym - 102501J
题意
给一个树的中序遍历序列，判断有多少满足类似小根堆的树，$n<=1e5$
Solution
- 直接dp一定会超时
- 考虑根可能在的位置，即当前最小元素的位置
- 考虑选这些元素为根会有哪些树，就可以发现当前的最小元素将序列分成子段，当前元素作为根的种类数是卡特兰数
- 因此递归解决这个问题，每次用最小元素分割当前序列，最后其实就是一些卡特兰数的乘积
- 用单调栈会更优美一点
#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
//#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <cassert>
#include <unordered_map>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define PI acos(-1.0)
#define random(x) rand() % x
#define debug(x) cout << #x << " " << x << "\n"
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
#ifdef DEBUG
const int MAX = 2e3 + 50;
#else
const int MAX = 2e6 + 500;
#endif
const int mod = 1e9 + 7;
void file_read() {
#ifdef DEBUG
freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
}
int a[MAX];
LL fact[MAX];
LL inv[MAX];
map<int, vector<int>> pos;
LL qpow(LL x, LL n) {
LL res = 1;
while(n) {
if(n & 1) {
res = res * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return res;
}
LL f(LL x) {
return fact[2*x] * inv[x] % mod * inv[x+1] % mod;
}
int main() {
file_read();
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
fact[0] = 1;
for(int i = 1; i < MAX; i++) fact[i] = 1LL * fact[i-1] * i % mod;
inv[MAX-1] = qpow(fact[MAX-1], mod-2);
for(int i = MAX-2; i >= 1; i--) inv[i] = 1LL * (i+1) * inv[i+1] % mod;
inv[0] = 1;
LL res = 1;
stack<int> stk;
for(int i = 1; i <= n; i++) {
if(stk.empty()) {
stk.push(a[i]);
continue;
}
int cnt = 0;
int cur = inf;
while(!stk.empty() and stk.top() > a[i]) {
if(stk.top() == cur) {
cnt++;
}
else {
res = res * f(cnt) % mod;
cnt = 1;
cur = stk.top();
}
stk.pop();
}
stk.push(a[i]);
res = res * f(cnt) % mod;
}
int cur = inf;
int cnt = 0;
while(!stk.empty()) {
if(stk.top() == cur) {
cnt++;
}
else {
res = res * f(cnt) % mod;
cur = stk.top();
cnt = 1;
}
stk.pop();
}
res = res * f(cnt ) % mod;
printf("%lld\n", res);
}