A 通配符匹配

问可带有通配符$*$的$s$串能否匹配上$t$串

code

 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
#include <bits/stdc++.h>
using namespace std;
#ifdef __LOCAL_DEBUG__
# define _debug(fmt,...)fprintf(stderr,"\033[94m%s: " fmt "\n\033[0m",__func__,##__VA_ARGS__)
#define dg(a) cout <<"\033[94m" <<#a << "\033[0m = "<< a << endl;
#else
#define _debug(...) ((void)0)
#define dg(a)((void)0)
#endif

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    unsigned long n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    if (s == t) {
        cout << "YES\n";
    } else {
        unsigned long idx = s.find('*');
        string pres(s, 0, idx), pret(t, 0, idx);
//        dg(pres); dg(pret);
        if (pres != pret) {
            cout << "NO\n";
            return 0;
        }
        string posts = string(s, idx + 1, n - idx - 1);
//        dg(posts);
        for (unsigned long i = m - 1, j = posts.length() - 1; ~j; i--, j--) {
            if (posts[j] != t[i] || i < idx) {
                cout << "NO\n";
                return 0;
            }
        }
        cout << "YES\n";
    }
}

B 组合计数

给出n,k, 问有多少组(a,b)(a≠b)满足a+b==k 讨论a的取值情况(k - n > 0 ? k - n : 1), 注意如果n是偶数不用考虑(3,4)和(4,3)的情况

code

1
2
3
4
5
6
7
int main() {
    ll n, k, ans = 0;
    cin >> n >> k;
    if (k > 2 * n - 1) ans = 0;
    else ans = k / 2 - (k - n > 0 ? k - n : 1);
    cout << ans + (k & 1) << endl;
}

C 平衡括号子序列

题意: 给出长度为n的平衡括号, 找出长度为k的平衡子序列 >8 8 (()(())) (()(())) 10 8 ((())(())) ((())())

思路: (固定输出为k/2, 1表示这个(在答案序列中未匹配上), 0表示这个(不在答案序列中, 起占位作用, 这两种情况按顺序匹配), 遇到), 如果(标记是1输出), 如果是0, 跳过输出

code

 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
#include <bits/stdc++.h>

using namespace std;
#ifdef __LOCAL_DEBUG__
#define _debug(fmt, ...)fprintf(stderr,"\033[94m%s: " fmt "\n\033[0m",__func__,##__VA_ARGS__)
#define dg(a) cout <<"\033[94m" <<#a << "\033[0m = "<< a << endl;
#else
#define _debug(...) ((void)0)
#define dg(a)((void)0)
#endif

typedef long long ll;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    string ans;
    stack<int> stk;
    k >>= 1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            if (k) {
                k--;
                cout << "(";
                stk.push(1);
            } else {
                stk.push(0);
            }
        } else {
            if (stk.top()) cout << ")";
            stk.pop();
        }
    }
    cout << endl;
}