M30637: 合法出栈序列pub

stack, http://cs101.openjudge.cn/practice/M30637/

【黄宇曦 地球与空间科学学院】思路：贪心。直接模拟一下过程就行了。

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using usi = unordered_set<int>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string str;
    cin >> str;
    cin.ignore();
    string q;
    while (getline(cin, q)) {
        if (q.size() != str.size()) {
            cout << "NO\n";
            continue;
        }
        stack<char> st;
        int i = 0;
        for (auto ch : str) {
            st.push(ch);
            while (st.size() && i < q.size() && st.top() == q[i]) {
                st.pop();
                i++;
            }
        }
        if (st.empty() && i == q.size())
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

【江昊中 数学科学学院】思路：合法字符串的充要条件是每一字符后的所有比它序号更小的字符必须是降序排列的 (至于 cin 会跳过空行, 以及会出现原字符串里没有的字符的情况我是完全没考虑)

#include<bits/stdc++.h>
using namespace std;
const int M = 10005;

int main() {
    string s;
    getline(cin, s);
    int n = s.length();
    unordered_map<char, int> mp;
    for (int i = 0; i < n; i++) {
        mp[s[i]] = i;
    }

    while (getline(cin, s)) {
        if (s.length() != n) {
            cout << "NO" << endl;
            continue;
        }
        bool possible = true;
        for (int i = 0; i < n; i++) {
            if (!mp.count(s[i])) {
                possible = false;
                break;
            }
            int idx = mp[s[i]];
            int last = idx;
            for (int j = i + 1; j < n; j++) {
                int cur_idx = mp[s[j]];
                if (cur_idx < idx) {
                    if (cur_idx > last) {
                        possible = false;
                        break;
                    }
                    last = cur_idx;
                }
            }

        }
        if (possible) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}