[2023 CSP-S T2]消消乐
解法关系图
1
2
3
4
| graph LR
A(N^3_算法1) -- 优化 -->B(N^2_算法2)
B -- 启发 --> C(哈希N^2_算法3)
B -- DP --> D(N_算法4)
|
算法一 (35pts)
枚举每一个子串，用栈判断子串是否合法，预计 。
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
| #include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
char a[2000005];
int ans;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> a + 1;
for(int i = 1; i <= n - 1; i++) {
for(int j = i + 1; j <= n; j++) {
if((j - i + 1) % 2) continue;
stack<pair<int, int> > st;
for(int k = i; k <= j; k++) {
if(!st.empty() && st.top().first == a[k] - 'a') st.pop();
else st.push(make_pair(a[k] - 'a', k));
}
if(st.size() == 0) ans++;
}
}
cout << ans << '\n';
return 0;
}
|
算法2 (50pts)
注意到并不需要枚举每个子串，每个子串必定是以该子串的首为首的串的子串。所以枚举每个前缀 ，用栈在 ~ 上匹配。
- 若在匹配到 时栈空，证明 ~ 是合法子串，记录即可。
预计 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
char a[2000005];
int ans;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cin >> a + 1;
for(int i = 1; i <= n; i++) {
stack<pair<int, int> > st;
for(int j = i; j <= n; j++) {
if(!st.empty() && st.top().first == a[j] - 'a') st.pop();
else st.push(make_pair(a[j] - 'a', j));
if(st.size() == 0) ans++;
}
}
cout << ans << '\n';
return 0;
}
|
算法3 (100pts)
摘编自洛谷题解
首先考虑一个串可以被消除时的结构：
- 可以被消除。
- 若 和 均可以被消除，则 也可以被消除。
- 若 可以被消除，则 也可以被消除。
观察到这个东西跟“合法括号序列”的定义很像，所以我们考虑枚举左端点，然后移动右端点，开个栈去膜你，就得到了一个 的做法。
进一步的，考虑我们固定左端点为 1，当右端点移动到 时，当前栈里元素为 ；当右端点移动到 时，栈里元素再一次变成 。那么说明了什么？也就是说， 范围内的字符串被完全消除了。
但其实这样子讲也不是很准确。
比如：字符串为 ，，但是在我们膜你过程中，第 2 个 明明是和第 1 个 消除了，但是在我们的意思中，他似乎是和第 3 个 消除了，这样子不会多记/少记吗？
实际上并不会。感性理解一下，如果说我们加入了几个字符，把原来栈顶的几个元素给消掉了，那么我们要再加入几个字符，使得加入后得到的新栈和原来栈相等，那说明了什么？说明了加入的几个字符和消掉的几个字符是相等的。也就是新加入的所有字符可以互相抵消。
那么我们时时维护一个栈，每加入一个字符后计算一下其哈希值（可以时时维护），然后丢到一个 map 里，并且查一下 map 里有几个跟他相同的。
然后就做完了，复杂度 ，如果用 unordered_map 代替 map，理论上可以做到 。
算法4 (100pts)
