滚木比较器。
用于对滚木集合进行字典序比较。
详细信息参见 P15654 [省选联考 2026] 工业系统 / industry。
用法：输入两行不含空格的字符串，表示两个合法滚木集合。
输出：
x > y 表示第一个集合大于第二个集合。
x < y 表示第一个集合小于第二个集合。
x = y 表示第一个集合等于第二个集合。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct node
{
multiset<node> ms;
node()
{
ms.clear();
}
bool operator>(const node &oth) const
{
auto &x = ms;
auto &y = oth.ms;
for (auto it1 = x.rbegin(), it2 = y.rbegin(); it1 != x.rend() && it2 != y.rend(); it1++, it2++)
{
if (*it1 > *it2)
return 1;
else if (*it2 > *it1)
return 0;
}
return x.size() > y.size();
}
bool operator<(const node &oth) const
{
return oth > *this;
}
};
string x, y;
node read(string s)
{
stack<int> stk;
node gunmu;
int id = 0;
vector<node> v(1);
for (auto ch : s)
{
if (ch == '{')
{
v.emplace_back(gunmu);
stk.push(id);
id++;
}
else if (ch == '}')
{
node tmp = v[stk.top()];
stk.pop();
if (!stk.empty())
v[stk.top()].ms.insert(tmp);
}
else if (ch != ',')
{
v[stk.top()].ms.insert(gunmu);
}
}
return v[0];
}
signed main()
{
cin >> x >> y;
node X = read(x), Y = read(y);
if (X > Y)
{
puts("x > y");
}
else if (Y > X)
{
puts("x < y");
}
else
{
puts("x = y");
}
return 0;
}
|
