AT_abc312 复盘

A

一眼过去直接 \(if\) 秒了
AC code:

#include <bits/stdc++.h>
using namespace std;

string s;

int main(){
    cin >> s;
    if (s == "ACE" || s == "BDF" || s == "CEG" || s == "DFA" || s == "EGB" || s == "FAC" || s == "GBD") cout << "Yes";
    else cout <<" No";
    return 0;
}

B

直接暴力枚举左上角的点，然后去判断整一个矩阵是否满足要求。
注意边界问题。
AC code：

#include <bits/stdc++.h>
using namespace std;

int n, m;
string s[105];

bool check(int x, int y){
    for (int i = x; i <= x + 2; i++){
        for (int j = y; j <= y + 2; j++){
            if (s[i][j] == '.') return 0;
        }
    }
    for (int i = x; i <= x + 3; i++){
        if (s[i][y + 3] == '#') return 0;
    }
    for (int i = y; i <= y + 3; i++){
        if (s[x + 3][i] == '#') return 0;
    }
    for (int i = x + 6; i <= x + 8; i++){
        for (int j = y + 6; j <= y + 8; j++){
            if (s[i][j] == '.') return 0;
        }
    }
    for (int i = x + 5; i <= x + 8; i++){
        if (s[i][y + 5] == '#') return 0;
    }
    for (int i = y + 5; i <= y + 8; i++){
        if (s[x + 5][i] == '#') return 0;
    }
    return 1;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i <= n - 9; i++){
        for (int j = 0; j <= m - 9; j++){
            if (check(i, j)) cout << i + 1 << " " << j + 1 << endl;
        }
    }
    return 0;
}

C

一眼二分答案，直接二分最低的价格就好了，\(check\) 里面就写满足卖家的数量和买家的数量是否满足条件。
注意：二分的有边界要设为 \(10^{9} + 1\)。
AC code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m;
int a[200005], b[200005];

bool check(int mid){
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] <= mid) cnt1++;
    }
    for (int i = 1; i <= m; i++){
        if (b[i] >= mid) cnt2++;
    }
    return cnt1 >= cnt2;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    int l = 1, r = 1e9 + 1;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

D

根据题面很容易想到用递归，由小的可以推出来大的，显然可以推出一个递推或者说 \(dp\) 式子。
不难想到可以用 \(dp_{i,j}\) 表示第 \(i\) 个数前面有 \(j\) 个右括号，其中最后答案为 \(dp_{n, n/2}\)。
转移方程就是分类讨论，? 和 ( 和 )，其中 ? 为左括号和右括号之和再模上 \(998244353\)。转移方程不难，只要想到当前情况是由这一个带右括号，或者不带右括号转移过来的就行了。
AC code：

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
string s;
int dp[3005][3005];

int main(){
    cin >> s;
    s = ' ' + s;
    int len = s.size() - 1;
    if (len % 2 == 1) return cout << "0", 0;
    dp[0][0] = 1;
    for (int i = 1; i <= len; i++){
        for (int j = 0; j * 2 <= i; j++){
            if (s[i] == '?') dp[i][j] = ((j ? dp[i - 1][j - 1] : 0) + dp[i - 1][j]) % mod;
            else if (s[i] == '(') dp[i][j] = dp[i - 1][j];
            else dp[i][j] = j ? dp[i - 1][j - 1] : 0;
        }
    }
    cout << dp[len][len / 2];
    return 0;
}