复赛二：刮刮乐(game)

 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

/**************************************************************** 
 * Description: 2023年CSP提高组复赛第二题，刮刮乐 35分
 * Author: Alex Li
 * Date: 2024-07-16 16:53:33
 * LastEditTime: 2024-09-27 22:17:14
****************************************************************/
#include <iostream>
#include <stack>
using namespace std;

// 判断一个字符串是否可被完全消除
bool isEliminable(const string &str) {
    stack<char> s; // 创建一个栈用于模拟消除过程
    for (char ch : str) {
        if (!s.empty() && s.top() == ch) { // 如果栈不为空且栈顶元素等于当前字符
            s.pop(); // 弹出栈顶元素，表示消除一对相同字符
        } else {
            s.push(ch); // 否则，将当前字符压入栈中
        }
    }
    return s.empty(); // 如果最终栈为空，表示字符串可被完全消除
}

int main(){
    int n, ans = 0;
    cin >> n; // 输入字符串长度（实际程序中未直接使用）
    string str;
    cin >> str; // 输入字符串
    for(int i = 0; i < str.size(); i++) {
        for(int j = i + 1; j < str.size(); j++) {
            // 只有当子串长度为偶数时，才可能完全消除
            if ((j - i + 1) % 2 == 0 && isEliminable(str.substr(i, j - i + 1))) 
                ++ans; // 如果子串可被完全消除，计数器加一
        }
    }
    cout << ans; // 输出满足条件的子串数量
}

 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

/**************************************************************** 
 * Description:  2023年CSP提高组复赛第二题，刮刮乐 50分
 * Author: Alex Li
 * Date: 2024-07-16 13:14:32
 * LastEditTime: 2024-09-27 22:49:23
****************************************************************/
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int countEliminableSubstrings(const string &str) {
    int n = str.size();
    int count = 0;

    // 枚举所有的子串的起始位置
    for (int i = 0; i < n; ++i) {
        stack<char> s;
        // 以i为起始位置，向右扫描
        for (int j = i; j < n; ++j) {
            if (!s.empty() && s.top() == str[j]) {
                s.pop();
            } else {
                s.push(str[j]);
            }
            // 如果栈为空，说明当前子串可完全消除
            if (s.empty()) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;

    int result = countEliminableSubstrings(str);
    cout << result << endl;

    return 0;
}

 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

/**************************************************************** 
 * Description: 2023年提高组复赛第三题 刮刮乐  100分
 * Author: Alex Li
 * Date: 2024-09-28 14:49:14
 * LastEditTime: 2024-09-28 16:16:59
****************************************************************/
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int>  dp(n+1),lst(n+1);
    string s;
    cin >> s;
    s = ' ' + s; // 在字符串前添加一个空格，使字符串下标从1开始，方便处理

    long long ans = 0;

    // 遍历字符串中的每一个字符
    for (int i = 1; i <= n; i++) {
        // 从当前位置 i 向前寻找与 s[i] 相同的字符
        // 使用 lst[j] 进行跳跃，避免重复遍历
        for (int j = i - 1; j > 0; j = lst[j] - 1) {
            if (s[i] == s[j]) {
                lst[i] = j; // 记录匹配的位置
                break;      // 找到匹配字符后退出循环
            }
        }
        // 如果找到了匹配的位置
        if (lst[i]) {
            dp[i] = dp[lst[i] - 1] + 1; // 动态规划转移方程
            ans += dp[i];               // 累加答案
        }
    }
    cout << ans;
    return 0;
}