ABC312

V_Melville精進録 / 2023-07-30 / 原文

T1：Chord

模拟

代码实现

s = input()
if s in 'ACE, BDF, CEG, DFA, EGB, FAC, GBD':
    print('Yes')
else:
    print('No')

T2：TaK Code

模拟

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

bool check(vector<string> s) {
    rep(i, 3)rep(j, 3) if (s[i][j] != '#') return false;
    rep(i, 3)rep(j, 3) if (s[8-i][8-j] != '#') return false;
    rep(i, 4)rep(j, 4) {
        if (i < 3 and j < 3) continue;
        if (s[i][j] != '.') return false;
        if (s[8-i][8-j] != '.') return false;
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    rep(si, n-8)rep(sj, m-8) {
        vector<string> t(9);
        rep(i, 9)rep(j, 9) t[i] += s[si+i][sj+j];
        if (check(t)) cout << si+1 << ' ' << sj+1 << '\n';
    }
    
    return 0;
}

T3：Invisible Hand

二分答案

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n), b(m);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    
    int wa = 0, ac = 1001001001;
    while (ac-wa > 1) {
        int wj = (ac+wa)/2;
        int na = 0, nb = 0;
        rep(i, n) if (a[i] <= wj) na++;
        rep(i, m) if (b[i] >= wj) nb++;
        if (na >= nb) ac = wj; else wa = wj;
    }
    
    cout << ac << '\n';
    
    return 0;
}

T4：Count Bracket Sequences

将 ( 看成 +1，将 ) 看成 -1，合法括号序列的前提条件是要保证任意位置处的前缀和 \(\geqslant 0\)

然后暴力 \(\operatorname{dp}\) 即可

记 dp[i][j] 表示到第 \(i\) 个字符为止的前缀和为 \(j\) 的合法方案数
最后的答案为 \(\operatorname{dp}[n][0]\)

时间复杂度为 \(\mathcal{O}(n^2)\)

代码实现

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using mint = modint998244353;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    vector dp(n+1, vector<mint>(n+1));
    dp[0][0] = 1;
    rep(i, n) {
        rep(j, n) {
            if (s[i] != ')') dp[i+1][j+1] += dp[i][j];
            if (s[i] != '(' and j > 0) dp[i+1][j-1] += dp[i][j];
        }
    }
    
    cout << dp[n][0].val() << '\n';
    
    return 0;
}